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