--0--

455. 分发饼干

class Solution {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
            int res=0;
            sort(g.begin(),g.end());
            sort(s.begin(),s.end());
            int p1=0,p2=0;
            while(p1<g.size() && p2<s.size()) {
                if(s[p2]>=g[p1]) {
                    res++;
                    p2++;
                    p1++;
                }
                else{
                    p2++;
                }
            }
            return res;
        }
};

--1--

376. 摆动序列

出自评论区这位大佬，真的tql%%%
思路其实和下面方法4的状态自动机差不多，但代码就是简洁很多。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return n;
        }
        int up = 1;
        int down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            }
            if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return max(up, down);
    }
};

--2--

402. 移掉K位数字

稍微思考一下可以发现，因为位数是相同的，所以需要尽量保持高位的数字小，因此出现当前位比下一位大，就把当前位删掉。
因此使用了一个栈结构，但是是用vector来模拟栈，因为vector可以遍历，最后输出字符串更方便。
还有需要注意的是前导0处理，在下面代码中有注释。

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char> s;
        string res="";
        for(int i=0;i<num.length();i++){
            while(s.size()!=0 && s[s.size()-1]>num[i] && k>0){
                s.pop_back();
                k--;
            }
              //处理前导0，只有在数字为0而且栈空的情况下，不会push
            if(num[i]!='0' || s.size())
                s.push_back(num[i]);
        }
        while(s.size()&&k){
            s.pop_back();
            k--;
        }
        for(int i=0;i<s.size();i++)
            res+=s[i];
        if(res=="") res="0";
        return res;
    }
};

--3--

55. 跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxlen=-1;
        for(int i=0; i<nums.size(); i++) {
            maxlen= max(nums[i]+i,maxlen);
            // 把maxlen<=i后面的&&去掉提交一下就知道为啥要加了。。
            if(maxlen<=i && !(i==nums.size()-1 && nums[i]==0))
                return false;
        }
        return true;
    }
};

--4--

45. 跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<2) return 0;
        int res=1;
        int current_max_index=nums[0];
        int pre_max_index=nums[0];
        for(int i=0;i<nums.size();i++){
            if(i>current_max_index){
                res++;
                current_max_index=pre_max_index;
            }
            pre_max_index=max(pre_max_index,nums[i]+i);
        }
        return res;
    }
};

--5--

452. 用最少数量的箭引爆气球

1.按气球前端排序（逐渐缩小区间的思想）

虽然过了但是很慢QAQ

class Solution {
  public:
    int findMinArrowShots(vector<vector<int>> &points) {
        if (points.size() == 0)
            return 0;
        sort(points.begin(), points.end(),
             [](vector<int> x, vector<int> y) { return x[0] < y[0]; });
        int res = 1;
        int begin = points[0][0];
        int end = points[0][1];
        for (int i = 1; i < points.size(); i++) {
            if (end >= points[i][0]) {
                begin = points[i][0];
                end = min(end, points[i][1]);
            } else {
                res++;
                begin = points[i][0];
                end = points[i][1];
            }
        }
        return res;
    }
};

2.按气球后端排序（大佬思想）

大佬的代码简洁又快QAQ，前面sync_with_stdio那个是关同步，提高cin速度。具体可以参考解析static auto x = []() { std::ios::sync_with_stdi..._CSDN博客

大佬的代码

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();


class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        
        sort(points.begin(), points.end(), [](const auto& l, const auto& r)
             {
                return l[1] < r[1];
             });
        
        int count = 1;
        int tail = points[0][1];
        for (int i = 1; i < points.size(); i++)
        {
            if (points[i][0] <= tail) continue;
            count += 1;
            tail = points[i][1];
        }
        return count;
    }
};

一开始感觉贪心算简单的了。。现在感觉贪心对脑子要求很高QAQ

PAT 1033 To Fill or Not to Fill (25分)

牛客pat

经典贪心，汽车加油问题

LeetCode 贪心练习题