C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

一、55. 跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 使用一个遍历表示覆盖范围，当覆盖范围达到数组最后一个元素时 返回true  否则返回false
        int cover =0;
        if(nums.size()==1) return true;
        for(int i=0;i<=cover;i++){
            cover = max(nums[i]+i,cover);
            if(cover>=nums.size()-1) return true;
        }
        return false;
    }
};

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

class Solution {
public:
    static bool cmp(const vector<int> &a,const vector<int> &b){
        return a[0]<b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size()==0) return 0;
        int result =1;
        sort(points.begin(),points.end(),cmp);
        for(int i=1;i<points.size();i++){
            if(points[i][0]>points[i-1][1]){
                result++;
            }
            else{
                points[i][1] =min(points[i][1], points[i-1][1]);
            }
        }
        return result;
    }
};

三、435. 无重叠区间

class Solution {
public:
    static bool cmp(const vector<int> a,const vector<int> b){
        return a[0]<b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size()==0) return 0;
        sort(intervals.begin(),intervals.end(),cmp);
        int result=0;
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>=intervals[i-1][1]){
                // 不重叠
            }
            else{
                result++;
                intervals[i][1] = min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return result;
    }
};

四、763.划分字母区间

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> result;
        int length;
        // 先求出每个字符出现的最大位置
        int hashmap[27] ={0};
        for(int i=0;i<s.length();i++){
            hashmap[s[i]-'a'] = i;
        }
        // 分割
        int left =0;
        int right = 0;
        for(int i=0;i<s.length();i++){
            right = max(right,hashmap[s[i]-'a']);
            if(i==right){
                result.push_back(right-left+1);
                left = right+1;
            }
        }
        return result;
    }
};

五、56. 合并区间

class Solution {
public:
    static bool cmp(const vector<int> &a,const vector<int> &b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size()==0) return {};
        // 结果数组
        sort(intervals.begin(),intervals.end(),cmp);
        vector<vector<int>> result;
        result.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(result.back()[1] <intervals[i][0]){
                // 说明没有重合
                result.push_back(intervals[i]);
            }
            else{
                // 有重合
                int right = max(result.back()[1],intervals[i][1]);
                result.back()[1] = right;
            }
        }
        return result;
    }
};

六、53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        int result =nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            if(dp[i]>result) result = dp[i];
        }
        return result;
    }
};