leetcode刷题记录03（2023-04-06）【跳跃游戏(队列+理解题意) | 合并区间(模拟) | 不同路径(二维dp) | 最小路径和(二维dp)】

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

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

示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：
$1<=nums.length<=3?104$
$0<=nums[i]<=105$

要想明白几个点：

1. 对于任何一个位置，它能覆盖的位置为 $i+nums[i]$；
2. 跳跃者能触碰到的范围一定是连续的，不会出现中间断开的情况，因为跳跃着可以跳 $<nums[i]$ 长度的任意长度的距离。

#include<vector>
#include<queue>
#include<iostream>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        queue<int> que;
        que.push(0);
        int end = 0;
        int secondEnd = 0;
        while (!que.empty()) {
            if (que.front() + nums[que.front()] > end) {
                secondEnd = end;
                end = max(end, que.front() + nums[que.front()]);
                if (end >= nums.size() - 1) {
                    return true;
                }
                int i = secondEnd + 1;
                while (i <= end) {
                    que.push(i);
                    i++;
                }
            }
            que.pop();            
        }
        return end >= nums.size() - 1;
    }
};

int main() {
    /*vector<int> vec = { 2,3,1,1,4 };*/
    /*vector<int> vec = { 3,2,1,0,4 };*/
    vector<int> vec = { 1 };
    Solution sol;
    bool res = sol.canJump(vec);
    cout << res;
}

自己写的代码好冗余，而且空间复杂度为O(n)，看了题解，感觉代码十分简单。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) return false;
            k = max(k, i + nums[i]);
        }
        return true;
    }
};

56. 合并区间

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

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

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

提示：
$1<=intervals.length<=104$
$intervals[i].length==2$
$0<=starti<=endi<=104$

解这道题目的关键就是排序，排序好之后，如果下一个区间的开始值小于上一个区间的结束值，那么就合并。否则，就新添加一个区间。

#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [&](vector<int> a, vector<int> b) {
            return a[0] < b[0];
            });
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] > res[res.size() - 1][1]) {
                res.push_back(intervals[i]);
            }
            else {
                res[res.size() - 1][1] = max(res[res.size() - 1][1], intervals[i][1]);
            }
        }
        return res;
    }
};

int main() {
    /*vector<vector<int>> vec = { {1,3} ,{2,6},{8,10},{15,18} };*/
    vector<vector<int>> vec = { {1,4} ,{4,5} };
    Solution sol;
    vector<vector<int>> res = sol.merge(vec);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
}

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6

提示：
$1<=m,n<=100$
题目数据保证答案小于等于 $2?10^9$

这道题目的思路是，因为只能向下和向右走，所以当前块的路径次数，必然等于左边的块的次数+上面的块的次数。

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

int main() {
    Solution sol;
    cout << sol.uniquePaths(3, 7);
}

这道题的代码看起来很美~

题解¹有用排列组合来做，时间复杂度也是O(n)，但是空间复杂度会降低一些，到O(1)。

因为机器到底右下角，向下几步，向右几步都是固定的，比如，m=3, n=2，我们只要向下 1 步，向右 2 步就一定能到达终点。

所以有
$$C_{m+n?2}^{m?1}?$$

题解给的是 Python 代码，如下：

def uniquePaths(self, m: int, n: int) -> int:
        return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：
$m==grid.length$
$n==grid[i].length$
$1<=m,n<=200$
$0<=grid[i][j]<=100$

这道题目和上面的不同路径很像。只能向右和向下走，那么最短路径一定来源于左边或者上边。

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

int main() {
    vector<vector<int>> vec = { {1,3,1} ,{1,5,1},{4,2,1} };
    Solution sol;
    cout << sol.minPathSum(vec);
}

---

1. https://leetcode.cn/problems/unique-paths/solution/dong-tai-gui-hua-by-powcai-2/ ??