贪心算法五

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

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

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

专栏选自：

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

一、算法讲解

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

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的局部最优解合成原来问题的一个解。 如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。 动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

二、算法习题

2.1、第一题

题目链接：[397 整数替换 - 力扣（LeetCode）]( replacement/description/ “397. 整数替换 - 力扣（LeetCode）”) 题目描述： 算法思路： 对于偶数： 只能执⾏除 2 操作，没有什么分析的； 对于奇数：

1. 当 n== 1 的时候，不⽤执⾏任何操作；
2. 当 n == 3 的时候，变成 1 的最优操作数是 2 ；
3. 当 n > 1 && n % 3 == 1 的时候，那么它的⼆进制表⽰是 ……01 ，最优的⽅式应该选择 -1 ，这样就可以把末尾的 1 ⼲掉，接下来执⾏除法操作，能够更快的变成 1 ；
4. 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）]( envelopes/description/ “354. 俄罗斯套娃信封问题 - 力扣（LeetCode）”) 题目描述： 算法思路： 当我们把整个信封按照「下⾯的规则」排序之后：

1. 左端点不同的时候：按照「左端点从⼩到⼤」排序；
2. 左端点相同的时候：按照「右端点从⼤到⼩」排序
3. 我们发现，问题就变成了仅考虑信封的「右端点」，完完全全的变成的「最⻓上升⼦序列」的模型。那么我们就可以⽤「贪⼼ + ⼆分」优化我们的算法。 代码呈现： class Solution { public: int maxEnvelopes(vector>& e) { // 解法⼆：重写排序 + 贪⼼ + ⼆分 sort(e.begin(), e.end(), [&](const vector& v1, const vector& v2) { return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1]; }); // 贪⼼ + ⼆分 vector 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; else left = mid + 1; } ret[left] = b; } } return ret.size(); } };

2.3、第三题

题目链接：[1262 可被三整除的最大和 - 力扣（LeetCode）]( three/description/ “1262. 可被三整除的最大和 - 力扣（LeetCode）”) 题目描述： 算法思路： 正难则反： 我们可以先把所有的数累加在⼀起，然后根据累加和的结果，贪⼼的删除⼀些数。 分类讨论： 设累加和为 sum ，⽤ x 标记 %3 == 1 的数，⽤ y 标记 % 3 == 2 的数。 那么根据 sum 的余数，可以分为下⾯三种情况：

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

2.4、第四题

题目链接： 题目描述： 算法思路：

• 每次处理⼀批相同的数字，往 n 个空⾥⾯摆放；
• 每次摆放的时候，隔⼀个格⼦摆放⼀个数；
• 优先处理出现次数最多的那个数。 代码呈现： class Solution { public: vector rearrangeBarcodes(vector& b) { unordered_map hash; // 统计每个数出现的频次 int maxVal = 0, maxCount = 0; for (auto x : b) { if (maxCount < ++hash[x]) { maxCount = hash[x]; maxVal = x; } } int n = b.size(); vector 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、第五题

题目链接： 题目描述： 算法思路： 遇上面解法一致。 代码呈现： 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; } };

三、结束语****

今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。