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

2023-12-28 14:47:02

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 < = n u m s . l e n g t h < = 3 ? 104 1 <= nums.length <= 3 * 104 1<=nums.length<=3?104
0 < = n u m s [ i ] < = 105 0 <= nums[i] <= 105 0<=nums[i]<=105

要想明白几个点:

  1. 对于任何一个位置,它能覆盖的位置为 i + n u m s [ i ] i + nums[i] i+nums[i]
  2. 跳跃者能触碰到的范围一定是连续的,不会出现中间断开的情况,因为跳跃着可以跳 < n u m s [ i ] <nums[i] <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 < = i n t e r v a l s . l e n g t h < = 104 1 <= intervals.length <= 104 1<=intervals.length<=104
i n t e r v a l s [ i ] . l e n g t h = = 2 intervals[i].length == 2 intervals[i].length==2
0 < = s t a r t i < = e n d i < = 104 0 <= starti <= endi <= 104 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 1 <= m, n <= 100 1<=m,n<=100
题目数据保证答案小于等于 2 ? 1 0 9 2 * 10^9 2?109

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

#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);
}

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

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

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

所以有
C m + n ? 2 m ? 1 ? C_{m+n?2}^{m?1} ? Cm+n?2m?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 = = g r i d . l e n g t h m == grid.length m==grid.length
n = = g r i d [ i ] . l e n g t h n == grid[i].length n==grid[i].length
1 < = m , n < = 200 1 <= m, n <= 200 1<=m,n<=200
0 < = g r i d [ i ] [ j ] < = 100 0 <= grid[i][j] <= 100 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/ ??

文章来源:https://blog.csdn.net/myf_666/article/details/129997243
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。