[LeetCode][Java] Unique Paths II
2023-09-11 14:14:59 时间
题目:
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1
and 0
respectively
in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2
.
Note: m and n will be at most 100.
题意:
紧跟着题目《Unique Paths》,现给出这样一题目:
假设在格子中加入一些障碍,会出现多少存在且唯一的不同路径呢?
障碍和空白格子分别被标记为1
and 0
.
比方一个3x3的格子中的中间存在一个障碍,例如以下所看到的:
[ [0,0,0], [0,1,0], [0,0,0] ]总的路径数为2.
算法分析:
思路与题目《Unique Paths》类似,不同之处为:
初始化边界上行和列时,出现障碍。后面路径数dp的都是0
中间的格子出现障碍时,该格子dp表示的路径数直接填0
AC代码:
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { if(obstacleGrid==null||obstacleGrid.length==0) return 0; int m = obstacleGrid.length; int n = obstacleGrid[0].length; int [][] dp = new int[m][n]; for(int i = 0; i < m; i++) { if(obstacleGrid[i][0]!=1) dp[i][0] = 1; else break; } for(int j = 0; j < n; j++) { if(obstacleGrid[0][j]!=1) dp[0][j] = 1; else break; } for(int i = 1; i < m; i++) { for(int j = 1; j< n; j++) { if(obstacleGrid[i][j]!=1) dp[i][j] = dp[i-1][j] + dp[i][j-1]; else dp[i][j]=0; } } return dp[m-1][n-1]; } }
相关文章
- JAVA学习(五):Java面向对象编程基础
- Java实现 LeetCode 838 推多米诺(暴力模拟)
- Java实现 LeetCode 685 冗余连接 II(并查集+有向图)
- Java实现 LeetCode 667 优美的排列 II(暴力)
- Java实现 LeetCode 454 四数相加 II
- Java实现 LeetCode 454 四数相加 II
- Java实现 LeetCode 445 两数相加 II
- Java实现 LeetCode 324 摆动排序 II
- Java实现 LeetCode 283 移动零
- Java实现 LeetCode 240 搜索二维矩阵 II(二)
- Java实现 LeetCode 225 用队列实现栈
- Java实现 LeetCode 154 寻找旋转排序数组中的最小值 II(二)
- Java实现 LeetCode 140 单词拆分 II(二)
- Java实现 LeetCode 140 单词拆分 II(二)
- Java实现 LeetCode 128 最长连续序列
- Java实现 LeetCode 126 单词接龙 II
- Java实现 LeetCode 122 买卖股票的最佳时机 II
- Java实现 LeetCode 119 杨辉三角 II
- Java实现 LeetCode 117 填充每个节点的下一个右侧节点指针 II(二)
- Java实现 LeetCode 100 相同的树
- Java实现 LeetCode 95 不同的二叉搜索树 II(二)
- Java实现 LeetCode 57 插入区间
- Java实现LeetCode_0026_RemoveDuplicatesFromSortedArray
- Java实现 LeetCode 240 搜索二维矩阵 II
- Java实现 LeetCode 212 单词搜索 II
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- 【JAVA】java中split以"." 、""、“|”分隔字符串