LeetCode 122.买卖股票的最佳时机Ⅱ
题目链接:
LeetCode 122.买卖股票的最佳时机Ⅱ
解题思路:
把利润拆成,后一天减前一天的累加和。如何累加和大于0,则加到sum里,否则则不要。
代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int size = prices.size();
int sum =0;
for(int i=1;i<size;i++){
if(prices[i]-prices[i-1]>0){
sum+=prices[i]-prices[i-1];
}
}
return sum;
}
};
LeetCode 55.跳跃游戏
题目链接:
LeetCode 55.跳跃游戏
解题思路:
看能跳跃的覆盖范围,如果覆盖范围大于当前数组长度减一,则返回true。
代码:
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
if(nums.size()==1) return true;
for(int i = 0;i<=cover;i++){
cover = max(cover,i+nums[i]);
if( cover>=nums.size()-1){
return true;
break;
}
}
return false;
}
};
LeetCode 45.跳跃游戏Ⅱ
题目链接:
LeetCode 45.跳跃游戏Ⅱ
解题思路:
维护两个值,一个是当前覆盖范围一个是下一步的覆盖范围。当i遍历完当前覆盖范围时,将当前覆盖范围的值更新为下一步最大能覆盖到的范围。
代码:
class Solution {
public:
int jump(vector<int>& nums) {
int cur = 0;
int next = 0;
int result = 0;
for(int i= 0;i<nums.size();i++){
next = max(next,i+nums[i]);
if(cur == i){
if(cur!=nums.size()-1){
cur = next;
result++;
}
else break;
}
}
return result;
}
};