java LeetCode題解不同路徑
題目描述
一個機(jī)器人位于一個m×n網(wǎng)格的左上角。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖到達(dá)網(wǎng)格的右下角 。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角 將會有多少條不同的路徑呢？
網(wǎng)格中的障礙物和空位置分別用1和0表示。
示例
來自LeetCode
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網(wǎng)格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
方法思路
同前面的不同路徑解法一樣，最優(yōu)方法是采用動態(tài)規(guī)劃。
此處同時采用滾動數(shù)組優(yōu)化空間。
我們用f(i,j)來表示從坐標(biāo)(0,0)到坐標(biāo)(i,j)的路徑數(shù)，u(i,j)表示坐標(biāo)(i,j)是否可行，如果坐標(biāo)(i,j)有障礙物，u(i,j)=0，否則u(i,j)=1。
因?yàn)闄C(jī)器人只能向下或者向右移動，所以坐標(biāo)(0,0)到坐標(biāo)(i,j)的路徑總數(shù)的值只能取決于坐標(biāo)(0,0)到坐標(biāo)(i-1,j)的路徑總數(shù)和從坐標(biāo)(0,0)到坐標(biāo)(i,j-1)的路徑總數(shù)，即f(i,j)只能通過f(i-1,j)和坐標(biāo)f(i,j-1)轉(zhuǎn)移得到。當(dāng)坐標(biāo)(i,j)本身有障礙物的時候，
任何路徑都到不了f(i,j)，此時f(i,j)=0。
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
int[] f = new int[m];
f[0]= obstacleGrid[0][0]==0?1:0;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(obstacleGrid[i][j]==1){
f[j]=0;
continue;
}
if(j>=1&&obstacleGrid[i][j-1]==0){
f[j]+=f[j-1];
}
}
}
return f[m-1];
}
}復(fù)雜度分析
- 時間復(fù)雜度：O(nm),其中n為網(wǎng)格的行數(shù)，m為網(wǎng)格的列數(shù)。
- 空間復(fù)雜度：O(m)。利用滾動數(shù)組優(yōu)化，我們可以只用O(m)大小的空間來記錄當(dāng)前行的通路值。
以上就是java LeetCode題解不同路徑的詳細(xì)內(nèi)容，更多關(guān)于java LeetCode不同路徑的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
基于Spring中的事務(wù)@Transactional細(xì)節(jié)與易錯點(diǎn)、幻讀
這篇文章主要介紹了基于Spring中的事務(wù)@Transactional細(xì)節(jié)與易錯點(diǎn)、幻讀，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例講解
這篇文章主要介紹了Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例,棧的后進(jìn)先出和隊(duì)列的先進(jìn)先出是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的知識,本文則又對Java實(shí)現(xiàn)棧和隊(duì)列結(jié)構(gòu)的方法進(jìn)行了細(xì)分,需要的朋友可以參考下2016-04-04
有朋友說jpa相比mybatis太難用，多表聯(lián)合的查詢寫起來也比較費(fèi)勁，所以便加入了mybatis的支持，在配置jpa時遇到各種問題，需要修改相關(guān)配置文件，下面小編給大家分享下修改配置文件的思路，感興趣的朋友參考下2016-10-10
基于springboot微信公眾號開發(fā)(微信自動回復(fù))
這篇文章主要介紹了基于springboot微信公眾號開發(fā)(微信自動回復(fù)),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11
這篇文章主要為大家詳細(xì)介紹了一個簡單的Python名片管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
在Java中讀取硬件寄存器數(shù)據(jù)不直接支持,但可以通過JNI或JNA技術(shù)實(shí)現(xiàn),此過程需要編寫本地代碼（如C/C++）以模擬硬件交互,然后在Java中調(diào)用這些方法,注意,JNI使用可能引入復(fù)雜性和性能開銷,且需考慮跨平臺兼容性,感興趣的朋友跟隨小編一起看看吧2024-09-09
下面小編就為大家?guī)硪黄狫ava輸出打印工具類封裝的實(shí)例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
XML現(xiàn)在已經(jīng)成為一種通用的數(shù)據(jù)交換格式,平臺的無關(guān)性使得很多場合都需要用到XML。本文將詳細(xì)介紹用Java解析XML的四種方法2012-10-10
這篇文章主要介紹了SpringBoot登錄判斷代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-12-12
這篇文章主要介紹了如何使用java寫Student類的功能,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04