LeetCode 63. Unique Path II(所有不同路径之二)
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.
题目标签:Array
题目给了我们一个matrix,里面1代表有障碍物,0代表空。这道题目和Unique Path 基本一样。之前我们是给start point 1的值,然后遍历matrix,拿left 和 top的值加起来。那么这题,1被用了,代表障碍物。那我们就用-1。首先来分析一下,如果起点或者终点都是1的话,那么就无路可走,直接return 0就可以。剩下的情况,对于每一个点,如果它是障碍物,就直接跳过;如果不是,那么拿left 和top 的加一起,那如果left 和 top 有障碍物的话,也跳过。最后把终点的值 * -1 就可以了。
当然,也可以另外新建一个matrix,过程是同样的方法,不同的是当这个点是1的话,就把这个点的值等于0。 这方法就需要多建一个matrix。
Java Solution:
Runtime beats 14.83%
完成日期:07/21/2017
关键词:Array
关键点:Dynamic Programming, 逆向思考
public class Solution
{
public int uniquePathsWithObstacles(int[][] obstacleGrid)
{
if(obstacleGrid[0][0] == 1 ||
obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1] == 1) // obstacle at start point or finish point
return 0; obstacleGrid[0][0] = -1; // start point for(int i=0; i<obstacleGrid.length; i++) // row
{
for(int j=0; j<obstacleGrid[0].length; j++) // column
{
// if this is not obstacle
if(obstacleGrid[i][j] !=1)
{
// get left: left is not obstacle
if(j-1 >=0 && obstacleGrid[i][j-1] !=1)
obstacleGrid[i][j] += obstacleGrid[i][j-1];
// get top: top is not obstacle
if(i-1 >=0 && obstacleGrid[i-1][j] !=1)
obstacleGrid[i][j] += obstacleGrid[i-1][j];
} }
} return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1] * -1;
}
}
参考资料:N/A
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
最新文章
- git 使用
- iOS:给Git仓库上传代码时,超过100M会被拒绝(例如github和oschina)
- 浏览器html页面乱码问题分析
- GridView 控件中如何绑定 CheckBoxList
- Progress Reporting
- 二分图 最大权匹配 km算法
- 使用vhd灌装系统&mdash;&mdash;测试系统专用
- install samba on crux without net.
- SQL SERVER——CPU问题定位与解决
- git的安装和环境配置过程(学习笔记)
- AndroidStudio R 文件标红
- CDH安装系统环境准备——虚拟机网络配置
- 【codeforces 698B】 Fix a Tree
- JQuery小知识
- 雷林鹏分享:jQuery EasyUI 数据网格 - 创建复杂工具栏
- .NET C# 创建WebService服务简单的例子
- JVM学习总结(一):Java内存区域
- 【转】asp.net项目在IE11下出现“__doPostBack”未定义的解决办法
- 查找xml中的接口名及涉及表名并输出
- jenkins 自动触发
热门文章
- Hyperledger Fabric 1.0 从零开始(一)——吐槽
- ng-model值字符串转数值型(convertToNumber directive)
- LINUX通过PXE自动部署系统
- JAVA多线程---wait() &; join()
- PLT文件 和 DXF文件
- Count(*), Count(1) 和Count(字段)的区别
- 使用LayUI操作数据表格
- Sets 比赛时想错方向了。。。。 (大数不能处理负数啊)
- Struts 关联DTD 文件
- 如何在maven pom.xml文件中设置Java编译器版本