记录

1. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 对于起点即终点直接返回true
        if(nums.size() < 2)
            return true;
        // 记录每次跳跃后下一次跳跃的最远距离
        int farPos = nums[0];
        // 因为跳跃到当前结点的值决定下一次的跳跃范围，所以在跳跃范围内进行选择下一次要跳的位置，以保证下下次能调到更远的位置，这样来进行贪心选择，每次满足局部最优
        for(int i = 1; i <= farPos; i ++){
            // 当在跳跃范围内，可能下一次要跳的距离范围大于当前值，就要对其进行更新，以保证局部最优逐渐收敛到全局最优
            if(nums[i] + i > farPos){
                farPos = nums[i] + i;
            }
            // 只要有一种跳跃方式能够跳到大于等于终点的位置，就能到达终点
            if(farPos >= nums.size() - 1)
                return true;
        }
        return false;
    }
};

2. 跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

fig1

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 farPos = 0;  // 记录每次跳跃到的最远距离
        int steps = 0;  // 记录最少跳跃次数
        int pos = 0;  // 记录每次跳跃到的位置范围的右边界
        // 采用贪心思想，无论跳到那个位置，为了使整个过程跳跃次数最少，就要使每次跳跃的范围最大，更接近最终的目标
        for(int i = 0; i < nums.size() - 1; i ++){ //使用 < nums.size() - 1是为了不访问最后一个元素，不然会增加一次不必要的跳跃
            if(i + nums[i] > farPos){  // 寻找每次的最远边界
                farPos = i + nums[i];
            }
            // 整个过程是将从第一个位置开始算是一次跳跃，一次来抵消最后一次没有实际跳跃动作
            if(i == pos){ // 通过到达最远边界来进行衡量跳跃次数
                pos = farPos;
                steps ++;
            }
        }
        return steps;
    }
};

3. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

1
2
3
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

1
2
3
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

1
2
3
输入: intervals = [ [1,2], [2,3] ]
输出: 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
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
// 方法一
class Solution {
public:
    static bool cmp(vector<int>& interval1, vector<int>& interval2){
        // 按照右边界排序
        return interval1[1] < interval2[1];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 按照贪心的思路，尽可能选右边界小的区间做不重叠区间
        if(intervals.size() < 1)
            return 0;
        int num = 1; // 记录最多不重叠区间数
        sort(intervals.begin(), intervals.end(), cmp);

        int end = intervals[0][1]; // 记录当前不重叠区间的最右边界
        for(int i = 1; i < intervals.size(); i ++){
            if(end <= intervals[i][0]){
                num ++;
                end = intervals[i][1];
            }
              
        }
        // 最少移除区间数就等于总的区间数减去最大不重叠区间数
        return intervals.size() - num;
    }
};

// 方法二
class Solution {
public:
    static bool cmp(vector<int>& interval1, vector<int>& interval2){
        // 按照左边界排序
        return interval1[0] < interval2[0];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 按照贪心的思路，尽可能选右边界小的区间做不重叠区间
        if(intervals.size() < 1)
            return 0;
        int num = 0; // 记录最少重叠区间数
        sort(intervals.begin(), intervals.end(), cmp);

        for(int i = 1; i < intervals.size(); i ++){
            if(intervals[i][0] < intervals[i - 1][1]){
                num ++;
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
            }
              
        }
        return num;
    }
};

4. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

1
2
3
4
5
6
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

1
2
输入：s = "eccbbbbdec"
输出：[10]

使用贪心的思想寻找每个片段可能的最小结束下标，因此可以保证每个片段的长度一定是符合要求的最短长度，如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的。

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<int> partitionLabels(string s) {
        // 记录每个字符出现的最远位置下标
        map<char, int> mp;
        // 记录字符串每个能够划分开的长度
        vector<int> ans;
        // 在向后遍历过程中，字符与其最远下标映射不断更新，直到没有变化
        for(int i = 0; i < s.size(); i ++){
            mp[s[i]] = i;
        }
        // 记录上一个能够划分成的字符串的右边界
        int lastinterval = 0;
        // 记录当前能够划分成的字符串的右边界
        int interval = 0;
        for(int j = 0; j < s.size(); j ++){
            // 不断向后遍历，不断更新当前已遍历过字符的最远边界
            interval = max(interval, mp[s[j]]);
            // 当已遍历字符的最远边界等于当前的下标，说明现在已遍历的字符可以划分成一个子字符串了，使用贪心思想，只要找到当前边界等于遍历过字符的最远边界就划分，从局部最优推至全局最优
            if(interval == j){
                ans.push_back(interval + 1 - lastinterval);
                lastinterval = interval + 1;
            }
              
        }
        return ans;
    }
};

5. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

用数组ans存储最终的答案。

  • 先将列表中的区间按照左端点升序排序。然后我们将第一个区间加入ans数组中，并按顺序依次考虑之后的每个区间：如果当前区间的左端点在数组ans中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组ans的末尾；
  • 否则，它们重合，我们需要用当前区间的右端点更新数组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
class Solution {
public:
    static bool cmp(vector<int>& interval1, vector<int>& interval2){
        // 按照左边界进行升序排序
        return interval1[0] < interval2[0];
    }
  
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 记录不重叠的区间数组
        vector<vector<int>> ans;
        // 当区间数为1或0时直接返回
        if(intervals.size() < 2){
            return intervals;
        }
        // 排序
        sort(intervals.begin(), intervals.end(), cmp);
        // 先将第一个区间入栈
        ans.push_back(intervals[0]);

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

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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

1
2
3
4
5
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

1
2
3
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

1
2
3
4
5
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
public:
    static bool cmp(vector<int>& point1, vector<int>& point2){
        // 按照左边界排序
        return point1[0] < point2[0];
    }

    int findMinArrowShots(vector<vector<int>>& points) {
        // 如果当前点的区间数为0直接返回0
        if(points.empty())
            return 0;

        // 记录重叠区间的交集和不重叠区间
        vector<vector<int>> overlaps;
        // 将整个点区间集合按照左边界展开排序，致使来寻找相互重叠的区间
        sort(points.begin(), points.end(), cmp);

        // 先将第一个区间入栈
        overlaps.push_back(points[0]);
        for(int i = 1; i < points.size(); i ++){
            // 发现两个区间有重叠，取其交集进行存储
            if(overlaps.back()[1] >= points[i][0]){
                overlaps.back()[0] = max(overlaps.back()[0], points[i][0]);
                overlaps.back()[1] = min(overlaps.back()[1], points[i][1]);
            }
            // 上一个处理好的区间与当前区间不重叠，直接存入
            else{
                overlaps.push_back(points[i]);
            }
        }
        // 这样就是按照贪心的思想将所有重叠区间的交集和不重叠的区间进行存储，其大小就是能够用的最少数量的箭
        return overlaps.size();
    }
};

// 方法二，没有使用数组进行存储
class Solution {
public:
    static bool cmp(vector<int>& point1, vector<int>& point2){
        // 按照左边界排序
        return point1[0] < point2[0];
    }

    int findMinArrowShots(vector<vector<int>>& points) {
        // 如果当前点的区间数为0直接返回0
        if(points.empty())
            return 0;

        int ans = 1;
        // 将整个点区间集合按照左边界展开排序，致使来寻找相互重叠的区间
        sort(points.begin(), points.end(), cmp);

        int start = points[0][0];
        int end = points[0][1];

        for(int i = 1; i < points.size(); i ++){
            // 发现两个区间有重叠，取其交集进行存储
            if(end >= points[i][0]){
                start = max(start, points[i][0]);
                end = min(end, points[i][1]);
            }
            // 上一个处理好的区间与当前区间不重叠
            else{
                start = points[i][0];
                end = points[i][1];
                ans ++;
            }
        }
  
        return ans;
    }
};

7. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增

示例 1:

1
2
输入: n = 10
输出: 9

示例 2:

1
2
输入: n = 1234
输出: 1234

示例 3:

1
2
输入: n = 332
输出: 299
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int monotoneIncreasingDigits(int n){
        string numStr = to_string(n);
        // 记录需要处理位数的分界点
        int flag = numStr.size();
        // 从前向后遍历，一直比较相邻两个数字的大小关系，当前面的数比后面的数大的时候，这时需要做一个标记，并且保证找到的单调递增数是最大的，所以此时先将前一个数减一，可以将后一个数赋为9，但是防止1000这种更新出错的情况，在每次检查出有不是单调递增的，这时需要进行标记，因为如果一个数在中间出现不是单调递增的情况，这时后面的全部数都应该更新为9
        for(int i = numStr.size() - 1; i > 0; i --){
            if(numStr[i - 1] > numStr[i]){
                numStr[i - 1] --;
                flag = i;
            }
        }
        // 按照最后一个不是单调递增的情况的标识位进行将所有后面的位全部更新为9，这这样保证最后所得的单调数字是最大的
        for(int j = flag; j < numStr.size(); j ++){
            numStr[j] = '9';
        }
        return stoi(numStr);
    }
};

8. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

1
2
3
4
5
6
7
8
9
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
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
// 如果x到不了y+1（但能到y），那么从x到y的任一点出发都不可能到达y+1。因为从其中任一点出发的话，相当于从0开始加油，而如果从x出发到该点则不一定是从0开始加油，可能还有剩余的油。既然不从0开始都到不了y+1，那么从0开始就更不可能到达y+1了
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // 首先在成功环行过程中，油箱始终会有大于0的油量，整个环行过程的耗油量大于总的油站存油量，则说明一定不能成功环行，为了使汽车从起点到终点，则最后的到达终点的剩油量一定是最少的
        // 累加差值最低点表示从0点出发 到达这个位置缺少的油量最多（假设为行程1），那么如果想要能顺利通过行程1，就需要在开启这段行程之前剩余尽可能多的油， 所以如果加油的总量大于消耗的总量，从累加差值最低点的下一站出发才有可能回到原点。
        int currentSum = 0;  // 记录从可能的起点开始到当前站油箱累积的油量
        int generalSum = 0;  // 记录从开始总的油站存油量和总的耗油量之间的差距
        int start = 0;  // 记录可能的起点下标
        for(int i = 0; i < gas.size(); i ++){
            currentSum += (gas[i] - cost[i]);
            generalSum += (gas[i] - cost[i]);
            // 当油箱的油量小于0时，说明从当前下标之前开始的站点都无法完成整个环行，需要将可能的起点设置为该站点的下一个站点，重新再检测下一个站点作为起点的可行性
            if(currentSum < 0){
                start = i + 1;
                currentSum = 0;
            }
        }
        // 油站总的存油量小于汽车耗油量，则说明一定不能完成整个环行
        if(generalSum < 0)
            return -1;
        return start;
    }
};

// 暴力解法
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (int i = 0; i < cost.size(); i++) {
            int rest = gas[i] - cost[i]; // 记录剩余油量
            int index = (i + 1) % cost.size();
            while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）
                rest += gas[index] - cost[index];
                index = (index + 1) % cost.size();
            }
            // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
            if (rest >= 0 && index == i) return i;
        }
        return -1;
    }
};

8. k次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

1
2
3
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

1
2
3
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

1
2
3
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。局部最优可以推出全局最优。那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让数组和达到最大。那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大

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
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        // 将整个数组进行排序
        sort(nums.begin(), nums.end());
        // 记录负数的个数
        int negNum = 0;

        for(int i = 0; i < nums.size(); i ++){
            if(nums[i] > 0){
                break;
            }
            negNum ++;
        }
        // 当数组中的负数数量大于k时，说明可以将所有的负数转化为其绝对值
        if(negNum >= k){
            for(int i = 0; i < k; i ++){
                int temp = nums[i];
                nums[i] = -1 * temp;
            }
            return accumulate(nums.begin(), nums.end(), 0);
        }
        // 当数组中负数数量小于k时，先将所有的负数转化为其绝对值，再选择将最小的元素不断取反
        for(int i = 0; i < negNum; i ++){
                int temp = nums[i];
                nums[i] = -1 * temp;
        }

        int sum = accumulate(nums.begin(), nums.end(), 0);
        if((k - negNum) % 2 == 1)
            return sum - 2 * *min_element(nums.begin(), nums.end());
        return sum;
    }
};