- 浏览: 172685 次
- 性别:
- 来自: 济南
文章分类
最新评论
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代表障碍物,有障碍物的地方就是死路,同样采用动态规划的思想,只是多了一些限定条件,当为1时,我们就把当前点的值设定为0;当为0的时候,如果此时(i = 0或者j = 0)这时当前点的值等于它前面的点的值(相当于初始化的过程),如果此时(i > 0并且j > 0),动态转移方程为dp[i][j] = dp[i - 1][j] + dp[i][j - 1],(i >= 1, j >= 1)。代码如下:
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代表障碍物,有障碍物的地方就是死路,同样采用动态规划的思想,只是多了一些限定条件,当为1时,我们就把当前点的值设定为0;当为0的时候,如果此时(i = 0或者j = 0)这时当前点的值等于它前面的点的值(相当于初始化的过程),如果此时(i > 0并且j > 0),动态转移方程为dp[i][j] = dp[i - 1][j] + dp[i][j - 1],(i >= 1, j >= 1)。代码如下:
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; for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) { if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0; else if (i == 0 && j == 0) obstacleGrid[0][0] = 1; else if(i == 0) obstacleGrid[0][j] = obstacleGrid[0][j - 1]; else if(j == 0) obstacleGrid[i][0] = obstacleGrid[i - 1][0]; else obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; } return obstacleGrid[m - 1][n - 1]; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 221You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 447Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 426Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 550Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II...
Unique Paths II N-Queens N-Queens II Restore IP Addresses Combination Sum Combination Sum II Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump...
62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/03/09 70.Climbing Stairs, 198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 ...
1、记忆化 2、二维dp 3、滚动优化
II mod之后,可能数学公式就不能简单地给出答案了。但对我来说,其实和前一题没区别。动态规划处理这种问题,早就是牛刀杀鸡了。。 Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 ...
63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的子串 49.组字谜...
unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...
and present the Short Paths Crossings Algorithm (SPCA) that computes sets of paths with limited length from anonymous nodes taking into account their crossings. Empirical tests show that SPCA produces...
扩展矩阵leetcode ...uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
每周最后一个问题是hard挑战,只有那些想尝试的人。 第一周的问题 :hundred_points: 问题 关联 876.链表中间 1491....第2周的问题 :red_apple: 问题 ...1769.将所有球移动到每个盒子的... Unique Paths III难度:(困难)
uniquePaths = function(m, n) { let dp = new Array(m).fill(0).map(() => new Array(n)); // dp[r][c] represents the number of possible paths from row = 0, col = 0 to row = r, col = c for (let row = 0; ...
Stopped polluting consumer groups in zookeeper by not creating a unique consumer group name for the consumer-offset and log-end-offset listener at each client instantiation. Improved ...
unique 可选仅对一次拼写错误发出警告。 默认情况下,为false 。 产出 没有任何。 用法示例 uses : zwaldowski/cspell-action@v1 with : paths : " **/*.{md,js} " config : .github/workflows/cspell.json ...
leetcode正方体收藏TakeUforward-...Unique Paths Reverse Pairs (Leetcode) 从 GFG 中通过拼图(自行搜索) Day4: (Hashing) 2 Sum 问题 4 Sum 问题 Longest Consecutive Sequence Longest Subarray with 0 sum 给定
Part scientific exploration, part philosophy, this unique book touches upon such diverse topics as dark matter, Feynman's "sum over paths", the quantum observer, and the soul. It is aimed at anyone ...
Unique Paths 这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见...
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 ...47/46....54/59....63/62.Unique Paths 2 64.最小路径和
<br>http://www.auerbach-publications.com/home.asp<br><br><br><br>Product Description<br>Network security development and implementation efforts involve the integration of technologies from seemingly unrelated fields that did not previously have to cross paths or internetwork. Areas such as cryptography, network protocols, and switch and router technology each have established theories and practices; developing expertise in ...
7) Save the BDF as a unique filename. 8) Set the BDF as your top level entity by clicking: Project -> Set as Top-Level Entity 9) Recompile the Quartus II project. For more information and ...
62.unique-paths.cpp [TODO] 5. 最长回文子串.cpp 第 3 天: [TODO] 96.unique-binary-search-trees.cpp [TODO] 70. 爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 ...