122.买卖股票的最佳时机II
完成
思路:
把每天的利润最大化,即可达到总利润的最大化。
把利润拆分到每一天,能获利就买。
代码
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for (int i = 0; i < prices.length-1; i++) {
int minus = prices[i+1]-prices[i];
if(minus > 0){
res += minus;
}
}
return res;
}
}
55. 跳跃游戏
完成
思路:
数组中的每个元素代表的是跳跃最大距离,而不是唯一距离。因此只需要看从第一个元素开始进行有效范围覆盖,能否覆盖到最后一个元素。
遍历组数时需要特别注意的是i
的范围限定,不是i < nums.length
,这样就遍历了整个数组,返回的一定是true
。
代码
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
// 注意这里i的范围不是 i < nums.length
for (int i = 0; i <= cover; i++) {
cover = Math.max(cover, i+nums[i]);
if(cover>=nums.length-1) return true;
}
return false;
}
}
45.跳跃游戏II
完成
思路:
本题也不需要纠结具体的路线,只要覆盖范围达到即可。
代码
class Solution {
public int jump(int[] nums) {
int res = 0;
// 当前覆盖的最远距离下标
int end = 0;
// 下一步覆盖的最远距离下标
int temp = 0;
for (int i = 0; i <= end && end < nums.length - 1; ++i) {
temp = Math.max(temp, i + nums[i]);
// 可达位置的改变次数就是跳跃次数
if (i == end) {
end = temp;
res++;
}
}
return res;
}
}