贪心算法三

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

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

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

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

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

一、算法讲解

贪心算法的定义：

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

解题的一般步骤是：

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

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

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

二、算法习题

---

2.1、第一题

题目链接：674. 最长连续递增序列 - 力扣（LeetCode）

题目描述：

算法思路：

找到以某个位置为起点的最⻓连续递增序列之后（设这个序列的末尾为 j 位置），接下来直接
以 j + 1 的位置为起点寻找下⼀个最⻓连续递增序列。

代码呈现：

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int ret = 0, n = nums.size();for (int i = 0; i < n;) {int j = i + 1;// 找到递增区间的末端while (j < n && nums[j] > nums[j - 1])j++;ret = max(ret, j - i);i = j; // 直接在循环中更新下⼀个位置的起点}return ret;}
};

2.2、第二题

题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）

题目描述：

算法思路：

由于只能交易⼀次，所以对于某⼀个位置 i ，要想获得最⼤利润，仅需知道前⾯所有元素的最⼩
值。然后在最⼩值的位置「买⼊」股票，在当前位置「卖出」股票即可。

代码呈现：

class Solution {
public:int maxProfit(vector<int>& prices) {int ret = 0; // 记录最终结果for (int i = 0, prevMin = INT_MAX; i < prices.size(); i++) {ret = max(ret, prices[i] - prevMin); // 先更新结果prevMin = min(prevMin, prices[i]);   // 再更新最⼩值}return ret;}
};

2.3、第三题

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

题目描述：

算法思路：

由于可以进⾏⽆限次交易，所以只要是⼀个「上升区域」，我们就把利润拿到⼿就好了。

代码呈现：

class Solution {
public:int maxProfit(vector<int>& prices) {// 实现⽅式⼆：拆分成⼀天⼀天int ret = 0;for (int i = 1; i < prices.size(); i++) {if (prices[i] > prices[i - 1])ret += prices[i] - prices[i - 1];}return ret;}
};

2.4、第四题

题目链接：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

题目描述：

算法思路：分情况讨论，设整个数组中负数的个数为 m 个

a. m > k ：把前 k ⼩负数，全部变成正数；

b. m == k ：把所有的负数全部转化成正数；

c. m < k ：

• 先把所有的负数变成正数；
• 然后根据 k - m 的奇偶分情况讨论：
• 1. 如果是偶数，直接忽略；
  2. 如果是奇数，挑选当前数组中最⼩的数，变成负数

代码呈现：

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0, minElem = INT_MAX, n = nums.size();for (auto x : nums) {if (x < 0)m++;minElem = min(minElem, abs(x)); // 求绝对值最⼩的那个数}// 分类讨论int ret = 0;if (m > k) {sort(nums.begin(), nums.end());for (int i = 0; i < k; i++) // 前 k ⼩个负数，变成正数{ret += -nums[i];}for (int i = k; i < n; i++) // 后⾯的数不变{ret += nums[i];}} else {// 把所有的负数变成正数for (auto x : nums)ret += abs(x);if ((k - m) % 2) // 判断是否处理最⼩的正数{ret -= minElem * 2;}}return ret;}
};

2.5、第五题

题目链接：2418. 按身高排序 - 力扣（LeetCode）

题目描述：

算法思路：

• 我们不能直接按照 i 位置对应的 heights 来排序，因为排序过程是会移动元素的，但是names 内的元素是不会移动的。
• 由题意可知， names 数组和 heights 数组的下标是⼀⼀对应的，因此我们可以重新创建出来⼀个下标数组，将这个下标数组按照 heights[i] 的⼤⼩排序。
• 那么，当下标数组排完序之后，⾥⾯的顺序就相当于 heights 这个数组排完序之后的下标。之后通过排序后的下标，依次找到原来的 name ，完成对名字的排序。

代码呈现：

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {// 1. 创建⼀个下标数组int n = names.size();vector<int> index(n);for (int i = 0; i < n; i++)index[i] = i;// 2. 对下标进⾏排序sort(index.begin(), index.end(),[&](int i, int j) { return heights[i] > heights[j]; });// 3. 提取结果vector<string> ret;for (int i : index) {ret.push_back(names[i]);}return ret;}
};

2.6、第六题

题目链接：870. 优势洗牌 - 力扣（LeetCode）

题目描述：

算法思路：

讲⼀下⽥忌赛⻢背后包含的博弈论和贪⼼策略：
⽥忌：下等⻢ 中等⻢ 上等⻢
⻬王：下等⻢ 中等⻢ 上等⻢

• a. ⽥忌的下等⻢ pk 不过⻬王的下等⻢，因此把这匹⻢丢去消耗⼀个⻬王的最强战⻢！
• b. 接下来选择中等⻢ pk ⻬王的下等⻢，勉强获胜；
• c. 最后⽤上等⻢ pk ⻬王的中等⻢，勉强获胜。

由此，我们可以得出⼀个最优的决策⽅式：

• a. 当⼰⽅此时最差的⽐不过对⾯最差的时候，让我⽅最差的去处理掉对⾯最好的（反正要输，不如去拖掉对⾯⼀个最强的）；
• b. 当⼰⽅此时
• c. 最差的能⽐得上对⾯最差的时候，就让两者⽐对下去（最差的都能获胜，为什么要输呢）。每次决策，都会使我⽅处于优势。

代码呈现：

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();// 1. 排序sort(nums1.begin(), nums1.end());vector<int> index2(n);for (int i = 0; i < n; i++)index2[i] = i;sort(index2.begin(), index2.end(),[&](int i, int j) { return nums2[i] < nums2[j]; });// 2. ⽥忌赛⻢vector<int> ret(n);int left = 0, right = n - 1;for (auto x : nums1) {if (x > nums2[index2[left]])ret[index2[left++]] = x;elseret[index2[right--]] = x;}return ret;}
};

三、结束语 

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