触碰贪心，不能说完全拿捏，起码知道了所以然，知道了贪心的侧重点是证明了~

目录

• • 前言
  • 浅谈贪心
  • 第一题 1221. 分割平衡字符串
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
    • • 解法①——常规模拟
      • 解法② —— 贪心
  • 第二题 1827. 最少 *** 作使数组递增
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 第三题 2144. 打折购买糖果的最小开销
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)
  • 第四题 1400. 构造 K 个回文字符串
  • • 💒题目描述
    • 🌟解题报告
    • 🌻参考代码(C++版本)

前言

每日算法练习，千锤百炼，静待花开。


现在的单片机是会持续更的，因为我要靠它去捣腾暑假实习的事儿：十四天学会51单片机；
Leetcode的专栏会持续更，因为在跟着英雄哥做知识星球的事儿：在lc被欺负的这些年；
对英雄哥的知识星球有兴趣的可以看看他这篇文章喔： 英雄算法联盟 | 31天让你的算法与众不同

至于现在这专栏了，是我4月12号的想法，只是因为四月我整体比较痛苦，一直没有动工，现在开始动工啦~，迟到一个月。这个专栏只会记录全部是每日一题：知识星球每天的习题，以及在咱高校算法学习社区中，泡泡和p佬普及组和提高组的题目，一般是当天写当天更吧。我一般会先写星球上的题，因为泡泡他俩的题有点难，得晚点补上


倘若对算法学习比较迷茫的小伙伴，可以考虑假如咱高校算法学习社区呀~

社区地址：高校算法学习社区


社区暂时有每日一题普及组以及提高组，由现役Acmer每日出题带领刷题，不会可群里随时提问喔。只是咱们拒绝划水党以及潜水党，需要的加入可私信执梗，也可以私信我哈。

浅谈贪心

浅翻了一下李煜东老师的《算法竞赛进阶指南》，他是这么说贪心的：

贪心是一种每次决策时采取当前意义下最优策略的算法，因此，使用贪心要求问题的整体最优是可以从局部最优推导出来的。贪心算法的正确性是需要证明的。

我也零零散散听到很多小伙伴说贪心是生活题，也就是直接可以从咱们的生活思维中找到实现的逻辑，比如下面第一题的分割字符串，要得到满足要求的字符串最多，那么很容易想到呀，每次分割的时候尽可能的小，但是这个想法怎么证明正确了

宫水三叶大大是这么形容贪心的

所有咱们还是老老实实学怎么证明吧

关于贪心的证明，李煜东老师总结了这些常见的手段

① 微扰(邻项交换)
证明在任意局面下，任何对局部最优策略的微小改变都会造成真题结果的变差。经常用于以"排序"为贪心策略的证明
② 范围缩小
证明任何对局部最优策略作用范围的拓展都不会造成整体结果变差
③ 决策包容性
证明在任意局面下，作出局部最优策略之后，在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换而言之，这局部最优策略提供的可能性包含了其他所有策略提供的可能性
④ 反证法
⑤ 数学归纳法

我现在的观念了，上面李老师总结这些证明方式，当做积累就好，零零散散的看到其他佬佬们的证明了，也浅记一下怎么证明的，学习是一个记忆的过程，不是创造的过程，模型和解法积累多了，我相信看到贪心的题就知道怎么证明了。
昨天的的第三题中，宫水大大用的是反证法，浅积累一下

第一题 1221. 分割平衡字符串

归纳法证明贪心

💒题目描述

原题传送门

🌟解题报告

因为我不太会贪心（以前听y总讲课说贪心比较难，就战术性的逃避了贪心）。 这个题对于我而言，我首先想法的是一种模拟栈的玩法：
当扫描到R的时候，想象进栈，也就是top ++
当扫描到L的时候，想象出渣，也就是top --
当top又等于栈底(栈底规定为0吧)的时候，就是找到了一组符合要求的了

下面进入解法二，老老实实学贪心了，我现在也不会证明，先模仿宫水大大的吧，需要的友友们也可以直接看他的证明
宫水三叶の相信科学系列】归纳法证明从「最小分割点」进行分割可以得到最优解
先模拟出两种选择，一种局部最优，一种不是。

① 证明起始时（第一次分割）将「从 b 分割点将 s 断开」调整为「从 a 分割点将 s 断开」结果不会变差：

① 从 b点首次分割调整为从 a 点首次分割，两种分割形式分割点两端仍为合法 LR 子串，因此不会从有解变成无解；
② 从 b 分割后的剩余部分长度小于从 a 分割后的剩余部分，同时由 b 分割后的剩余部分会被由 a 分割后的剩余部分所严格覆盖，因此「对 a 分割的剩余部分再分割所得的子串数量」至少 与「从 b 点分割的剩余部分再分割所得的子串数量」相等（不会变少）。
到这里为止，证明了对于首次分割，将任意合格分割点调整为最小分割点，结果不会变得更差（当 a < b 时还会更好）。
继续使用归纳来模拟其他剩余合格LR字串，得到的结果也是一样的，因此，就证明了只要每一次都从最小分割点进行分割，就可以得到最优解

🌻参考代码(C++版本)

解法①——常规模拟

class Solution {
public:
    int balancedStringSplit(string s) {
        //扫一遍？
        int len = s.size();
        int top= 0,ans = 0;
        for(int i = 0; i < len;i++)
        {
            if(s[i] == 'R') top++;
            if(s[i] == 'L') top--;
            if(top == 0) ans ++;
        }

        return ans;
    }
};

解法② —— 贪心

class Solution {
public:
    int balancedStringSplit(string s) {
        int len = s.size();
        int ans = 0;
        for(int i = 0; i < len;)
        {
            //其实本质也就是我模拟的代码，只是我模拟的时候就根据生活经验来的
            int j = i+1;
            //遇到R就标记-1，遇到L就标记+1
            int flag = (s[i] == 'L' ? 1 : -1);
            while(j < len && flag != 0)
                flag += (s[j++] == 'L'? 1 : -1);
            
            //匹配出一组0了，也即是找到局部最优了，调整起点，统计结果
            i = j;
            ans ++;
        }
        return ans;
    }
};

第二题 1827. 最少 *** 作使数组递增 💒题目描述

原题传送门

🌟解题报告

题目的意思是求解需要变换多少次，使数组中的每一个元素要比前一个元素大1，至于证明，现在能力微弱，后续补上吧

🌻参考代码(C++版本)

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int len = nums.size();
        int ans = 0;
        if(len == 1) return ans;

        for(int i = 1; i < len;i++)
        {
            if(nums[i-1] < nums[i]) continue;
            else 
            {
                //统计前后相邻的两个数字需要加几次1才能够实现前一个比后一个大1
                int tmp = nums[i-1] + 1 - nums[i];
                ans += tmp;
                //更新较大数字的值
                nums[i] = nums[i-1]+1;
            }
        }
        return ans;
    }
};

第三题 2144. 打折购买糖果的最小开销 💒题目描述

原题传送门

🌟解题报告

因为题目的要求是送咱的糖果只能是小于等于购买的两个糖果价格的 较小值 ，那么我们可以考虑降序排序，这种方便拿价格较大的两个糖果。
买两个，送一个，其实就可以看做是三个一组，比如拿样例来说，[3，2，1]的降序排序，买3和2 ，送1 ，那么这三个一组中，数组索引是2的糖果就送了，其他的样例也可以这种理解。
贪心的题，能够想出来吧，想证明了，还缺火候

🌻参考代码(C++版本)

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        int len = cost.size();
        int ans = 0;
        if(len == 1) return cost[0];
        if(len == 2) return cost[0]+cost[1];

        //三个一组，降序排序，拿到大的，两个，最后一个就可以送了
        sort(cost.begin(),cost.end(),greater<int>());
        for(int i = 0; i < len;i++)
            if(i % 3 == 2) continue;
            else ans += cost[i];

        return ans;

    }
};

第四题 1400. 构造 K 个回文字符串

哈希表(可用数组模拟，可用STL吧)+模拟

💒题目描述

原题传送门

🌟解题报告

这个感觉更像是一个观察规律的题吧，因为题目要咱们构造，没有让咱们找出回文串，那么难度其实就降低很多了。

首先，出现频率是偶数的字母，是一定可以形成回文串的，它怎么放都可以。
但是出现频率是奇数的字母，它是没法匹配的，所以必须放在回文串的中间。
那么对于每一个出现频率为奇数的字母，都需要单独一个回文串来容纳它。我们只要保证，题目要求构造的回文串的数目k，比出现频率为奇数的字母的个数num大。

🌻参考代码(C++版本)

class Solution {
public:
    bool canConstruct(string s, int k) {
        int len = s.size();
        if(len < k) return false;
        if(len == k) return true;

        //这个题是让咱们构造
        //看到字符串的东西了，条件反射的去做映射吧
        int cnt[26];
        memset(cnt,0,sizeof(cnt));
        for(int i = 0; i < len;i++)
            cnt[s[i]-'a'] ++;

        int num = 0;
        for(int i = 0; i < 26;i++)
            //记录出现次数为奇数的字母
            if(cnt[i] % 2 == 1) num++;
        
        return num <= k;
    }
};