目录
今天我们将用 10 道题目来带各位更进一步地了解贪心算法
这一篇文章是这个系列的第二篇，如果对贪心是什么还不太了解的，或者想了解一下上一篇内容的同学可以点这个： 【算法学习计划】贪心算法（上）
（下文中的标题都是leedcode对应题目的链接）
leetcode 2418.按身高排序
这道题目其实说是贪心也不是，因为主要的逻辑就是简单排个序
但是难的点就在于，我们将身高数组从大到小排完序之后，和我们的名字数组对不上了
所以我们可以重写排序方法，这里我就直接用 lambda 表达式来写了，因为这是最方便的
然后最主要的是，我们可以用重写之后的排序方法对下标进行排序
是的，就是下标，我们搞一个下标数组，其实就是从 0~n 的数依次放进这个数组里面，然后按着身高数组的排序方法同时对下标数组进行排序，这样子我们就可以很直观地看到，几号下标的身高最高，这个下标对应到名字数组里面是谁我们也能知道
最后排完序之后，依次将最高的人的名字放进一个新的数组里面，返回即可
代码如下：
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights)
{
auto idea = [&](int a, int b){ return heights[a] > heights[b];};
int n = names.size();
vector<int> arr(n);
for(int i = 0; i < n; i++) arr[i] = i;
sort(arr.begin(), arr.end(), idea);
vector<string> ret;
for(auto e : arr) ret.push_back(names[e]);
return ret;
}
};leetcode 870.优势洗牌
这道题目如果我直接讲原理的话各位可能会有点懵，但如果我说这其实就是田忌赛马各位就明白了
首先，我们要让优势尽可能大的话，那么我们首先需要对两个数组进行一下排序（从小到大）
或许有人会说：这不对啊，哪能排序呢，排完不就找不到原来的顺序了吗，那我们不就没法返回了吗
但其实，我们可以直接使用第一题的解法，也就是，创建一个下标数组，用对nums2排序的方法对下标数组进行排序
最后，当我们将这道题目解决完之后，我们就可以对照着下标数组，知道nums2原本的顺序
然后就是我们田忌赛马的主逻辑了
首先，我们已经将两个数组都排完序了，那么我们接下来要做的，就是将两个数组一个一个对照，两个数组的第一个都是各自最小的，那如果nums1[0] < nums2[0]，那这就说明，nums1的第一个比不过nums2里面的全部元素，既然都比不过了，那我们就将第一个拿去和nums2里面的最后一个，也就是最大的那一个匹配
如果对应着的两个数，nums1的比nums2的大，那么我们就直接匹配即可
因为nums1前面的一定与更小的匹配或者比不过前面的和最大的匹配了，所以这个对应着的一定是当前情况中能和nums2该元素相匹配的最小的元素了
以上就是全部的算法原理了，接着就是具体做题时候需要注意的几个点
一个是，我们可以用双指针，一个left，一个right，用来代表我们要将nums1中匹配的数放在前面或者后面（放前面就是比得过，后面就是比不过）
然后我们还可以用up和down两个指针（其实和left、right一样就是两个int变量），分别代表nums1和nums2中的数
最后就是，别忘了我们还有一个数组下标，所以我们可以直接通过数组下标将nums1中的元素通过left放进要返回的数组中
代码如下：
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2)
{
int n = nums1.size();
vector<int> arr(n);
for(int i = 0; i < n; i++) arr[i] = i;
sort(arr.begin(), arr.end(), [&](int a, int b){return nums2[a] < nums2[b];});
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> ret(n);
int left = 0, right = n-1;
int up = 0, down = 0;
while(up < n)
if(nums1[up] <= nums2[down])
ret[arr[right--]] = nums1[up++];
else
{
ret[arr[left++]] = nums1[up++];
down++;
}
return ret;
}
};leetcode 409.最长回文串
这道题目其实，相当简单，首先我们回文序列都是两个两个的，但是在回文序列的最中间，还可以包含一个单个的，比如：abbac k cabba，所以我们可以创建一个数组，将所有的字符都放进该数组中，随后如果是奇数的，我们就将其减一并加上减完之后的偶数部分（因为多出来的那一个没有办法回文），如果是偶数，直接加上即可
最后我们判断一下，如果加完之后和原来数组的总大小不一样，那么就说明我们一定有奇数的部分，我们就可以从这些奇数部分挑一个出来放在最中间
所以如果不相等的话，我们就直接在加完之后的结果上面加一即可
代码如下：
class Solution {
public:
int longestPalindrome(string s)
{
int hash[127] = {0};
for(auto e : s) hash[e]++;
int ret = 0;
for(auto x : hash)
ret += x / 2 * 2 ;
return ret == s.size() ? ret : ret + 1;
}
};leetcode 942.增减字符串匹配
这道题目核心逻辑就一个，‘I’ 的话一定比前面小，那么我们可以直接贪，也就是放上最小的，那么肯定会比前面的小
如果是‘D’，那么要求这个比前面的大，那么我们直接放上最大的即可
然后我们就可以直接用left = 0，right = s.size() 来表示 0~n 的数
接着就是循环逻辑了，但是要注意的就是，我们循环到最后是 left == right 的，所以我们在最后的时候还需要再填上left或者right中的随便一个（因为此时两个相等）
代码如下：
class Solution {
public:
vector<int> diStringMatch(string s)
{
int left = 0, right = s.size();
vector<int> ret;
for(auto e : s)
{
if(e == 'I') ret.push_back(left++);
else ret.push_back(right--);
}
ret.push_back(left);
return ret;
}
};leetcode 455.分发饼干
其实这道题目就是上面那道优势洗牌的简易版，原理其实就是田忌赛马
我们先将两个数组从小到大排序，然后一一对应着比较
如果当前位置的饼干喂不饱这个小孩，那就意味着后面的小孩他全都喂不饱，那就直接将该饼干舍弃
如果对应位置喂得饱，那就直接喂，然后计数器++即可
代码如下：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s)
{
int n = g.size();
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, count = 0;
for(auto e : s)
if(i < n && e >= g[i]) count++, i++;
return count;
}
};leetcode 553.最优除法
这道题目其实就是一道脑经急转弯（差不多了）
他要的是所有元素都是除法，但是如果我们加了括号可以改变优先级，然后要求一个最大值而已
那么如果你是递归选手，用上了记忆化搜索之类的，那么这道题目就相当恶心
但是我们细看题干，要除法的最大值，我们只需要保证除数最大，被除数最小不就行了吗
我们第一个元素除以第二个元素是没有办法改变的，但后面的数如果就这么除下去的话相当于都乘到分子上了，所以最优的解法就是只在第二个数和最后一个数之间加一个括号即可
当然如果只有一个数或者两个数的时候，我们需要特判一下
代码如下：
class Solution
{
public:
string optimalDivision(vector<int> &nums)
{
int n = nums.size();
if (n == 1)
return to_string(nums[0]);
if (n == 2)
return to_string(nums[0]) + "/" + to_string(nums[1]);
string ret;
for (int i = 1; i < n; i++)
ret += (to_string(nums[i]) + "/");
ret = (to_string(nums[0]) + "/(") + ret;
ret[ret.size() - 1] = ')';
return ret;
}
};leetcode 45.跳跃游戏Ⅱ
这道题目有两种做法，一种是dp，一种是贪心
如果是dp的话，状态表示就是：在以 i 位置为结尾的所有情况中，到达该位置的最少跳跃次数
然后状态表示方程就是：
if(nums[j] + j >= i)
dp[i] = min(dp[i], dp[j] + 1);代码如下：
class Solution {
public:
int jump(vector<int>& nums)
{
int n = nums.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < i; j++)
if(nums[j] + j >= i)
dp[i] = min(dp[i], dp[j] + 1);
return dp[n-1];
}
};接着就是贪心了，但是在贪心之前，我们还需要模拟一遍这个过程，我们在过程中找到能贪的地方我们才能贪，否则只能乖乖的搜索
我们直接来看这张图，我们第一次跨的时候，我们能到达的位置就是 1 和 3，这一段区间可以视为第二次跳跃的起点，然后第二次我们能到达 3、1、1、4，但是这里的 3 和第二个重叠了，所以舍去，这一段橙色的区间就是第三次跳跃的起点
接着第三次的时候就能直接到达终点了
我们贪的点就在于，我们每一次都要找出下一段跳跃区间的最远距离
代码如下：
class Solution {
public:
int jump(vector<int>& nums)
{
int n = nums.size();
if(n == 1) return 0;
int left = 1, right = nums[0], ret = 1;
while (right < n-1)
{
int mn = INT_MIN;
for (int i = left; i <= right; i++) {
mn = max(mn, i + nums[i]);
}
left = right + 1;
right = mn;
ret++;
}
return ret;
}
};leetcode 55.跳跃游戏
这道题目和上面那一道差不多，就是每一次找完区间之后判断一下，如果这段区间的 right 在 left 的左边，那么就相当于我们无论如何也到不了结尾了
如果能顺利完成判断逻辑，从循环里面出来，那么就意味着可以到达终点，返回 true
代码如下：
class Solution {
public:
bool canJump(vector<int>& nums)
{
int n = nums.size();
int left = 1, right = nums[0];
while(right < n-1)
{
int mn = INT_MIN;
for(int i = left; i <= right; i++)
{
mn = max(mn, i + nums[i]);
}
left = right + 1;
right = mn;
if(right < left) return false;
}
return true;
}
};leetcode 134.加油站
这道题目还是挺有意思的
在做这道题目之前，我们需要想一想暴力解法，因为不能直接看出哪里可以贪，所以我们需要在将题意模拟一遍之后，我们才有可能找到可以贪的点
首先，当我们的油比消耗小的时候，我们是无法到达下一个加油站的，所以这种情况我们都可以舍去
然后我们的暴力解法就是，固定一个位置，接着从这个位置开始走一圈，如果能回来，那么就证明可以，就返回出发点的下标，否则就从下一个开始再走一圈（前提是油比消耗多）
这里有一个难点就是，我们应该如何控制他从尾巴走回到前面的绕环操作
其实这里我们可以创建一个变量step，step的大小就是整个数组的大小，我们从 i 位置出发之后，( i + step) % n，这样我们就能够在走到尾的时候走回最前面了（n 是整个数组的大小）
接着就是，我们应该怎么贪
我们做一个假设，假设加油站中有一部分是 abcdef，我们从 a 出发，但是到了 f 位置的时候走不动了，那么就有
a + b + c + d + e + f < 0
那此时我们发现 a 不行之后，我们就从 b 出发，但是我们的 a 的净收益一定是正数，因为他能从那里出发，此时我前面有 a 这个正数加一块儿都小于零了，现在我再去掉一个正数那就更小了，所以当我们遍历完 a 之后，我们可以直接从 f 位置的下一个位置开始遍历
代码如下：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
{
int n = gas.size();
for(int i = 0; i < n; i++)
{
if(gas[i] < cost[i]) continue;
int step = 0, gas_cap = 0;
for(; step < n; step++)
{
int index = (i + step) % n;
gas_cap = gas_cap + gas[index] - cost[index];
if(gas_cap < 0) break;
}
if(gas_cap >= 0) return i;
i = i + step;
}
return -1;
}
};leetcode 738.单调递增的数字
这道题目相对简单，首先我们要能判断数字里面的情况的话，有两种方法
一个是一直 /10 %10，还有一个就是直接将这个数变成一个string
这里其实还是更推荐变成string的，因为这样子更加清晰，遍历每一位就像是遍历数组一样
接着在知道最大数字之前，我们要搞清楚一种情况，那就是，他本身是否就是结果，比如123，返回的就是123
然后我们来举一个例子，12345324
此时我们走到了 5 的时候，我们后面就不是递增的了，此时我们要递增，我们只能将 5 减小 1 变成 4，我们降了一位之后，后面的数要最大，我们直接全部放 9 即可
也就是 12344999，这就是最大的情况
但是这样子做有一个bug，比如 1234555321
我们可以看到，当我们遍历到最后一个 5 的时候，按上面的逻辑，我们应该将这个 5 减一，但是我们减完 1 之后，和前面的 5 就又不是递增了，所以我们在遍历到这个数的时候，我们还需要往前走一走，看看有没有一样的，如果有的话，就将最前面那个一样的减一
对于这个例子，1234499999 就是答案
代码如下：
class Solution {
public:
int monotoneIncreasingDigits(int n1)
{
string arr = to_string(n1);
if(n1 < 10) return n1;
int n = arr.size();
for(int i = 1; i < n; i++)
{
if(arr[i] < arr[i-1])
{
for(int j = i-1; j > 0; j--)
if(arr[j] == arr[j-1]) i--;
else break;
int mid = (int)arr[i-1] - 1;
arr[i-1] = (char)mid;
for(int k = i; k < n; k++)
arr[k] = '9';
return stoi(arr);
}
}
return n1;
}
};今天这篇博客到这里就结束啦~(￣▽￣)~*
如果觉得对你有帮助的话，希望可以关注一下喔
最后，如果你有什么疑问，可以直接私信我或者在评论区留言，博主看到了的话一定会为你答疑的