【LeetCode-面试算法经典-Java实现】【063-Unique Paths II(唯一路径问题II)】
2024-08-31 16:09:23
【063-Unique Paths II(唯一路径问题II)】
【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】
原题
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
.
题目大意
唯一路径问题兴许。假设路径中有障碍,求总的路径的种数。
【唯一路径问题】
注意:网格的行数和列数都不超过100
解题思路
採用分治求解方法
用一个m*n的组数A保存结果。
对于A数组中的元素有。
1、当x=0或者y=0时。而且(x, y)位置无障碍。
有A[x][y] = 1。 有障碍就是0
2、当x>=1而且y>=1时,而且(x, y)位置无障碍。
有A[x][y] = A[x-1][y]+A[x][y-1]。 有障碍就是0
3、所求的结点就是A[m-1][n-1]。
代码实现
算法实现类
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 输入校验
if (obstacleGrid == null || obstacleGrid.length < 1 || obstacleGrid[0].length < 1
|| obstacleGrid[0][0] == 1
|| obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
return 0;
}
int rows = obstacleGrid.length;
int cols = obstacleGrid[0].length;
int[][] result = new int[rows][cols];
// 第一个位置有多少种方法。无障碍就是1种,有障碍就是0种
result[0][0] = obstacleGrid[0][0] == 0 ?
1 : 0;
for (int i = 1; i < cols; i++) {
result[0][i] = obstacleGrid[0][i] == 0 ? result[0][i - 1] : 0;
}
for (int i = 1; i < rows; i++) {
result[i][0] = obstacleGrid[i][0] == 0 ? result[i - 1][0] : 0;
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
result[i][j] = obstacleGrid[i][j] == 0 ?
result[i - 1][j] + result[i][j - 1] : 0;
}
}
return result[rows - 1][cols - 1];
}
// 使用递归方法会超时
public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
// 输入校验
if (obstacleGrid == null || obstacleGrid.length < 1 || obstacleGrid[0].length < 1
|| obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
return 0;
}
int[] result = {0};
solve(obstacleGrid, 0, 0, result);
return result[0];
}
public void solve(int[][] grid, int row, int col, int[] sum) {
// 到达终点
if (row == grid.length - 1 && col == grid[0].length - 1) {
sum[0]++;
}
// 没有到终点,点在棋盘内。而且当前位置不是
else if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == 0) {
// 往右走
solve(grid, row, col + 1, sum);
// 往下走
solve(grid, row + 1, col, sum);
}
}
}
评測结果
点击图片,鼠标不释放,拖动一段位置,释放后在新的窗体中查看完整图片。
特别说明
欢迎转载,转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47182723】
最新文章
- 动作手游实时PVP技术揭密(服务器篇)
- Git入门
- yum:在Red Hat和Fedora中使用
- docker镜象
- CRUD Operations in MVC4 Using AngularJS and WCF REST Services
- JavaScript判断文件的大小
- java返回参数中几种常见的方法
- CTE Recursion Performance
- MSSQL显错注入爆数字型数据的一点思考
- zabbix 对于logstash告警连续发邮件
- hdu2289Cup(神坑题,精度+二分,以半径二分不能过,以高度为二分就过了)
- Vue列表过渡
- AJAX使用说明书
- 彻底关闭windows10自动更新解决方案
- 机器学习实战ch04 关于python版本所支持的文本格式问题
- (21/24) webpack实战技巧:webpack对三方类库的优化操作
- BZOJ4811 [Ynoi2017]由乃的OJ 树链剖分
- 护眼党必备良心app
- 【原创】<;Debug>; “duplicate connection name”
- Phabricator代码审核Audit用户指南