当前位置：首页 > article >正文

【Day24 LeetCode】贪心Ⅱ

article 2025/1/23 15:54:57

一、贪心Ⅱ

1、买卖股票的最佳时机 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、跳跃游戏 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]);
            else
                break;
            if(end >= n-1)
                return true;
        }
        return false;
    }
};

3、跳跃游戏Ⅱ 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、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;
    }
};