【贪心算法】贪心算法七

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.整数替换

题目链接： 397. 整数替换

题目描述：

算法原理：

解法一：模拟（递归 + 记忆化搜索）

假设n = 18，我们要干的事情是把18变成1最小的步数。因为18是一个偶数只能除2变成9，拿到9这个数字，要干的其实也是一件相同的事情，要把9变成1最小的步数。

此时这里就出现了重复的子问题，大问题是18变成1的最小步数，18/2=9后就从了9变成1的最小步数的相同问题。因此我们可以把重复子问题拿到设计出函数头
int dfs(int n) 给一个整数n返回n变成1的最小步数。函数体 其实就是题目给的，如果n是偶数/2，如果n是奇数要么+1，要么-1我们求得是最小步数所以是 min(dfs(n-1)，dfs(n+1))，递归出口 当 n == 1是之间返回0就行了。

在递归过程中发现大量重复，就可以用记忆化搜索，建一个数组，但是这道题的数据范围是1 <= n <= 2^31 - 1，我们要开这么大的空间肯定不行，因此搞一个hash<int,int> 第一个参数对应数字n，第二个参数对应这个数变成1的最小步数。

class Solution {
    unordered_map<int,int> hash;
public:
    int integerReplacement(int n) {

        return dfs(n);
    }


    // 递归
    int dfs(long long n) // 细节问题 数据范围1 <= n <= 2^31 - 1 加1会越界
    {
        if(n == 1)
        {
            return 0;
        }

        if(n % 2 == 0) // 如果是偶数 
        {
            return 1 + dfs(n / 2);
        }
        else
        {
            return 1 + min(dfs(n - 1), dfs(n + 1));
        }
    }

    // 记忆化搜索
    int dfs(long long n)
    {
        if(hash.count(n))
        {
            return hash[n];
        }

        if(n == 1)
        {
            hash[1] = 0;
            return hash[1];
        }

        if(n % 2 == 0)
        {
            hash[n] = 1 + dfs(n / 2);
            return hash[n];
        }
        else
        {
            hash[n] = 1 + min(dfs(n - 1), dfs(n + 1));
            return hash[n];
        }
    }
};

解法二：贪心

补充知识：二进制

1. 偶数：二进制表示中最后一位是 0
2. 奇数：二进制表示中最后一位是 1
3. /2 操作：二进制表示中统一右移一位

我们这里研究的都是整数。
前两个可以自己举例看看。我们看最后一个

接下来想我们的贪心策略：

如果n是偶数没法贪，只能执行/2操作

是奇数就可以贪，要么执行+1，要么执行-1操作。
在模拟解法我们就是试试+1操作和-1操作看谁最小，但是如果在没有试之前就已经知道是+1好还是-1好，直接让奇数沿着较好的选择走，就可以舍去一个选择，那我们的时间复杂度会变得更优。

所以我们的贪心就是判断是+1好还是-1好。

如何判断？分情况讨论：

奇数的二进制最后一位是0，所以我们可以把奇数分为两大类

第一类：前面二进制位是 …，最后两个二进制位是 01

第二类：前面二进制位是 …，最后两个二进制位是 11

其中第一类我们默认 n > 1，也就是说 … 有1，如果没有1的话就是00…01了，直接返回即可。第二类默认 n > 3。

如果是 …01，接下来要么执行+1操作，要么执行-1操作。 +1操作会变成 …10，-1操作会变成 …00，那到底那个操作好呢? +1和-1操作都会变成偶数，偶数只能执行/2操作。假设…01是 …10001，执行+1操作会变成10010在执行/2操作会变成1001，执行-1操作会变成10000在执行/2操作会变成1000。这个时候就可以看出那个操作好了，肯定是-1操作好，因为1000我们可以一直/2操作尽快得到1，1001还需要在+1和-1操作在/2操作。

所以是奇数二进制最后两位是01，就执行-1操作，然后/2操作，会比较快得到1。

如果是 …11，接下来也是要么执行+1操作，要么执行-1操作，分析过程和上面一样。

但是n > 3这里有一个意外，当 n = 3的时候，我们需要特殊讨论，n = 3，二进制位前面都是0，后面虽然也是11。但是这里我们执行-1操作得到…10，然后在执行/2操作，直接就变成1了。这个和选择是不一样的。如果执行+1操作就会多一步/2操作。

我们这个贪心不用证明，分类讨论过程本身就是对这个贪心的证明。

那如何写代码呢？

如何判断二进制最后两位是01还是11呢？
拿n%4就可以了，因为n是奇数%4只能得到1和3，如果是1就是01情况，如果是3就是11情况。

class Solution {
    unordered_map<int,int> hash;
public:
    int integerReplacement(int n) {

        int ret = 0;
        while(n > 1)
        {
            if(n % 2 == 0)
            {
                n /= 2;
                ++ret;
            }
            else
            {
                if(n == 3)
                {
                    ret += 2;
                    n = 1;
                }
                else if(n % 4 == 1)
                {
                    n = n / 2;
                    ret += 2;
                }
                else
                {
                    n = n / 2 + 1;
                    ret += 2;
                }
            }
        }
        return ret;
    }
};

2.俄罗斯套娃信封问题

题目链接： 354. 俄罗斯套娃信封问题

题目分析：

给一个二维数组，每一行表示信封的宽度和高度，当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）

算法原理：

解法一：常规解法（通用解法）-> 动态规划

先对数组排序，如果不排序的话，去找某一个信封能去套谁的时候，既要去它左边找找，也要去右边找找。说白了就是要变量数组一遍，才能去确定这个信封能去套谁。

但是如果我们把这个数组按照左端点排序后，此时在去确定一个信封能去套谁的时候，仅需去左边看看就行了。因为如果能套必须满足左大于左，右大于右，我们已经按左端点排好序，右边的左都比当前的左大，因此不用考虑右边。

此时我们的最长套娃序列特别像之前的最长递增子序列问题，最长递增子序列是在原始的数组中挑选一些数出来形成递增的序列，问最长的长度是多少。我们这里是在一些信封里面挑一些信封出来使它能形成一个套娃序列，问最长的套娃序列是多少。这个问题就和最长递增子序列一模一样。无非最长子序列是在一个个数中挑，我们这里是在一个个信封里面挑。

1.状态表示

dp[i] 表示：以 i 位置的信封为结尾的所有套娃序列中，最长套娃序列的长度

2.状态转移方程

根据最近一步，划分情况

i 位置本身就是套娃序列 ，长度是1

以 i 位置为结尾的最长套娃长度，那么就去 0 ~ i - 1 这段区间遍历一遍找到一个j位置，只要发现 i 信封 能套到 j 信封 外面，那此时用dp[j]在加上 i 这一个信封就是以 i 位置的信封为结尾套娃序列的长度。找到 0 ~ i -1 区间所有能套的 dp[j] + 1 的最大值，就是 i 位置的信封为结尾的所有套娃序列中，最长套娃序列的长度。

3初始化

数组初始为1，就可以不用考虑为的1情况

4.填表顺序

从左往右

5.返回值

dp[i] 表示：以 i 位置的信封为结尾的所有套娃序列中，最长套娃序列的长度。我们要的是整个区间最长套娃序列的长度，所以返回dp表中的最大值。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& e) {

        // 动态规划
        sort(e.begin(), e.end());

        int n = e.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0 ; j < i; ++j)
            {
                if(e[j][0] < e[i][0] && e[j][1] < e[i][1])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

因为这道题的数据量太大我们的动规会超时，但是动规是解决这类题的常规方法。这道题不行不代表相同类型的题不行，比如1263. 推箱子这道题用动规是可以通过的。

解法二：重写排序 + 贪心 + 二分

动态超时了，肯定得用贪心 + 二分了，但是为什么多一个重写排序呢?

如果我们仅仅只是按照左端点排序，接下来用贪心和二分，你会发现我们要分类讨论，原因就是之前研究的最长递增子序列只有一个限定条件 只在一堆数中去挑，然后贪心保留是长度为1，长度为2 … 的最后一个元素的最小值，比如长度为2：5，现在来了一个3，我们可以把5干掉，保留3，原因是能跟在5的后面更能跟在3的后面。但是我们这道题给的是一个个区间，有的时候我们并不能直接删除，有的时候是把之前结果保留而把新来的给删除。虽然能做但是需要分类讨论比较麻烦。所以我们先重写排序在贪心和二分。

下面我们给的是左端点都是不同的排完序后的样子，如果左端点不一样，我们其实可以把左端点删去。原因就是左端点都不一样，我们还按照左端点从小到大排好序了，那就相当于前面的是严格递增，所以不考虑前边信封左端点是多少。那不就变成了在 3、1、8、12、3中挑一个最长递增子序列了嘛。

但是我们这里是可能有重复的左端点的，假设有重复的话，我们排完序是下面这种情况，如果我们继续不看左端点，我们可能会挑出来4、6、7、9长度为4的序列，但是这并不符合，原因就是我们的左必须大于左才能套。

那如何避免这种情况呢？很简单当左端点相同的时候，我们就按照右端点从大到小排序。当继续不看左端点，我们在挑7的时候绝对不要9，因为当左边相同的时候右边是按照从大到小排的，同理挑4绝对不会考虑前三个。

重写排序后就完完全全变成只有一个限制的最长递增序列了。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& e) {

        // 重写排序 + 贪心 + 二分
        sort(e.begin(), e.end(),[&](vector<int>& e1, vector<int>& e2)
        {
            return e1[0] != e2[0] ? e1[0] < e2[0] : e1[1] > e2[1];
        });
        
		// 贪心 + 二分
        vector<int> ret;
        ret.push_back(e[0][1]);
        int n = e.size();
        for(int i = 1; i < n; ++i)
        {
            if(e[i][1] > ret.back())
            {
                ret.push_back(e[i][1]);
            }
            else
            {
                int left = 0, right = ret.size() - 1;
                while(left < right)
                {
                    int mid = (left + right) >> 1;
                    if(ret[mid] < e[i][1])
                        left = mid + 1;
                    else
                        right = mid;
                }
                ret[left] = e[i][1];
            }
        }
        return ret.size();

    }
};

3.可被三整除的最大和

题目链接： 1262. 可被三整除的最大和

题目分析：

这道题的意思是给一个数组，在这个数组中挑一些数使这些数的和能被3整除，并且这些挑的这些数的和是最大的。

算法原理：

解法一：正难则反 + 贪心 + 分类讨论

题目要在数组中挑一些数的和能被3整除并且和是最大的，我们可以直接把整个数组中的数全部挑出来，%3正好等于0，那我就不用考虑了，如果%3不等于，那我在全部挑选的基础上删一些数就可以了。

先把所有的数累加在一起，根据累加和，删除一些数

假设所有数的和是sum，接下来就分类讨论：

1. sum % 3 == 0

直接返回sum

2. sum % 3 == 1

我们定义一些数，x ：标记 % 3 == 1 的数，y ： 标记 % 3 == 2 的数

如果%3 == 1，必定有下面几种情况：

第一种情况：

1. 存在一个%3 == 1 的数，剩下所有数的和%3 == 0

2. 存在四个%3 == 1 的数，剩下所有数的和%3 == 0，其实可以把三个%3 == 1的数归到剩下所有数的和%3 == 0里面

3. 存在七个%3 == 1 的数，剩下所有数的和%3 == 0，也可以把六个%3 == 1的数归到剩下所有数的和%3 == 0里面

剩下的也不用枚举了，我们只用考虑第一种情况就行了，原因就是不管这里有多少种情况，我们仅需删去第一种情况的x1就可以让剩下的数的和%3==0。

那么贪心的地方来了，要删除怎样的x1，肯定是最小的x1。因为我们想让sum的和最大。

第二种情况：

存在两个%3 == 2 的数 y1，y2 (2 + 2 = 4 % 3 = 1)，或者和上面一样存在y1、y2、y3、y4…，但是和上面一样我们仅需第一种情况就行了，此时删y1，y2。此时贪的地方来了，为了使sum最大，删y1和y2，一个是最小的，一个是次小的。

因为sum %3 == 1 会分为这两种情况，因此我们取这两种情况的最大值。

3. sum % 3 == 2

也是两种情况，要么存在一个y1 使sum % 3 == 2，要么存在一个x1，一个x2 使 sum % 3 == 2。我们依旧取两种情况的最大值。

如何求一堆数中的最小值以及次小值？
同理求一堆数中的最大值和次大值也是一样的求法。

第一种方法：sort排序 O(nlogn)

第二种方法：分类讨论

先定义两个数x1、x2，然后初始化为无穷大。然后从左到右遍历根据新来的x，分类讨论：

1. x < x1
   
2. x1 < x < x2

3. x > x2

并不影响最小和次小的。所以不用考虑

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {

        const int INF = 0x3f3f3f3f;
        int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;
        for(auto x: nums)
        {
            sum += x;

            if(x % 3 == 1)
            {
                if(x < x1) x2 = x1, x1 = x;
                else if(x < x2) x2 = x;
            }
            else if(x % 3 == 2)
            {
                if(x < y1) y2 = y1, y1 = x;
                else if(x < y2) y2 = x;
            }    
        }

        //分类讨论
        if(sum % 3 == 0) return sum;
        else if(sum % 3 == 1) return max(sum - x1, sum - y1 - y2);
        else return max(sum - y1, sum - x1 - x2);

    }
};

解法二：动态规划

从一堆数中选取一些数，使这些数的和能被3整除。其实这道题就是一个01背包问题。

1.状态表示

dp[i][j] 表示：从前 i 个数中选取一些数，这些数的和模3等于 j (0 <= j < 3) 时，最大值的和是多少

2.状态转移方程

根据最后一个位置，划分情况

不选 i 位置这个数，那就去 0 ~ i - 1 区间去选一些数的和模3等于j 时最大值的和，正好是 dp[i-1][j]

选 i 之后，还是去 0 ~ i - 1 区间去选一些数的和模3，但是此时就不是直接去找和模3等于 j 的了，因为 i 位置这个数 nums[i] % 3 会等于0、1、2 中的任意一个数，那么去 0 ~ i - 1区间去找和模3等于 的 j 也要随 nums[i] % 3 的改变而去改变。

以nums[i]%3 == 1为例，如果求的dp[i][0]，那就要去 0 ~ i -1 区间去找和%3 但是 j 为 2 的情况，因为这个和 加上 nums[i] 才会有 和 % 3 等于 0，比如 nums[i] 是 1，去 0 ~ i - 1找的和是2，2 % 3 = 2， （2 + 1）% 3 == 0 。同理求dp[i][1]，dp[i][2]也是一样。

我们要求的是最大和，因此取两种情况的最大值

3.初始化

1. 多开一行，列开3个
2. 里面的值要保证后序的填表是正确的
3. 下标的映射关系

第一行为空表示没有数可以选，此时和%3等于0，不选就行了，直接就是0，第一格填0，没有数可以选还要和%3 == 1 和 2 是不可能存在的，可以给这两个位置得值位-1表示不存在得情况，但是我们下面写代码要判断一下 不等于-1 才能要这个状态，但是因为我们求得又是最大值，我们可以使它俩足够小就行了这样就可以不用去判断了，也不会影响填表。因此可以给-0x3f3f3f3f。

第一列除了第一格下面的不用初始化。直接放在填表里面就行了。

4.填表顺序

从上往下，从左往右

5.返回值

dp[i][j] 表示：从前 i 个数中选取一些数，这些数的和模3等于 j (0 <= j < 3) 时，最大值的和是多少，我们要得使从所有数种选一些数，这些数得和%3 == 0 最大值是多少，因此返回的是 dp[n][0]

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        // 动态规划
        const int INF = 0x3f3f3f3f;
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(3, -INF));
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < 3; ++j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - nums[i -1] % 3 + 3) % 3] + nums[i - 1]);
        return dp[n][0];
    }
};

优化：利用滚动数组做优化

背包问题哪里我们使用的是一个数组充当滚动数组，但是这里我们要用两个数组充当滚动数组，因为%3可能会等于0、1、2，那在一个数组中更新下一行的值及其可能会覆盖j 为 0 、1、2的任何位置，比如 填 j = 0，会用到 j = 1, 但是填 j 也可能会用到 j = 0，但是前面已经把 j = 0 更新了找不到之前的值了，所以这里我们用两个数组充当滚动数组，就不担心这个问题了。并且如果是两个数组充当滚动数组，01背包优化填表顺序从左往右，从右往左都行。

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {

        // 利用滚动数组优化(二个数组)
        const int INF = 0x3f3f3f3f;
        int n = nums.size();
        vector<int> dp(3, -INF);
        dp[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            vector<int> ndp(3);
            for(int j = 0; j < 3; ++j)
                ndp[j] = max(dp[j], dp[(j - nums[i -1] % 3 + 3) % 3] + nums[i - 1]);
            dp = move(ndp);
        }
        return dp[0];
    }
};

4.距离相等的条形码

题目链接： 1054. 距离相等的条形码

题目分析：

算法原理：

解法：贪心 + 模拟

我们这道题就是让我们把这些数重新排列一下，相邻的两个不相同。此时我们这样考虑问题，我们有9个格子，把给的数放到格子里让相邻的两个不相同就可以了。此时我们可以这样处理，把相同的数看出一批数，每次摆放一批数，摆放的时候仅需让这些相同的数不相邻就可以了。如何做到不相邻特别简单，每次摆的时候隔一个格子。这样绝对会让相同的数不相邻。

我们先在偶数位上摆，摆完后在摆奇数位。此时摆完后会发现相邻两个数是不相同的。

贪心策略：

1. 每次处理一批相同的数
2. 摆放的时候，每次隔一个格子

但是这个策略还有一个问题，可能会有把相同的数放在相邻的位置，这里我们还要多加一个限定条件。

3. 先处理出现次数最多的那个数，剩下的数的处理顺序无所谓
   

证明：

题目一定有解，我们可以得到一个性质，假设有n个数，我们可以分成 (n+1)/2 个组。如果题目一定有解，我们可以证明的是：出现次数最多的那个数，不超过(n+1)/2个。

假设出现次数最多的那个数，超过(n+1)/2个。那此时去摆这些数的时候必定会有一组里面出现相同的数。但是题目一定有解，因此出现次数最多的那个数，不超过(n+1)/2个。

我们的策略是先处理出现次数最多的那个数，剩下的数的处理顺序无所谓。

第一种情况：出现次数最多的数，正好出现 （n + 1）/2。我们先处理最多的那个数，剩下的数无论怎么放都不会相邻。

第二种情况：出现次数最多的数，小于（n + 1）/ 2。此时我们也可以证明相同的数不相邻，因为如果相邻必定是后面的数x出现次数还要比o还要多，但是这种情况绝对不会存在。因为我们的前提就是出现次数最多的数，小于（n + 1）/ 2，那就是x就是出现次数最多的数。但是我们是优先处理出现次数最多的那次数。所以如果是先填o，x绝对不可能相邻。

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& b) {
        // 统计每个数出现的频次
        unordered_map<int,int> hash;
        int maxVal = 0, maxCount = 0;
        for(auto x : b)
        {
            if(maxCount < ++hash[x])
            {
                maxCount = hash[x];
                maxVal = x;
            }
        }

        // 先处理出现次数最多的那个数
        int n = b.size();
        vector<int> ret(n);
        int index = 0;
        for(int i = 0; i < maxCount; ++i)
        {
            ret[index] = maxVal;
            index += 2; 
        }
        
        //处理剩下的数
        hash.erase(maxVal);
        for(auto& [x, y] : hash)
        {
            for(int i = 0; i < y; ++i)
            {
                if(index >= n) index = 1;
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
    }
};

5.重构字符串

题目链接： 767. 重构字符串

题目分析：

算法原理：

解法：贪心 + 模拟

1. 每次处理一批相同的字符
2. 摆放的时候，隔一个位置放一个字符
3. 优先处理出现次数最多的那一个字符

这道题并没有告诉我们一定会有排序，所以我们要先判断一下是否有排列，方法很简单，出现次数最多的字符个数不超过（n+1）/2就行了。

class Solution {
public:
    string reorganizeString(string s) {

        // 统计每个字符出现的频次
        int hash[26] = { 0 };
        char maxChar = ' '; int maxCount = 0;
        for(auto ch : s)
        {
            if(maxCount < ++hash[ch - 'a'])
            {
                maxCount = hash[ch - 'a'];
                maxChar = ch;
            }
        }

        // 先判断⼀下
        int n = s.size();
        if(maxCount > ((n + 1) / 2)) return "";

        // 先处理出现次数最多的那个字符
        string ret(n,' ');
        int index = 0;
        for(int i = 0; i < maxCount; ++i)
        {
            ret[index] = maxChar;
            index += 2;
        }

        //处理剩下的数
        hash[maxChar - 'a'] = 0;
        for(int i = 0; i < 26; ++i)
        {
            for(int j = 0; j < hash[i]; ++j)
            {
                if(index >= n) index = 1;
                ret[index] = 'a' + i;
                index += 2;
            }
        } 
        return ret;

    }
};