55. 跳跃游戏【中等】
55.跳跃游戏
中等
2.4K
相关企业
给定一个非负整数数组 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
官方
class Solution { //方法1.2 可以到达最远位置 public boolean canJump(int[] nums) { int reach=0; int n=nums.length; for(int i=0;i<=reach&&reach<n-1;i++){ reach=Math.max(i+nums[i],reach); } return reach>=n-1; } }
官方
class Solution { //方法2 最早开始的位置 public boolean canJump(int[] nums) { int n=nums.length; int last=n-1; for(int i=n-2;i>=0;i--){ if(i+nums[i]>=last) last=i; } return last==0; } }
56. 合并区间【中等】
56.合并区间
中等
1.9K
相关企业
以数组 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
https://yzhyaa.blog.csdn.net/article/details/109033262
class Solution { public int[][] merge(int[][] intervals) { // 注：这里是通过List<int[]>来保存二维数组的； // 通过List#add很方便；但在最后返回时要toArray(new int[0][])表示放到一个二维数组 List<int[]> res = new ArrayList<>(); if(intervals.length == 0 || intervals == null) return res.toArray(new int[0][]); // 1.排序 // 这里通过lamada用函数式接口，实现了Comptor接口；表示比较两个一维数组i1，i2通过i[0]比较 Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]); // 2.初始区间 int start = intervals[0][0], end = intervals[0][1]; // 3.创建区间 for(int[] arr:intervals){ if(arr[0]<=end){ end=Math.max(end,arr[1]); }else{ res.add(new int[]{start,end}); start=arr[0]; end=arr[1]; } } // 4.剩余处理 res.add(new int[]{start, end}); return res.toArray(new int[0][]); } }
62. 不同路径【中等】
62.不同路径
中等
1.8K
相关企业
一个机器人位于一个 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 * 109
动态规划
class Solution { public int uniquePaths(int m, int n) { int [][] f=new int[m][n]; for(int i=0;i<m;i++){ f[i][0]=1; } for(int j=0;j<n;j++){ f[0][j]=1; } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ f[i][j]=f[i-1][j]+f[i][j-1]; } } return f[m-1][n-1]; } }
64. 最小路径和【中等】
64.最小路径和
中等
1.5K
相关企业
给定一个包含非负整数的 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] <= 200
自己
动态规划
class Solution { //动态规划 public int minPathSum(int[][] grid) { int m=grid.length; int n=grid[0].length; int [][] dp=new int[m][n]; dp[0][0]=grid[0][0]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0&&j-1>=0){ dp[0][j]=dp[0][j-1]+grid[0][j]; }else if(j==0&&i-1>=0){ dp[i][0]=dp[i-1][0]+grid[i][0]; }else if(i-1>=0&&j-1>=0){ dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } } return dp[m-1][n-1]; } }
70. 爬楼梯【简单】
70.爬楼梯
提示
简单
3.1K
相关企业
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1： 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2： 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
1 <= n <= 45
斐波那契数列
动态规划
class Solution { public int climbStairs(int n) { int p = 0, q = 0, r = 1; for (int i = 1; i <= n; ++i) { p = q; q = r; r = p + q; } return r; } }
72. 编辑距离【困难】
72.编辑距离
困难
3K
相关企业
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1： 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 示例 2： 输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
参考
动态规划
class Solution { public int minDistance(String word1, String word2) { int n=word1.length(); int m=word2.length(); //有一个字符串为空串 if(n*m==0){ return n+m; } //DP数组 int [][] D=new int[n+1][m+1]; //边界状态初始化 for(int i=0;i<n+1;i++){ D[i][0]=i; } for(int j=0;j<m+1;j++){ D[0][j]=j; } //计算所有DP值 for(int i=1;i<n+1;i++){ for(int j=1;j<m+1;j++){ int left=D[i-1][j]+1; int down=D[i][j-1]+1; int left_down=D[i-1][j-1]; if(word1.charAt(i-1)!=word2.charAt(j-1)){ left_down+=1; } D[i][j]=Math.min(left,Math.min(down,left_down)); } } return D[n][m]; } }
