【Day24 LeetCode】贪心Ⅱ

一、贪心Ⅱ

1、leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/" rel="nofollow">买卖股票的最佳时机 II 122

这题第一想法是使用动态规划做，每天有两个状态，持有股票和非持有股票，每次计算这两个状态下的最优值。

class Solution {
public:int maxProfit(vector<int>& prices) {//表示当前 没有/有股票的两个状态int dp0 = 0, dp1 = -prices[0]; for(int i=1; i<prices.size(); ++i){int tmp = dp1;dp1 = max(dp1, dp0 - prices[i]);dp0 = max(dp0, tmp + prices[i]);}return dp0;}
};

贪心的做法就是只要当前股票值会在明天上升，则在当前进行购买，在明天进行售卖获取利润。因为要求只能持有一只股票，即使price[i]到price[j]之间股票一直在涨，亦可将利润划分成 $p r i ce [j] - p r i ce [i] = (p r i ce [j] - p r i ce [j - 1]) + (p r i ce [j - 1] - p r i ce [j - 2]) + ... + (p r i ce [i + 1] - p r i ce [i])$ ，所以每天的正利润构成了最后的总利润。

class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0;for(int i=1; i<prices.size(); ++i)ans += max(prices[i]-prices[i-1], 0);return ans;}
};

这题采用动态规划的思路更容易想到一点。

2、leetcode.cn/problems/jump-game/description/" rel="nofollow">跳跃游戏 55

思路：找到最大的跳跃范围，看能不能跳到终点。每次取当前点能跳的最远点作为跳跃范围，在这个合法的范围内不断更新最大范围。

class Solution {
public:bool canJump(vector<int>& nums) {int end = 0, n = nums.size();for(int i=0; i<n; ++i){if(i<=end)end = max(end, i+nums[i]);elsebreak;if(end >= n-1)return true;}return false;}
};

3、leetcode.cn/problems/jump-game-ii/description/" rel="nofollow">跳跃游戏Ⅱ 45

这题在上一题跳跃游戏的基础上需要找到最小跳跃次数，思路是：在当前这跳的范围内选择一个作为起点，可达终点最远。当遍历到当前这跳的边界，可是视为已经完成一跳，直到当前这跳范围已达最终终点。

class Solution {
public:int jump(vector<int>& nums) {// curEnd记录当前这一跳的范围终点，nxtEnd记录下一跳的最大范围终点int curEnd = 0, nxtEnd = 0; int n = nums.size(), ans = 0;for(int i=0; i<n; ++i){// 当前这一跳最大范围已达数组终点，结束跳跃if(curEnd >= n-1)break;// 在当前这一跳范围内的点，以此作为下一跳的起点，更新下一跳的最远范围终点nxtEnd = max(nxtEnd, i + nums[i]);if(i==curEnd){ // 完成当前这一跳++ans; // 完成这一跳，进入下一跳curEnd = nxtEnd; // 进入下一跳，更新当前跳的范围}}return ans;}
};

4、leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/" rel="nofollow">K次取反后最大化的数组和 1005

思路：先将数组从小到大排序，遇到负数且有次数就反转该负数，这样越小的负数反转得到的值越大。最后判断是否有次数剩余，如果剩余奇数次，则需要再进行一次反转，对哪个数进行反转最有利呢？有次数剩余的情况下一定会是数组内已经没有负数了，所以当然对最小值进行反转最有利。

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int n = nums.size();sort(nums.begin(), nums.end());  // 从小到大排序int i = 0;while(i<n && k>0){if(nums[i] < 0){ // 遇到负数反转nums[i] *= -1;--k;}++i;}int s = 0, MIN = INT_MAX;for(int num : nums){// 计算 数组和s += num;// 有k剩余 则需要找到数组的最小值if(k % 2)MIN = min(MIN, num);}// 有k剩余，则对数组和s减去2倍的数组最小值// 因为是要反转这个最小值，而s已经加过没反转的最小值，所以是2倍s += (MIN < INT_MAX ? -2 * MIN : 0); return s;}
};