文档章节

63. Unique Paths II

JiaMing
 JiaMing
发布于 07/10 00:16
字数 619
阅读 55
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

题目: 63. Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

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.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

解题思路

这道题是62. Unique Path的升级版,相对于62. Unique Path来说,只是多了障碍的情况。所以其实解法和62. Unique Path类似(参考 https://my.oschina.net/JiamingMai/blog/4348177 ),只是唯一不同的是,将有障碍的地方的h()都设为0,例如假设(i, j)这个位置有障碍物,那么h(i, j)=0,表示(i, j)这个位置到达右下角的可行路径数为0,即到达不了右下角。

值得注意的是,有一种特殊情况:右下角有障碍物。例如输入的数组为[[1]],这个时候应该返回0,所以要排除这种右下角有障碍物的情况,当右下角有障碍物时,应该直接返回0,因为无论如何永远无法到达右下角。

时间复杂度

与62. Unique Path一样,都为O(mn),具体分析过程参考 https://my.oschina.net/JiamingMai/blog/4348177

最终实现

Java 实现

// Input: [[1]]
// Expected: 0
public class Solution {

    private int h[][];

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (null == obstacleGrid || obstacleGrid.length <= 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // initialize the two-dimension array h
        h = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                h[i][j] = obstacleGrid[i][j] != 1 ? -1 : 0;
            }
        }
        // return 0 because the right-bottom position is blocked
        if (h[m-1][n-1] == 0) {
            return 0;
        }
        // set the right-bottom position to 1
        h[m-1][n-1] = 1;
        return calcH(0, 0);
    }

    private int calcH(int i, int j) {
        int m = h.length;
        int n = h[0].length;
        if (i >= m || j >= n) {
            return 0;
        }
        if (h[i][j] != -1) {
            return h[i][j];
        }
        h[i][j] = calcH(i + 1, j) + calcH(i, j + 1);
        return h[i][j];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int m = 1;
        int n = 1;
        int[][] obstacleGrid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                obstacleGrid[i][j] = 0;
            }
        }
        obstacleGrid[0][0] = 1;
        int res = solution.uniquePathsWithObstacles(obstacleGrid);
        System.out.println(res);
    }

}

 

上一篇: 263. Ugly Number
下一篇: 62. Unique Paths
JiaMing
粉丝 8
博文 57
码字总数 37622
作品 0
广州
私信 提问
加载中
请先登录后再评论。
Flappy Bird(安卓版)逆向分析(一)

更改每过一关的增长分数 反编译的步骤就不介绍了,我们直接来看反编译得到的文件夹 方法1:在smali目录下,我们看到org/andengine/,可以知晓游戏是由andengine引擎开发的。打开/res/raw/at...

enimey
2014/03/04
6K
18
XUI Lib

XUI 是一个高效、灵活易用的 Windows UI 库,使用 C++ 编写,基于 ATL 库。 Features: Layout by XML. Full basic controls: Static, Button, Edit, List (by aggregation), Tree, Animation......

匿名
2012/11/29
1.4W
0
Sliding Grid View

SlidingGridView 是一个表格组件,支持滑动动画效果:更新单元格从上到小替换老的内容。 特点: 1. Unique sliding animation. 2. Shake to refresh. 3. Mimics "load more..." items. 4. Ab......

匿名
2012/12/24
659
0
如何写程序自动下载BBC Learning English的所有在线课程

BBC Learning English在线3大系列课程:Lower intermediate、Intermediate、English My Way 声音很悦耳,尤其是Jamaica Inn和The Importance of Being Earnest,堪称完美,百听不厌,这对于英...

杨尚川
2015/10/21
1.9K
3
Python 中的枚举类型

枚举类型可以看作是一种标签或是一系列常量的集合,通常用于表示某些特定的有限集合,例如星期、月份、状态等。Python 的原生类型(Built-in types)里并没有专门的枚举类型,但是我们可以通...

rainyear
2016/04/30
2.3K
0

没有更多内容

加载失败,请刷新页面

加载更多

jQuery Ajax调用后如何管理重定向请求 - How to manage a redirect request after a jQuery Ajax call

问题: I'm using $.post() to call a servlet using Ajax and then using the resulting HTML fragment to replace a div element in the user's current page. 我使用$.post()使用Ajax调用......

javail
59分钟前
15
0
没有指定分支的“git push”的默认行为 - Default behavior of “git push” without a branch specified

问题: I use the following command to push to my remote branch: 我使用以下命令推送到我的远程分支: git push origin sandbox If I say 如果我说 git push origin does that push ch......

技术盛宴
今天
21
0
为什么在允许某些Unicode字符的注释中执行Java代码?

问题: The following code produces the output "Hello World!" 以下代码生成输出“Hello World!” (no really, try it). (不,真的,试试吧)。 public static void main(String... args......

富含淀粉
今天
18
0
什么是按位移位(位移)运算符以及它们如何工作? - What are bitwise shift (bit-shift) operators and how do they work?

问题: I've been attempting to learn C in my spare time, and other languages (C#, Java, etc.) have the same concept (and often the same operators) ... 我一直在尝试在业余时间学习......

法国红酒甜
今天
32
0
OSChina 周二乱弹 —— 卧槽 李荣浩的契约兽啊

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《红色的回忆》- 痛仰乐队 手机党少年们想听歌,请使劲儿戳(这里) 动弹, 又好多...

小小编辑
今天
92
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部