[贪心算法]最长回文串 增减字符串匹配 分发饼干

1.最长回文串

我们可以存下每个字母的个数，然后分类讨论

1. 如果是奇数就减一加到结果中
2. 如果是偶数就直接加入即可
   最后判断长度跟原字符串的差距，如果小于原数组说明有奇数结果+1

class Solution {
public:int longestPalindrome(string s) {int ret=0;//1.计数int hash[127]={0};for(char ch:s)  hash[ch]++;//2.统计结果for(int x:hash){ret+=x/2*2;}return ret<s.size() ? ret+1 :ret;}
};

2.增减字符串匹配

• 如果是I说明数字是递增的，贪心就体现在把最小的数字放在这个，因为不论后面放什么数字都一定会是递增的
• 如果是D说明数字在递减，同理把最大的数字放在这即可。
  所以我们使用left和right来标记数组的最大和最小即可

class Solution {
public:vector<int> diStringMatch(string s) {int left=0,right=s.size();vector<int> ret;for(auto ch:s){if(ch=='I')ret.push_back(left++);elseret.push_back(right--);}ret.push_back(left);return ret;}
};

3.分发饼干

我们先对这两个数组排序，然后就按照田忌赛马的思路，如果最小的可以满足就直接给最小的，然后向后继续寻找即可。
也就是：两个指针，找到最小能满足孩子的饼干，不能就直接++

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&& g[i]>s[j])//这个是循环，直到找到合适的饼干为止{j++;}if(j<n){ret++;}}return ret;}
};

4.跳跃游戏Ⅱ

用left和righ控制跳跃的空间，left=right+1 right就是每次跳跃的最大距离

class Solution {
public:int jump(vector<int>& nums) {int count=0;int n=nums.size();int left=0,right=0;int maxn=0;while(left<=right){if(maxn>=n-1)return count;for(int i=left;i<=right;i++)//找出区间内最大的数及其下标的和{maxn=max(maxn,nums[i]+i);}left=right+1;right=maxn;count++;}return -1;}
};

5.跳跃游戏

这里把上题的返回值修改一下即可

class Solution {
public:bool canJump(vector<int>& nums) {int count = 0;int n = nums.size();int left = 0, right = 0;int maxn = 0;while (left <= right) {if (maxn >= n - 1)return true;for (int i = left; i <= right;i++) // 找出区间内最大的数及其下标的和{maxn = max(maxn, nums[i] + i);}left = right + 1;right = maxn;count++;}return false;}
};

6.最优除法

根据除除为乘，我们只需要把b到最后这段区间的数字优先处理，就可以让分子变为最大，分母最小

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 str=to_string(nums[0])+"/("+to_string(nums[1]);for(int i=2;i<n;i++){str+="/";str+=to_string(nums[i]);}str+=")";return str;}
};