• 贪心算法巩固

    贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

    贪心算法并没有固定的套路。因而需要进一步巩固，多做做多有感觉才行。

    这次巩固题目来源：代码随想录

    1.贪心简单题

    （1）分发饼干，已做过。

    （2）1005.K次取反后最大化的数组和

     其实模拟就能做（每次改变最小的其实也是一种贪心）

    1.  
    2. class Solution {
    3. public:
    4.  
    5.     int largestSumAfterKNegations(vector<int>& nums, int k) {
    6.         int max = 0;
    7.         for (int i = 0; i < nums.size(); ++i) {
    8.             max += nums[i];
    9.         }
    10.         while (k--) {
    11.             int min = nums[0];
    12.             int dex = 0;
    13.             for (int i = 0; i < nums.size(); ++i) {
    14.                 if (min > nums[i]) {
    15.                     min = nums[i];
    16.                     dex = i;
    17.                 }
    18.             }
    19.             max -= nums[dex];
    20.             nums[dex] = -nums[dex];
    21.             max += nums[dex];
    22.  
    23.         }
    24.         return max;
    25.     }

    贪心也行：
    /*第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
    第二步：从前向后遍历，遇到负数将其变为正数，同时K--
    第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
    第四步：求和*/

    1. static bool cmp(int a, int b) {
    2.         return abs(a) > abs(b);
    3.     }
    4. public:
    5.     int largestSumAfterKNegations(vector<int>& A, int K) {
    6.         sort(A.begin(), A.end(), cmp);       // 第一步
    7.         for (int i = 0; i < A.size(); i++) { // 第二步
    8.             if (A[i] < 0 && K > 0) {
    9.                 A[i] *= -1;
    10.                 K--;
    11.             }
    12.         }
    13.         if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
    14.         int result = 0;
    15.         for (int a : A) result += a;        // 第四步
    16.         return result;
    17.     }

    （3）860.柠檬水找零

    • 情况一：账单是5，直接收下。
    • 情况二：账单是10，消耗一个5，增加一个10
    • 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
    1. class Solution {
    2. public:
    3.     bool lemonadeChange(vector<int>& bills) {
    4.         vector<int> cur(3,0);
    5.         for (int i = 0; i < bills.size(); ++i) {
    6.             if (bills[i] == 5) {
    7.                 cur[0] += 1;
    8.                 continue;
    9.             }
    10.             if (bills[i] == 10) {
    11.                 cur[1] += 1;
    12.                 if (cur[0] > 0) {
    13.                     --cur[0];
    14.                 }
    15.                 else {
    16.                     return false;
    17.                 }
    18.             }
    19.             if (bills[i] == 20) {
    20.                 cur[2] += 1;
    21.                 if (cur[0] > 0 && cur[1] > 0) {
    22.                     --cur[0];
    23.                     --cur[1];
    24.                 }
    25.                 else if (cur[0] >= 3) {
    26.                     cur[0] -= 3;
    27.                 }
    28.                 else {
    29.                     return false;
    30.                 }
    31.  
    32.             }
    33.  
    34.         }
    35.  
    36.         return true;
    37.     }
    38. };

    2.贪心中等题

    贪心中等题，靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。

    （1）738.单调递增的数字

    这个说白了是个数学问题，怎么能最小呢？

    首先先把每一位存到数组里面，然后从后往前遍历：

         * 思路：
         *  从右向左扫描数字，若发现当前数字比其左边一位（较高位）小，
         *  则把其左边一位数字减1，并将该位及其右边的所有位改成9 

    仔细想想，这很正确

    1. class Solution {
    2. public:
    3.  
    4.     void turnNine(vector<int>& num,int left) {
    5.         for (int i = left; i < num.size(); ++i) {
    6.             num[i] = 9;
    7.         }
    8.     }
    9.  
    10.     int monotoneIncreasingDigits(int n) {
    11.         int len = 0;
    12.         int temp = n;
    13.         while (temp) {
    14.             ++len;
    15.             temp = temp / 10;
    16.         }
    17.         temp = n;
    18.         vector<int> num(len);
    19.         int i = len - 1;
    20.         while (temp) {
    21.             int tail = temp % 10;
    22.             temp /= 10;
    23.             num[i--] = tail;
    24.         }
    25.         /**
    26.      * 思路：
    27.      *  从右向左扫描数字，若发现当前数字比其左边一位（较高位）小，
    28.      *  则把其左边一位数字减1，并将该位及其右边的所有位改成9
    29.      */
    30.         for (int i = len - 1; i > 0; --i) {
    31.             if (num[i - 1] > num[i]) {
    32.                 num[i - 1] -= 1;
    33.                 turnNine(num, i);
    34.             }
    35.  
    36.         }
    37.         int rs = 0;
    38.         for (int i = 0; i < len; ++i) {
    39.             rs = rs * 10 + num[i];
    40.         }
    41.         return rs;
    42.     }
    43. };

    （2）376. 摆动序列

    这还真的挺难，不会做

    法一：贪心

    //贪心，转化为上坡下坡，有几个坡。最后不忘加一就行（这里事先就加一了）
    //保持区间波动，只需要把单调区间上的元素移除就可以了。 

     实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

    这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点。

    于是这就转化为了求有几个坡（ 包括上坡下坡）的问题

    1. class Solution1{
    2. public:
    3.     //注意不能为0
    4.     int wiggleMaxLength(vector<int>& nums) {
    5.         if (nums.size() <= 1) return nums.size();
    6.         int curDiff = 0; // 当前一对差值
    7.         int preDiff = 0; // 前一对差值
    8.         int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
    9.         for (int i = 0; i < nums.size() - 1; i++) {
    10.             curDiff = nums[i + 1] - nums[i];
    11.             // 出现峰值
    12.             //cur不能为0，prediff=0仅仅在第一次判断时用，我们假设0号元素（也就是第一个元素）的prediff=0
    13.             if ((curDiff > 0 && preDiff <= 0) //当前上坡，前一个下坡
    14.                 || (preDiff >= 0 && curDiff < 0)) {//前一个上坡，当前下坡
    15.                 result++;
    16.                 preDiff = curDiff;
    17.             }
    18.         }
    19.         return result;
    20.     }
    21. };

    法二 dp

    设dp状态dp[i][0]，表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度
    设dp状态dp[i][1]，表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度
    dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，
    表示将nums[i]接到前面某个山谷后面，作为山峰。
    dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，
    表示将nums[i]接到前面某个山峰后面，作为山谷

    1. class Solution {
    2. public:
    3.     int dp[1005][2];
    4.     int wiggleMaxLength(vector<int>& nums) {
    5.         memset(dp, 0, sizeof dp);
    6.         dp[0][0] = dp[0][1] = 1;
    7.  
    8.         for (int i = 1; i < nums.size(); ++i)
    9.         {
    10.             dp[i][0] = dp[i][1] = 1;
    11.  
    12.             for (int j = 0; j < i; ++j)
    13.             {
    14.                 if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
    15.             }
    16.  
    17.             for (int j = 0; j < i; ++j)
    18.             {
    19.                 if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
    20.             }
    21.         }
    22.         return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    23.     }
    24. };

    3.贪心解决股票问题

    (1)122.买卖股票的最佳时机II

    做过了，思路就是每天都可以卖出然后买进，只要比昨天高就卖然后再买

    [7, 1, 5, 6]   ——》  （5-1）+ （6-5）= 5

    (2）714. 买卖股票的最佳时机含手续费

    这个就不会了。好好审题。

    法一贪心

    本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。

    如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖

    无非就是要找到两个点，买入日期，和卖出日期

    所以我们在做收获利润操作的时候其实有三种情况：

     这三个情况要深刻体会，尤其是第一种，如何用代码实现，并且和第二种连接。

    1. //妙，很难，多思考
    2. class Solution {
    3. public:
    4.     int maxProfit(vector<int>& prices, int fee) {
    5.         int result = 0;
    6.         int minPrice = prices[0]; // 记录最低价格
    7.         for (int i = 1; i < prices.size(); i++) {
    8.             // 情况二：相当于买入
    9.             if (prices[i] < minPrice) minPrice = prices[i];
    10.  
    11.             // 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
    12.             if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
    13.                 continue;
    14.             }
    15.  
    16.             // 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
    17.             if (prices[i] > minPrice + fee) {
    18.                 result += prices[i] - minPrice - fee;
    19.                 minPrice = prices[i] - fee; // 情况一，这一步很关键
    20.             }
    21.         }
    22.         return result;
    23.     }
    24. };
    25.
    • 时间复杂度：O(n)
    • 空间复杂度：O(1)

    从代码中可以看出对情况一的操作，因为如果还在收获利润的区间里，表示并不是真正的卖出，而计算利润每次都要减去手续费，所以要让minPrice = prices[i] - fee;，这样在明天收获利润的时候，才不会多减一次手续费！

    这里有个更好理解的：

    1. class Solution {
    2.     public int maxProfit(int[] prices, int fee) {
    3.         if (prices.length == 1) return 0; // 长度为1，没有交易空间；
    4.  
    5.         int base = prices[0] + fee; // 本身带交易费的买入，后面高于这个部分的，都是利润；
    6.         int profit = 0;
    7.  
    8.         for (int i = 1; i < prices.length; ++i) {
    9.             if (prices[i] > base) { // 高于的，都是利润；
    10.                 profit += prices[i] - base;
    11.                 base = prices[i]; // 一直往上走；
    12.             }
    13.             else if (prices[i] + fee < base) { // 一旦遇到下降，说明利润达到顶点了，转为下滑；
    14.                 // 不断试探，最低点（买入点）在哪里；但是只要遇到高点，if语句就会加入利润
    15.                 base = prices[i] + fee;
    16.             }
    17.         }
    18.  
    19.         return profit;
    20.     }
    21. }

    法二dp

    dp1[i]表示第i天手上有股票，dp2[i]表示第i天手上没有股票，递归方程：

    dp1[i] = max(dp1[i-1], dp2[i-1] - prices[i]) （第二项表示在第i天买入股票）
    dp2[i] = max(dp2[i-1], dp1[i-1] + prices[i] - fee) （第二项表示在第i天将股票卖出，需扣除手续费）

    1. class Solution2 {
    2. public:
    3.     int maxProfit(vector<int>& prices, int fee) {
    4.         vector<int>dp1(prices.size(), 0);
    5.         vector<int>dp2(prices.size(), 0);
    6.         if (prices.size() < 2) {
    7.             return 0;
    8.         }
    9.         dp1[0] -= prices[0];
    10.         for (int i = 1; i < prices.size(); ++i) {
    11.             dp1[i] = max( dp1[i - 1],dp2[i - 1] - prices[i] );
    12.             dp2[i] = max(dp2[i - 1], dp1[i - 1] - fee+ prices[i]);
    13.         }
    14.         
    15.         //最后一天后肯定都卖了
    16.         return dp2[prices.size() - 1];
    17.  
    18.  
    19.     }
    20. };

    4.两个维度权衡问题   

    分发糖果和根据身高重建队列

    遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。

    如果两个维度一起考虑一定会顾此失彼。

    比如重建队列：

    如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。

    那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

    此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

    5.区间问题

    （1）

     (2)55. 跳跃游戏

    1.  
    2. //跳跃覆盖范围究竟可不可以覆盖到终点
    3. //贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），
    4. //整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
    5. class Solution {
    6. public:
    7.     bool canJump(vector<int>& nums) {
    8.         int cur = 0;
    9.         if (nums.size() <= 1) return true;
    10.         int range = nums[cur];
    11.         int i = 0;
    12.         while (i <= range) {
    13.             if (i >= nums.size() - 1) {
    14.                 return true;
    15.             }
    16.             if (i + nums[i] > range) {
    17.                 range = nums[i] + i;
    18.             }//范围扩大
    19.             ++i;
    20.  
    21.         }
    22.         return false;
    23.     }
    24. };

    (3)45.跳跃游戏II

    这个难一点

     

    先第一个元素获取第一个范围，然后在这第一个范围里面找到值最大的数，作为新的范围，如此反复，然后这里说了一定可以跳到最后，所以我们不用担心无解

    1.  
    2. class Solution {
    3. public:
    4.     int jump(vector<int>& nums) {
    5.         int cur = 0;
    6.         if (nums.size() <= 1) return 0;
    7.         int range = nums[cur];
    8.         int rs = 1;//第一步肯定要跳
    9.         int max = range;
    10.         int p = 0;//加快内部的for
    11.         while (rangesize()-1) {
    12.             for (int i = p; i <=range; ++i) {//这里是等于，很重要
    13.                 if (i + nums[i] > max) {
    14.                     max = i + nums[i];
    15.                 }
    16.             }
    17.             p += range;
    18.             range = max;
    19.             ++rs;
    20.         }
    21.         return rs;
    22.     }
    23. };

    （4）56. 合并区间

    模拟的过程就是贪心啦。

    排序然后分情况处理，排序用引用加快速度

    1. class Solution {
    2. public:
    3.     vectorint>> merge(vectorint>>& intervals) {
    4.         if (intervals.size()<=1 ){
    5.             return  intervals;
    6.         }
    7.    
    8.         sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b)->bool {
    9.             return a[0] < b[0];//这里按左边界排序
    10.             });
    11.         vectorint>> rs;
    12.         vector<int> temp;
    13.  
    14.         int end = intervals[0][1];
    15.         int start = intervals[0][0];
    16.         temp.push_back(start);
    17.         temp.push_back(end);
    18.         for (int i = 1; i < intervals.size(); ++i) {
    19.             if (intervals[i][0] <= end) {
    20.                 if (intervals[i][1] > end) {
    21.                     end = intervals[i][1];
    22.                 }
    23.                 temp.pop_back();
    24.                 temp.push_back(end);
    25.             }
    26.             else {
    27.                 rs.push_back(temp);
    28.                 temp.clear();
    29.                 start = intervals[i][0];
    30.                 end = intervals[i][1];
    31.                 temp.push_back(start);
    32.                 temp.push_back(end);
    33.  
    34.             }
    35.             if (i == intervals.size() - 1) {
    36.                 rs.push_back(temp);
    37.             }
    38.         }
    39.         return rs;
    40.  
    41.     }
    42. };

     6.其他

    （1）53. 最大子序和 

    第一反应用动态规划而不是贪心

    dp
    /*定义一个函数f(n)，以第n个数为结束点的子数列的最大和，
    存在一个递推关系f(n) = max(f(n-1) + A[n], A[n]);

    将这些最大和保存下来后，取最大的那个就是，最大子数组和。
    因为最大连续子数组 等价于 最大的以n个数为结束点的子数列和*/

    1.  
    2. class Solution {
    3. public:
    4.     //f_n表示n为终点的最大子数组和
    5.     int maxSubArray(vector<int>& nums) {
    6.         if (nums.size() == 0)return NULL;
    7.         int res = INT_MIN;
    8.         int f_n = -1;
    9.         for (int i = 0; i < nums.size(); ++i) {
    10.             f_n = max(nums[i], f_n + nums[i]);
    11.             res = max(f_n, res);
    12.         }
    13.  
    14.         return res;
    15.  
    16.  
    17.     }
    18. };

    牛逼的！

    法二：暴力

    1. class Solution2 {
    2. public:
    3.     int maxSubArray(vector<int>& nums) {
    4.         int result = INT32_MIN;
    5.         int count = 0;
    6.         for (int i = 0; i < nums.size(); i++) { // 设置起始位置
    7.             count = 0;
    8.             for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
    9.                 count += nums[j];
    10.                 result = count > result ? count : result;
    11.             }
    12.         }
    13.         return result;
    14.     }
    15. };

    法三：贪心

    关键在于：不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数。

    如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

    局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

    全局最优：选取最大“连续和”

    1. class Solution {
    2. public:
    3.     int maxSubArray(vector<int>& nums) {
    4.         int result = INT32_MIN;
    5.         int count = 0;
    6.         for (int i = 0; i < nums.size(); i++) {
    7.             count += nums[i];
    8.             if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
    9.                 result = count;
    10.             }
    11.             if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
    12.         }
    13.         return result;
    14.     }
    15. };

    （2）134. 加油站

     很妙的解法，看代码来体会，这题我是不会的

    1. class Solution {
    2. public:
    3.  
    4.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    5.         int rest = 0, run = 0, start = 0;
    6.         //rest是计算是否有解的，也就是说如果没有解，其实就是所有的gas加起来小于cost
    7.         //run代表实时的油量
    8.         //start就是起点
    9.         for (int i = 0; i < gas.size(); ++i) {
    10.             run += (gas[i] - cost[i]);
    11.             rest += (gas[i] - cost[i]);
    12.             if (run < 0) {
    13.                 start = i + 1;//为什么不是i？因为如果run此时小于0了就说明i-i+1这一段的cost大于之前剩余的油量加上第i站加油站的油量
    14.                 //所以必须是i+1
    15.                 run = 0;
    16.             }
    17.         }
    18.         return rest < 0 ?
    19.             -1 : start;
    20.     }
    21.  
    22. };

    当然还有个暴力的：

    //暴力
    class Solution2 {
    public:
        int canCompleteCircuit(vector& gas, vector& cost) {
            for (int i = 0; i < cost.size(); i++) {
                int rest = gas[i] - cost[i]; // 记录剩余油量
                int index = (i + 1) % cost.size();
                while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈
                    rest += gas[index] - cost[index];
                    index = (index + 1) % cost.size();
                }
                // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
                if (rest >= 0 && index == i) return i;
            }
            return -1;
        }
    };

    （3）968.监控二叉树

     每个节点有三种状态：节点上有摄像机，节点没摄像机但是被摄像机覆盖，节点没摄像机也没被覆盖。

    1. // 版本一
    2. class Solution {
    3. private:
    4.     int result;
    5.     int traversal(TreeNode* cur) {
    6.  
    7.         // 空节点，该节点有覆盖
    8.         if (cur == NULL) return 2;
    9.  
    10.         int left = traversal(cur->left);    // 左
    11.         int right = traversal(cur->right);  // 右
    12.  
    13.         // 情况1
    14.         // 左右节点都有覆盖
    15.         if (left == 2 && right == 2) return 0;
    16.  
    17.         // 情况2
    18.         // left == 0 && right == 0 左右节点无覆盖
    19.         // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
    20.         // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
    21.         // left == 0 && right == 2 左节点无覆盖，右节点覆盖
    22.         // left == 2 && right == 0 左节点覆盖，右节点无覆盖
    23.         if (left == 0 || right == 0) {
    24.             result++;
    25.             return 1;
    26.         }
    27.  
    28.         // 情况3
    29.         // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
    30.         // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
    31.         // left == 1 && right == 1 左右节点都有摄像头
    32.         // 其他情况前段代码均已覆盖
    33.         if (left == 1 || right == 1) return 2;
    34.  
    35.         // 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
    36.         // 这个 return -1 逻辑不会走到这里。
    37.         return -1;
    38.     }
    39.  
    40. public:
    41.     int minCameraCover(TreeNode* root) {
    42.         result = 0;
    43.         // 情况4
    44.         if (traversal(root) == 0) { // root 无覆盖，判断根节点
    45.             result++;
    46.         }
    47.         return result;
    48.     }
    49. };

    简化后：

    1.  
    2. // 版本二
    3. class Solution {
    4. private:
    5.     int result;
    6.     int traversal(TreeNode* cur) {
    7.         if (cur == NULL) return 2;
    8.         int left = traversal(cur->left);    // 左
    9.         int right = traversal(cur->right);  // 右
    10.         if (left == 2 && right == 2) return 0;
    11.         else if (left == 0 || right == 0) {
    12.             result++;
    13.             return 1;
    14.         }
    15.         else return 2;
    16.     }
    17. public:
    18.     int minCameraCover(TreeNode* root) {
    19.         result = 0;
    20.         if (traversal(root) == 0) { // root 无覆盖
    21.             result++;
    22.         }
    23.         return result;
    24.     }
    25. };

  • 相关阅读:
    heic图片转换
    EFCore的新东西
    详细了解Redis的八种数据类型及应用场景分析
    OPNET Modeler 的安装及其相关配置
    Tomcat安装及配置教程
    Vue2--11种组件通信、Vue2处理响应式数据
    vue实现blob文档流下载文件
    arthas进阶版排查问题之idea插件工具操作
    轻松导航：教你在Excel中添加超链接功能
    [MAUI]集成富文本编辑器Editor.js至.NET MAUI Blazor项目
  • 原文地址：https://blog.csdn.net/keepstrivingchy/article/details/127038901