Day32 贪心算法 part02
我的思路:
只有当后一天比前一天价格高时,才出售,profit才累加
解答:
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0) {
return 0;
}
int profit = 0;
for(int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
}
我的思路:
想简单了,没有考虑到step指的是最大跳跃格数,可以跳小,[2, 5, 0, 0] 这个例子过不去
后来还是老实按照题解,先把maxJump算出来,和当前i进行对比
解答:
class Solution {
public boolean canJump(int[] nums) {
int maxJump = nums[0];
for(int i = 0; i < nums.length - 1; i++) {
if(maxJump < i) {
return false;
}
maxJump = Math.max(maxJump, i + nums[i]);
if(maxJump >= nums.length - 1) {
return true;
}
}
return maxJump >= nums.length - 1;
}
}
我的思路:
把当前i下一个最大跳转数记录下来,当到了该位置的时候,进行跳转并计数
解答:
class Solution {
public int jump(int[] nums) {
if(nums == null) {
return 0;
}
int currMax = 0;
int nextMax = 0;
int count = 0;
for(int i = 0; i < nums.length - 1; i++) {
nextMax = Math.max(nextMax, i + nums[i]);
if(currMax == i) {
currMax = nextMax;
count++;
}
}
return count;
}
}