1.回溯算法

1.1 77-组合

77

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    //组合抽象为一个泡泡树
    void backtracking(int n, int k, int startIndex)
    {
        if(path.size() == k)
        {
            ans.push_back(path); //将泡泡数据加入结果
            return; //返回去等待删除一个泡泡
        }
        for(int i = startIndex; i <= n-(k-path.size())+1; ++i )
        {
            path.push_back(i);  //加入一个泡泡
            backtracking(n,k,i+1); //负责剩下的泡泡处理
            path.pop_back(); //删除一个泡泡
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n,k,1);
        return ans;
    }
};

画的巨抽象的图
在这里插入图片描述
在这里插入图片描述

1.2 216-组合的综合III

216

在这里插入图片描述

注意剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(int k , int n, int startindex)
    {
        if(path.size() == k)
        {
            int sum = 0;
            for(auto& e : path)
                sum+=e;
            if(sum == n)
                ans.push_back(path);
            return;
        }
        for(int i = startindex; i <= 9 - (k-path.size()) +1; ++i)
        {
            path.push_back(i);
            backtracking(k,n,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,1);
        return ans;
    }
};

1.3 17-电话号码的字母组合

17

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string path;
    vector<string> ans;
    vector<string> dir={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void backtracking(string digits,int startindex)
    {
        if(startindex==digits.size())
        {
            ans.push_back(path);
            return;
        }
        int num=digits[startindex]-'0'; //字符串转整形
        for(int i = 0; i < dir[num].size();i++)
        {
            path.push_back(dir[num][i]);
            backtracking(digits,startindex+1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) 
            return ans;
        backtracking(digits,0);
        return ans;
    }
};

1.4 39-组合总和

39

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target,int sum,int startindex)
    {
        if(sum == target)
        {
            ans.push_back(path);
            return;
        }
        else if(sum > target)
            return;

        for(int i = startindex; i < candidates.size(); ++i)
        {
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,i);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int sum = 0;
        backtracking(candidates,target,sum,0);
        return ans;
    }
};

然而还需要优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target,int sum,int startindex)
    {
        if(sum == target)
        {
            ans.push_back(path);
            return;
        }

        //将sum>target的if移入至for中,由于已经排序,如果发生了,直接当作for的判断条件跳出循环
        for(int i = startindex; i < candidates.size() && 
            sum+candidates[i] <= target; ++i)
        {
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,i);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int sum = 0;
        sort(candidates.begin(),candidates.end()); //排序一下
        backtracking(candidates,target,sum,0);
        return ans;
    }
};

1.5 40-组合总和II

40

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target,int sum, int startindex)
    {
        if(sum == target)
        {
            ans.push_back(path);
            return;
        }

        for(int i = startindex; i < candidates.size() && sum+candidates[i] <= target;++i)
        {
            //防止candidates中有重复元素的影响,重复开始算入答案,导致结果有重复
            if(i > startindex && candidates[i] == candidates[i-1])
                continue;
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,i+1);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0);
        return ans;
    }
};

在这里插入图片描述

1.6 131-分割回文串

131

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    bool is_back(const string& str,int start,int end)
    {
        while(start < end)
        {
            if(str[start] != str[end])
                return false;
            start++;
            end--;
        }
        return true;
    }

    void backtracking(string s,int startindex)
    {
        if(startindex == s.size())
        {
            ans.push_back(path);
            return;
        }
        for(int i = startindex; i < s.size();++i)
        {
            if(is_back(s,startindex,i))
            {
                string tmp = s.substr(startindex,i-startindex+1);
                path.push_back(tmp);
            }
            else
                continue;

            backtracking(s,i+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return ans;
    }
};

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private:
    vector<vector<string>> result;
    vector<string> path;
    vector<vector<bool>> isPalindrome; // 放事先计算好的是否回文子串的结果
    void backtracking (const string& s, int startIndex) 
    {
        if (startIndex >= s.size()) 
        {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) 
        {
            if (isPalindrome[startIndex][i]) 
            {   
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            }
            else         
                continue;
            backtracking(s, i + 1); // 寻找i+1为起始位置的子串
            path.pop_back(); // 回溯过程，弹出本次已经填在的子串
        }
    }
    void computePalindrome(const string& s) { //aab 
        // true  true  false  j--i 为回文串?
        // false true  false
        // false false true
        isPalindrome.resize(s.size(), vector<bool>(s.size(), false)); 
        for (int i = s.size() - 1; i >= 0; i--) 
        { 
            for (int j = i; j < s.size(); j++) 
            {
                if (j == i) 
                    isPalindrome[i][j] = true;
                else if (j - i == 1) 
                    isPalindrome[i][j] = (s[i] == s[j]);
                else    //如果中间隔的多,只需判断首尾和通过表中的判断
                    isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        computePalindrome(s);
        backtracking(s, 0);
        return result;
    }
};

1.7 93-复原IP地址

93

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    vector<string> ans;
    bool isvalid(string& s,int start,int end)
    {
        if(start>end)
            return false;
        if(s[start] == '0' && start != end) //头部为0
            return false;
        int sum = 0; //统计三个数是否合法
        for(int i = start; i <=end ; ++i)
        {
            if(s[i] >'9' || s[i] < '0') //非法字符
                return false;

            sum = sum*10+s[i]-'0'; //超过255
            if(sum > 255)
                return false;
        }
        return true;
    }

    void backtracking(string& s,int startindex,int pointnum)
    {
        if(pointnum == 3)
        {
            //将最后一组全部放进去,还可以避免切的太小而导致的没有用完
            if(isvalid(s,startindex,s.size()-1)) 
                ans.push_back(s);
            return;
        }
        for(int i = startindex;i<s.size();++i)
        {
            if(isvalid(s,startindex,i))
            {
                s.insert(s.begin()+i+1,'.');
                pointnum++;
                backtracking(s,i+2,pointnum); //i跳两格,因为有.
                s.erase(s.begin()+i+1); //删除.
                pointnum--;
            }
            else
                break; //不合法直接跳出去(递归中出去)
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.size() < 4 || s.size()>12)
            return ans;
        backtracking(s,0,0);
        return ans;
    }
};

1.8 78-子集

78

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& nums,int startindex)
    {
        ans.push_back(path);
        for(int i = startindex; i < nums.size(); ++i)
        {
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return ans;
    }
};

1.9 90-子集II

90

在这里插入图片描述

相较于上一题,只是多了一步去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& nums,int startindex)
    {
        ans.push_back(path);
        for(int i = startindex; i < nums.size(); ++i)
        {
            if(i>startindex && nums[i] == nums[i-1]) //去重
                continue;
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end()); //先排序以便去重
        backtracking(nums,0);
        return ans;
    }
};

1.10 491-递增子序列

491

在这里插入图片描述

利用哈希来去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) 
    {
        if (path.size() > 1) 
            result.push_back(path);

        int used[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]

        for (int i = startIndex; i < nums.size(); i++) 
        {
            if ((!path.empty() && nums[i] < path.back()) //不满足递增
                    || used[nums[i] + 100] == 1) //有重复
                    continue;
            
            used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
};

1.11 46-全排列

46

在这里插入图片描述

利用used数组和for的从0开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& nums,vector<bool>& used)
    {
        if(path.size() == nums.size())
        {
            ans.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); ++i)
        {
            if(used[i] == true)
                continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums,used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false); //记录元素是否被使用过
        backtracking(nums,used);
        return ans;
    }
};

1.12 47-全排列II

47

在这里插入图片描述

相较于上一题多出了,树枝去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& nums,vector<bool>& used)
    {
        if(path.size() == nums.size())
        {
            ans.push_back(path);
            return;
        }
        for(int i = 0; i<nums.size(); ++i)
        {
            //i>0 且 有重复的数据时,判断used[i-1]
            if((i>0 && nums[i] == nums[i-1] && used[i-1] == false) //树枝去重
                || used[i] == true) //树层去重
                continue;

            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums,used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);
        backtracking(nums,used);
        return ans;
    }
};

1.13* 51-N皇后

51
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    vector<vector<string>> ans;
    bool isvalid(int row,int col,vector<string>& chessboard,int n)
    {
        int count = 0;

        //check col
        for(int i = 0; i < row; ++i)
        {
            if(chessboard[i][col] == 'Q')
                return false;
        }

        //check lefter
        for(int i = row-1,j = col-1;i>=0 && j>=0; --j,--i )
        {
            if(chessboard[i][j] == 'Q')
                return false;
        }

        //check righter
        for(int i = row-1, j = col+1; j < n && i>=0; ++j,--i)
        {
            if(chessboard[i][j] == 'Q')
                return false;
        }
        return true;
    }

    void backtracking(int n , int row,vector<string>& chessboard)
    {
        if(row == n)
        {
            ans.push_back(chessboard);
            return;
        }
        for(int i = 0; i < n;++i)
        {
            if(isvalid(row,i,chessboard,n))
            {
                chessboard[row][i] = 'Q';
                backtracking(n,row+1,chessboard);
                chessboard[row][i] = '.';
            }
        }
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n,string(n,'.')); //初始化棋盘
        backtracking(n,0,chessboard);
        return ans;
    }
};

2. 贪心算法

2.1 455-分发饼干

455

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = s.size() - 1; //最大饼干坐标
        int ans = 0;
        for(int i = g.size()-1; i >= 0; --i) //从最大胃口开始遍历
        {
            if(index >= 0 && s[index] >= g[i])
            {
                ans++;
                index--;
            }
        }
        return ans;
    }
};

2.2 376-摆动序列

376

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1)
            return nums.size();
        int curdif = 0;
        int prevdif = 0;
        int ans = 1; //第一个数没有比较,直接算上
        for(int i = 0; i < nums.size() -1;++i) //最后一个数据不算入(i+1)
        {
            curdif = nums[i+1] - nums[i];
            if((prevdif <= 0 && curdif>0) || (prevdif >=0 && curdif<0))
            {
                ans++;
                prevdif = curdif;
            }
        }
        return ans;
    }
};

2.3 53-最大数组和

53

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        int count = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            count+=nums[i];
            if(count > ans) //记录小段中的最大值,即答案
                ans = count;
            if(count <= 0) //小段中如果小于0,累加之后就是亏,直接置0重新开始
                count = 0;
        }
        return ans;
    }
};

2.4 122-买股票的最佳时机II

122

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 1; i < prices.size(); i++) 
        {
            int tmp = prices[i] - prices[i - 1];
            if (tmp > 0) 
                profit += tmp;
        }
        return profit;
    }
};

2.5 55-跳跃游戏

55

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        for (int i = 0; i <= cover; i++) 
        { 
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) 
                return true;
        }
        return false;
    }
};

2.6 45-跳跃游戏II

45

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int jump(vector<int>& nums) 
    {
        int ans = 0;
        int start = 0;
        int end = 1;
        int maxPos = 0;
        while (end < nums.size())
        {
            for (int i = start; i < end; i++)
                maxPos = max(maxPos, i + nums[i]);
                
            start = end;      // 下一次起跳点范围开始的格子
            end = maxPos + 1; // 下一次起跳点范围结束的格子
            ans++;            // 跳跃次数
        }
        return ans;
    }
};

2.7 1005-K次取反后最大化的数组和

1005

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        sort(nums.begin(), nums.end());
        int index = 0;
        int ans = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] < 0 && k > 0)
            {
                nums[i] *= -1;
                k--;
                index = i + 1; // 最后一个取反的元素的下标+1，也就是第一个没被取反的元素的下标}
            }
            ans += nums[i];
        }
        // 找到对所有负数取反后的最小非负数的下标,分别考虑原数组全正、全负、有正有负的情况
        if (index > 0 && index < nums.size() && nums[index] > nums[index - 1])
            index = index - 1;			//对比正负交界处,如果原本是全正,根本就进不去
        else if (index == nums.size()) //即原本是全负
            index = nums.size() - 1;

        if (k % 2 == 1)
            ans -= nums[index] * 2;

        return ans;
    }
};

2.8 134-加油站

134
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) 
        {
            curSum += gas[i] - cost[i]; //计算起点
            totalSum += gas[i] - cost[i]; //计算是否可以跑完
            if (curSum < 0) 
            {
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) 
            return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

2.9* 135-分发糖果

135

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++)
            if (ratings[i] > ratings[i - 1]) 
                candyVec[i] = candyVec[i - 1] + 1;

        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--)
            if (ratings[i] > ratings[i + 1] ) 
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);

        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) 
            result += candyVec[i];
        return result;
    }
};

2.10 860-柠檬水找零

860

在这里插入图片描述
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0, twenty = 0;
        for (int bill : bills) 
        {
            if (bill == 5) 
                five++;
            else if (bill == 10) 
            {
                if (five <= 0) 
                    return false;
                ten++;
                five--;
            }
            else
            {
                if (five > 0 && ten > 0) 
                {
                    five--;
                    ten--;
                } 
                else if (five >= 3) //三个五块也能找零
                    five -= 3;
                else return 
                    false;
            }
        }
        return true;
    }
};

2.11 406-根据身高重建队列

406

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b)
    {
        if(a[0] == b[0])
            return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        list<vector<int>> que; //链表插入效率高
        for(int i = 0; i < people.size(); ++i)
        {
            int position = people[i][1];
            list<vector<int>>::iterator it = que.begin();
            while(position--)
                it++;
            que.insert(it,people[i]);
        }
        return vector<vector<int>>(que.begin(),que.end());
    }
};

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

452
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) 
    {
        if (points.size() == 0) 
            return 0;
        sort(points.begin(), points.end(), cmp);

        int result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < points.size(); i++) 
        {
            if (points[i][0] > points[i - 1][1])   // 气球i和气球i-1不挨着，注意这里不是>=
                result++; // 需要一支箭
            
            else  // 气球i和气球i-1挨着
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
        }
        return result;
    }
};

2.13 435-无重叠区间

435

在这里插入图片描述

用引爆气球的方式可以通过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) 
    {
        return a[1] < b[1]; // 右边界排序 
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) 
            return 0;
        sort(intervals.begin(), intervals.end(), cmp);

        int result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < intervals.size(); i++) 
        {
            if (intervals[i][0] >= intervals[i - 1][1]) 
                result++; // 需要一支箭
            else  // 气球i和气球i-1挨着
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界
        }
        return intervals.size() - result;
    }
};

另外

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 count = 0; // 注意这里从0开始，因为是记录重叠区间
        for (int i = 1; i < intervals.size(); i++) 
        {
            if (intervals[i][0] < intervals[i - 1][1]) 
            { 
                //重叠情况
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
                count++;
            }
        }
        return count;
    }
};

2.14 763-划分字母区间

763

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++)  // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;

        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) 
        {
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) 
            {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

2.15 56-合并区间

56

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) 
            return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) 
        {
            if (result.back()[1] >= intervals[i][0]) 
            // 发现重叠区间
            // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            else 
                result.push_back(intervals[i]); // 区间不重叠 
        }
        return result;
    }
};

2.16 738-单调递增的数字

738

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) 
        {
            if (strNum[i - 1] > strNum[i] ) 
            {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++)
            strNum[i] = '9';
        return stoi(strNum);
    }
};

2.17* 968-监控二叉树

968

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) 
    {
        // 空节点，该节点有覆盖
        if (cur == NULL) 
            return 2;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        // 情况1
        // 左右节点都有覆盖
        if (left == 2 && right == 2) 
            return 0;

        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) 
        {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) 
            return 2;

        // 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0)  // root 无覆盖
            result++;
        return result;
    }
};