点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃
1.最长回文串
题目链接: 409. 最长回文串
题目分析:
给一个包含大小字母的字符串,从里面挑选出来一些字母构成一个最长回文串,然后返回它的长度。
算法原理:
我们可以先统计每个字符的个数,为什么先统计次数呢,我们发现构建的回文串从中间劈开后,相同的字符左边放一个右边放一个。把所有能用的字符能放就全部放那就是我们的贪心策略。
所以先统计每个字符出现的个数,然后以中间线为分割线左边放一个右边放一个。
上面是我们的总体思路,接下来考虑一下细节问题。字符可能是偶数个,也可能是奇数个。如果是偶数的话太好了全都放。但是如果是奇数个就有问题了,因为我们要左边放一个右边放一个要能对称,此时最贪心的想法就是奇数-1变成偶数然后放。
虽然上面把一左一右的搞定的,但是还是有一个小问题,回文串中间这个分割线也是可以摆一个字符,只要我们在统计字符个数的时候发现某个字符出现了奇数次,一左一右我们肯定会漏这一个字符,所以中间这里可以把这个字符加上。
所以我们策略出来了,如果偶数全部加上,如果是奇数 - 1 后在加上,所以情况都考虑完,在考虑中间这个地方能不能摆,取决于有没有出现一个字符出现奇数次,如果出现就在中间摆一个。
写代码的时候奇偶是可以放在一块写的,假设字符出现 x 次,ret += x / 2 * 2。因为 算 / 2 是一个向下取整 , 7 / 2 = 3, 3 * 2 =6,相当于就是7 - 1 = 6,如果是偶数 / 2 * 2 是不变的。
还有在最后要统计一下是否有个字符出现奇数次,其实也没有必要,其实用最后统计出来的ret和s.size()比较一下,如果小于 ret + 1,原因就是如果字符都出现偶数那么ret = s.size() 一左一右,如果小于那肯定有字符出现了奇数次。
class Solution {
public:int longestPalindrome(string s) {// 1.计数 -- 用数组模拟哈希表int hash[127] = {0};for(auto ch : s) hash[ch]++; // 2.统计结果 int ret = 0;for(auto x : hash) ret += x / 2 * 2;if(ret < s.size()) ++ret;return ret;}
};
2.增减字符串匹配
题目链接: 942. 增减字符串匹配
题目分析:
由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ,其中:
如果 perm[i] < perm[i + 1] ,那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ,那么 s[i] == ‘D’
其实s字符串就是描述[0,n]组成的数组的序列增减情况。
算法原理:
下面用一个例子说明一下
刚开始要符合一个增的形式,此时有很多选项可以放这里,那放5好不好?肯定是不好的,5是当前最大的数,接下来是一个增长趋势这里放5,下一个放谁都增不了,这里就有一个贪心的策略,我不会把最大的数放这里,因此我就贪到底,把最小的数放这里。
接下来是降,如果是降,会把1放这里吗?绝对不会,如果把最小的数放在这里接下来还降个锤子,此时还是贪到底,把最大的数放这里。
同理后面都是这样选择的。
最后在把最后一个数放在后面
我们的贪心策略:
- 当遇到 " I ",选择当前最小的那个数
- 当遇到 " D ",选择当前最大的那个数
这里简单证明一下我们这个策略是正确的。
当在增长的时候,如果我们选择较小的数摆,那无论接下来下一个数选谁绝对都是符合情况的。后面的数都是比我大。所以是绝对正确的。
同理如果第一个是降的话,拿最大的数摆,那括号里待选的数都是比我选的,无论较小的数如何排列,接下来下一个数绝对呈现下降趋势。
处理完之后,接下来对括号里面处理是一样的,这其实就是一个递归的过程,当算法一直递归下去的时候,每一个摆放都是合理的,所以我们和用归纳法来证明我们这个贪心策略是正确的。
class Solution {
public:vector<int> diStringMatch(string s) {int left = 0, right = s.size();// 用 left,right 标记最小值最大值vector<int> ret;for(auto ch : s){if(ch == 'I') ret.push_back(left++);else ret.push_back(right--);}ret.push_back(left); // 把最后一个数放进去return ret;}
};
3.分发饼干
题目链接: 455. 分发饼干
题目分析:
有一群孩子,还有一堆饼干,拿着这些饼干去喂这些孩子,问最多能喂饱多少孩子?喂饱孩子的要求是饼干尺寸要大于等于孩子的胃口。
算法原理:
看下面这个示例,我们来想贪心策略。首先我们要将胃口和饼干升序排列,如果数组乱序我们找的时候还需要去遍历数组很麻烦。所以我们先要把数组排序。
如果搞清题意的话,不知道会不会想到《优势洗牌 - 田忌赛马》这道题,田忌赛马这道题也是给数组之后我们给数组排下序,然后尽可能多的去赢。这道题是数组排序后,然后挑一些去满足上面的数,其实也是打败它。所以田忌赛马这道题的经验是有可能应用到我们这道题的。
这里我们就针对某个孩子然后去挑选饼干。
此时挑的时候发现,当前最小的饼干就能满足孩子,此时贪心就来了,如果最小的饼干就能这个孩子,后面的饼干肯定更能满足,此时我们的贪心就是选择较小的饼干去满足,尺寸较大的饼干可以去满足胃口更大的孩子。
如果此时最小的饼干满足不了孩子胃口,在田忌赛马哪里我们是让它直接去拖累掉最后一个元素,但是我们这里是喂孩子,不能拿最小的饼干去喂孩子,所以当我们发现当前数组中最小的饼干都不能满足孩子胃口的时候,那上面所有孩子胃口都不能满足,因为我们是升序排序的,所以当前这个饼干删掉,然后针对这个孩子,再去选前提饼干。
后序操作如上,直到所有饼干用完,那 i 前面这堆孩子是全部都能满足的,返回它的数量就可以了。
总结一下贪心策略:
排序,针对当前胃口最小的孩子,然后挑选饼干
- 能满足,直接喂
- 不能满足,直接删掉这个饼干
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 先排序sort(g.begin(), g.end());sort(s.begin(), s.end());// 利⽤双指针找答案int ret = 0, m = g.size(), n = s.size();for(int i = 0, j = 0; i < m && j < n; ++i, ++j){while(j < n && s[j] < g[i]) ++j;// 找饼⼲if(j < n) ret++;}return ret;}
};
证明:
证明方法:交换论证法
最优解在不失去最优性的前提下能调整成贪心解,就说明贪心解是正确的。
从左往右扫描贪心解和最优解饼干匹配情况,当第一次遇到匹配不相等,此时根据贪心解的策略,分两种情况讨论:
- 喂不饱
贪心策略是删去这个饼干,最优解如果和贪心解不一样的话,最优解会让这个饼干去喂某个孩子。但是这种情况是不可能发生的,因为我们是升序的,如果当前饼干连最小的孩子都不能满足,那后面的孩子也满足不了,所以这个贪心和最优是一样的,都是直接删掉。
2. 能喂饱
能喂饱我们的贪心是直接喂,最优解其实是有两种情况,要么这个饼干喂后面的孩子,要么这个饼干压根就没用。这个孩子也有情况情况,要么后面有饼干来喂这个孩子,要么没有饼干来喂这个孩子。两两结合我们要分四种情况讨论。
一:饼干用了,这个孩子也被后面饼干满足了。
二:饼干用了,孩子没被满足
三:饼干没用,孩子被满足
四:饼干没用,孩子没被满足
考虑第一种情况:
此时调整就是,就是绿色情况,只要证明绿色和紫色同样优秀就可以了
紫色的线有两个不等式,b > x1, a > x2,又因为升序 b > a,所以 b > a > x2,
所以b一定能喂x2,a调整喂x1贪心告诉我们是可以的。 调整前喂得饱,调整后也喂得饱,所以第一种情况是可以的。
考虑第二种情况:
饼干喂了后面孩子x2,但是x1这个孩子没人喂。
此时调整a去喂x1也不会破坏最优,把a喂x2可以填饱肚子,那此时不喂x2,去喂x1也是可以填饱肚子,并且孩子个数没有发生改变,所以第二种情况是可以的。
考虑第三种情况:
没有用a这个饼干,x1这个孩子被后面b喂。
此时调整,不用b喂了,用a喂,也是可以的,在贪心解里知道a 是可以满足x1的,所以也是可以的。
考虑第四种情况:
没有a饼干,也没有x1这个孩子
此时调整a去喂x1,相当于在之前最优解的情况下又多了一个能喂饱的孩子,所以贪心更优最优解,所以绝对是可以的。
综上所述,无论是上述情况哪一种我们都可以调整的,所以能喂饱也是可以的。
此时我们的贪心就是正确的。
4.最优除法
题目链接: 553. 最优除法
题目分析:
给定一正整数数组 nums,nums 中的相邻整数将进行浮点除法。
例如,nums = [2,3,4],我们将求表达式的值 “2/3/4”。
但是,你可以在任意位置添加任意数目的括号,来改变算数的优先级。
你需要找出怎么添加括号,以便计算后的表达式的值为最大值。
题意其实就是数组给一堆数,数中间其实都有除法的,此时让我们任意位置添加一些括号,使表达式的值为最大值,最后返回的是以字符串格式返回具有最大值的对应表达式。
注意:你的表达式不应该包含多余的括号。
原本括号里面顺序是3/4/5,现在多添加一个括号还是3/4/5。
算法原理:
举一个例子来提取我们的贪心策略
这个时候我们要明白一点,在这个表达式中添加括号最终都会转换为 x/y 的形式。也就是从这些数中挑一些放在分子上,一些数放在分母上,
我们最终要的是 x/y 是最大的,一个分数要最大,要么就是分子变大,要么就是分子变小。接下来我们设计表达式就是尽可能让分子大,分母小。这就是我们的贪心方向。
还有一点无论在表达式哪里填上括号,a都是在分子上,b都是在分母上,所以a和b这两个无法通过添加括号去改变的a/b。所以最终a一定在分子上,b一定在分母上。
现在可供我们选择的就是c、d、e、f,为了使最终结果最大,我们就想无脑的把c、d、e、f和a一起放在分子上。
这里可以用贪心优化就是因为这个值乘起来是越来越大的
贪心策略:除了前两个数以外,其余的数全部放在分子即可
如何实现贪心策略呢?
这里我们用小学就学过的知识,负负得正。除除得正。因此我们仅需在b之前填一个(,f后填一个)
括号里面得除法全都因为括号外面得除法变成除除得正,
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 = to_string(nums[0]) + "/(" + to_string(nums[1]);for(int i = 2; i < n; ++i){ret += '/' + to_string(nums[i]);}ret += ')';return ret;}
};