贪心算法五
> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：了解什么是贪心算法，并且掌握贪心算法。
> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!
> 专栏选自：贪心算法_დ旧言~的博客-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;
else
left = 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);
else
return 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;
}
};三、结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
