目录

力扣135 分发糖果

力扣316.去除重复字母

力扣402  移掉K位数字

力扣397  整数替换：

贪心真的很看感觉！！！

力扣135 分发糖果

 贪心策略：这道题属于是第一次咋也不会，写过第二次就秒了，从左到右一遍，再从右到左一遍

class Solution {
public:int candy(vector& ratings) {int n=ratings.size();vector res(n,1);int sum=0;for(int i=1;iratings[i-1])res[i]=res[i-1]+1;}    for(int i=n-2;i>=0;--i){//第二次从右到左，保证左边大的比右边小的得到糖果多if(ratings[i]>ratings[i+1]&&res[i]<=res[i+1]){res[i]=res[i+1]+1;}}for(auto e:res)sum+=e;return sum;}
};

力扣316.去除重复字母

贪心策略： 

假如当前的字符是x，永远只看前一个，只要前一个比x大而且前一个可以删除（后面还有），那就把前一个删了，然后让x顶上（前提是x之前没有用过，因为一个字符只能用一次）。

   string removeDuplicateLetters(string s) {int n=s.size();int counts[26]={0};bool used[26];string res="";//要返回的结果memset(used, false, sizeof(used));for(auto e:s){counts[e-'a']++;//记录一下每个字母出现的次数}for(auto e:s){//添加字符到结果中counts[e-'a']--;//不管用不用这个字符，都要把可使用的次数减一if(used[e-'a'])//这个字符已经用过了，不能再使用了continue;//res中有字符，字符尾小于e，字符尾还可以删while(res.length() > 0 && res[res.size()-1]>e&&counts[res[res.size()-1]-'a']>0){used[res[res.size()-1]-'a']=false;//删除之前一定不要忘了把use改为没有用过res.erase(res.size()-1);}res+=e;used[e-'a']=true;//表示已经用过了}return res;}

力扣402  移掉K位数字

 贪心策略：和上一道题差不多，也是只看前一个数字，如果能删就把前一个数字删了，（能删的条件是k>0、res.size()>0）然后当前的数字顶上，当前数字的删除与否由后面的数字决定，当前觉得能用，那就先用上（这就是贪啊！！！）。

string removeKdigits(string num, int k) {int n = num.size();if (k >= n)return "0";string res = "";for (auto e : num) {if (k == 0) {//直接把后面的拼上就行了res += e;continue;}else {while(res.size() > 0 && res[res.size() - 1] > e&&k>0) {//代表能删掉末尾了res.erase(res.size() - 1);k--;}res += e;}}int i = 0;//如果删除的字符个数不够，需要将末尾的删除for (int j = 0; j < k; ++j) {res.pop_back();}while (res[0] == '0') {res.erase(res.begin());}if (res.size() == 0) {return "0";}return res;
}

力扣397  整数替换：

题目描述：

 对于偶数，不用多想，肯定直接 /2   就行了

但是对于奇数，那就很巧妙了！（这个题不看题解是真的想不出来居然还有这么巧妙的办法，太amazing了）

既然是一个奇数，那么%4，肯定是要么==1，要么==3，

对于余1和余3分别做不同的贪心策略：

1、假设是余1的情况，相当于是   x==4k+1  的一个数，怎么变化呢？

直觉告诉我们，这个1好讨厌啊，要是去掉就好了，对的，就是直接  -1  。4k+1    ---》 4k   ---》  2k  ---》 k  ，两步就能达到2k，这里也很巧妙啊（WC），他这里直接是   x/2   ，相当于是直接走两步   因为（4k+1)/2  正好是  2k, 所以直接res+=2就好了。

2、假设是余3的情况，相当于是   x==4k+3  的一个数，怎么变化呢？

额额额，上一个-1了，这个必是+1啊，但是这里就很骚了，+1是有可能越界的

 为了不产生+1这个动作，他也是直接进行了两步操作   x/2 +1 ，相当于（4k+3+1）/2  ,（WC这里真的是秀我一脸），然后ans+=2

就好了。

    int integerReplacement(int n) {int res=0;while(n>1){if(n%2==0){n=n/2;res++;}else{if(n%4==1){n=n/2;//这里直接就进行了两步   -1 和 /2res+=2;}else{if(n==3){n=1;res+=2;break;}else{//这里直接两步的话，先/2，还能保证不会越界n=n/2+1;//这里也是直接进行两步  +1  /2res+=2;}}}}return res;}