贪心
# 121. 买卖股票的最佳时机 (opens new window)
class Solution {
public int maxProfit(int[] prices) {
int ret = 0;
int min = Integer.MAX_VALUE;
for(int i=0;i<prices.length;i++){
min = Math.min(min,prices[i]);
ret = Math.max(prices[i]-min,ret);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 55. 跳跃游戏 (opens new window)
方法一：贪心
class Solution {
public boolean canJump(int[] nums) {
int max = 0;
for(int i=0;i<=max;i++){
max = Math.max(max,i+nums[i]);
if(max>=nums.length-1)
return true;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
方法二：动态规划
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
// 能否跳到该位置
boolean[] dp = new boolean[n];
dp[0] = true;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(dp[j] && (i-j)<=nums[j]){
dp[i] = true;
break;
}
}
}
return dp[n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
另一种状态定义：i 点之前能跳的最远距离
class Solution { public boolean canJump(int[] nums) { int n = nums.length; if(n==1) return true; if(nums[0]==0) return false; // i点之前能跳的最远距离 int[] dp = new int[n]; dp[0] = nums[0]; for(int i=1;i<n-1;i++){ dp[i] = Math.max(dp[i-1],nums[i]+i); if(dp[i]>=n-1) return true; if(dp[i]==i) return false; } return true; } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 45. 跳跃游戏 II (opens new window)
方法一：贪心
class Solution {
public int jump(int[] nums) {
int end = 0;
int max = 0;
int ret = 0;
int n = nums.length;
for(int i=0;i<n-1;i++){
max = Math.max(max,i+nums[i]);
if(i==end){
end = max;
ret++;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
方法二：动态规划
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp,Integer.MAX_VALUE/2);
dp[0] = 0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(i-j<=nums[j]){
dp[i] = Math.min(dp[j]+1,dp[i]);
}
}
}
return dp[n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 134. 加油站 (opens new window)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// 全程油量，局部油量（<0起始位置需要改）
int sum = 0,partSum = 0;
int start = 0;
int n = gas.length;
for(int i=0;i<n;i++){
sum += gas[i]-cost[i];
partSum += gas[i]-cost[i];
if(partSum<0){
partSum = 0;
start = i+1;// 能说明前面都不是答案，只能向后继续寻找
}
}
if(sum<0)
return -1;
return start;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 763. 划分字母区间 (opens new window)
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> ret = new ArrayList<>();
int[] map = new int[26];
char[] cs = s.toCharArray();
for(int i=0;i<cs.length;i++){
map[cs[i]-'a'] = i;
}
int start=-1,end=0;
for(int i=0;i<cs.length;i++){
end = Math.max(end,map[cs[i]-'a']);
if(i==end){
ret.add(i-start);
start = i;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 561. 数组拆分 (opens new window)
class Solution {
public int arrayPairSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int ret = 0;
for(int i=0;i<n;i+=2){
ret += nums[i];
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11