贪心算法五

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是算法>贪心算法，并且掌握算法>贪心算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：算法>贪心算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

算法>贪心算法的定义：

算法>贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。算法>贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的局部最优解合成原来问题的一个解。

如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。算法>贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。

动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而算法>贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于算法>贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

二、算法习题

2.1、第一题

题目链接：397. 整数替换 - 力扣（LeetCode）

题目描述：

算法思路：

对于偶数：只能执⾏除 2 操作，没有什么分析的；

对于奇数：

当 n== 1 的时候，不⽤执⾏任何操作；
当 n == 3 的时候，变成 1 的最优操作数是 2 ；
当 n > 1 && n % 3 == 1 的时候，那么它的⼆进制表⽰是 ......01 ，最优的⽅式应该选择 -1 ，这样就可以把末尾的 1 ⼲掉，接下来执⾏除法操作，能够更快的变成 1 ；
iv. 当 n > 3 && n % 3 == 3 的时候，那么它的⼆进制表⽰是 ......11 ，此时最优的策略应该是 +1 ，这样可以把⼀堆连续的 1 转换成 0 ，更快的变成 1 。

代码呈现：

class Solution {
public:int integerReplacement(int n) {int ret = 0;while (n > 1) {// 分类讨论if (n % 2 == 0) {ret++;n /= 2;} else {if (n == 3) {ret += 2;n = 1;} else if (n % 4 == 1) {ret += 2;n /= 2;} else {ret += 2;n = n / 2 + 1;}}}return ret;}
};

2.2、第二题

题目链接：354. 俄罗斯套娃信封问题 - 力扣（LeetCode）

题目描述：

算法思路：

当我们把整个信封按照「下⾯的规则」排序之后：

左端点不同的时候：按照「左端点从⼩到⼤」排序；
左端点相同的时候：按照「右端点从⼤到⼩」排序
我们发现，问题就变成了仅考虑信封的「右端点」，完完全全的变成的「最⻓上升⼦序列」的模型。那么我们就可以⽤「贪⼼ + ⼆分」优化我们的算法。

代码呈现：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& e) {// 解法⼆：重写排序 + 贪⼼ + ⼆分sort(e.begin(), e.end(),[&](const vector<int>& v1, const vector<int>& v2) {return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];});// 贪⼼ + ⼆分vector<int> ret;ret.push_back(e[0][1]);for (int i = 1; i < e.size(); i++) {int b = e[i][1];if (b > ret.back()) {ret.push_back(b);} else {int left = 0, right = ret.size() - 1;while (left < right) {int mid = (left + right) / 2;if (ret[mid] >= b)right = mid;elseleft = mid + 1;}ret[left] = b;}}return ret.size();}
};

2.3、第三题

题目链接：1262. 可被三整除的最大和 - 力扣（LeetCode）

题目描述：

算法思路：

正难则反：

我们可以先把所有的数累加在⼀起，然后根据累加和的结果，贪⼼的删除⼀些数。

分类讨论：设累加和为 sum ，⽤ x 标记 %3 == 1 的数，⽤ y 标记 % 3 == 2 的数。

那么根据 sum 的余数，可以分为下⾯三种情况：

sum % 3 == 0 ，此时所有元素的和就是满⾜要求的，那么我们⼀个也不⽤删除；
sum % 3 == 1 ，此时数组中要么存在⼀个 x ，要么存在两个 y 。因为我们要的是最⼤值，所以应该选择 x 中最⼩的那么数，记为 x1 ，或者是 y 中最⼩以及次⼩的两个数，记为 y1, y2 。那么，我们应该选择两种情况下的最⼤值： max(sum - x1, sum - y1 - y2) ；
c. sum % 3 == 2 ，此时数组中要么存在⼀个 y ，要么存在两个 x 。因为我们要的是最⼤值，所以应该选择 y 中最⼩的那么数，记为 y1 ，或者是 x 中最⼩以及次⼩的两个数，记为 x1, x2 。那么，我们应该选择两种情况下的最⼤值： max(sum - y1, sum - x1 - 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);elsereturn max(sum - y1, sum - x1 - x2);}
};

2.4、第四题

题目链接：1054. 距离相等的条形码 - 力扣（LeetCode）

题目描述：

算法思路：

每次处理⼀批相同的数字，往 n 个空⾥⾯摆放；
每次摆放的时候，隔⼀个格⼦摆放⼀个数；
优先处理出现次数最多的那个数。

代码呈现：

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;}
};

2.5、第五题

题目链接：767. 重构字符串 - 力扣（LeetCode）

题目描述：

算法思路：

遇上面解法一致。

代码呈现：

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']) {maxChar = ch;maxCount = hash[ch - 'a'];}}// 先判断⼀下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;}
};