新人公眾號(hào)(求支持)：bigsai 專注于Java、數(shù)據(jù)結(jié)構(gòu)與算法，一起進(jìn)大廠不迷路！
算法文章題解全部收錄在github倉(cāng)庫(kù)bigsai-algorithm,求star！
關(guān)注這個(gè)瀟灑青年一起飛，回復(fù)進(jìn)群即可加入力扣打卡群，歡迎劃水。近期打卡：
跟我打卡LeetCode 61旋轉(zhuǎn)鏈表&62不同路徑&63不同路徑 II
打卡LeetCode 65有效數(shù)字&66加一 &67二進(jìn)制求和
LeetCode 67二進(jìn)制求和&68文本左右對(duì)齊&69x的平方根
如有幫助，記得對(duì)本文一鍵三連！

LeetCode 70爬樓梯

題目描述：

分析：
入門dp，狀態(tài)轉(zhuǎn)移方程為：初始賦值好后，dp[i]=dp[i-1]+dp[i-2];

public int climbStairs(int n) {if(n<3)return n;int dp[]=new int[n+1];dp[1]=1;dp[2]=2;for(int i=3;i<n+1;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}

另外，本題還可以使用兩個(gè)變量替代數(shù)組去優(yōu)化空間

LeetCode 71 簡(jiǎn)化路徑

題目描述

以 Unix 風(fēng)格給出一個(gè)文件的絕對(duì)路徑，你需要簡(jiǎn)化它。或者換句話說，將其轉(zhuǎn)換為規(guī)范路徑。

在 Unix 風(fēng)格的文件系統(tǒng)中，一個(gè)點(diǎn)（.）表示當(dāng)前目錄本身；此外，兩個(gè)點(diǎn) （…） 表示將目錄切換到上一級(jí)（指向父目錄）；兩者都可以是復(fù)雜相對(duì)路徑的組成部分。更多信息請(qǐng)參閱：Linux / Unix中的絕對(duì)路徑 vs 相對(duì)路徑

請(qǐng)注意，返回的規(guī)范路徑必須始終以斜杠 / 開頭，并且兩個(gè)目錄名之間必須只有一個(gè)斜杠 /。最后一個(gè)目錄名（如果存在）不能以 / 結(jié)尾。此外，規(guī)范路徑必須是表示絕對(duì)路徑的最短字符串。

示例 1：

輸入："/home/" 輸出："/home" 解釋：注意，最后一個(gè)目錄名后面沒有斜杠。

示例 2：

輸入："/../" 輸出："/" 解釋：從根目錄向上一級(jí)是不可行的，因?yàn)楦悄憧梢缘竭_(dá)的最高級(jí)。

示例 3：

輸入："/home//foo/" 輸出："/home/foo" 解釋：在規(guī)范路徑中，多個(gè)連續(xù)斜杠需要用一個(gè)斜杠替換。

示例 4：

輸入："/a/./b/../../c/" 輸出："/c"

示例 5：

輸入："/a/../../b/../c//.//" 輸出："/c"

示例 6：

輸入："/a//bc/d//././/.." 輸出："/a/b/c"

分析

這題就是棧的應(yīng)用，通過棧遍歷放入目錄，在遍歷字符串的同時(shí)如果遇到/ 那么就考慮進(jìn)行操作。邏輯如下：

具體編寫代碼的時(shí)候，需要注意是否為最后一個(gè)字符和一些特殊情況(棧為空則別拋出)。

具體代碼為：

public String simplifyPath(String path) {Stack<String>stack=new Stack<String>();char ch[]=path.toCharArray();StringBuilder sBuilder=new StringBuilder();for(int i=0;i<ch.length;i++){if(ch[i]=='/'||i==ch.length-1){if(i==ch.length-1&&ch[i]!='/'){sBuilder.append(ch[i]);}if(sBuilder.length()==0||sBuilder.toString().equals(".")){}else if (sBuilder.toString().equals("..")) {if(!stack.isEmpty())stack.pop();}else if(sBuilder.length()>0){stack.push(sBuilder.toString());}sBuilder=new StringBuilder();} else {sBuilder.append(ch[i]);}}sBuilder=new StringBuilder("");for(String s:stack){sBuilder.append('/');sBuilder.append(s);}if(stack.isEmpty())return "/";return sBuilder.toString();}

LeetCode 72編輯距離(dp)

題目描述

給你兩個(gè)單詞 word1 和 word2，請(qǐng)你計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。

你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：

插入一個(gè)字符
刪除一個(gè)字符
替換一個(gè)字符

示例 1：

輸入：word1 = "horse", word2 = "ros" 輸出：3 解釋： horse -> rorse (將 'h' 替換為 'r') rorse -> rose (刪除 'r') rose -> ros (刪除 'e')

示例 2：

輸入：word1 = "intention", word2 = "execution" 輸出：5 解釋： intention -> inention (刪除 't') inention -> enention (將 'i' 替換為 'e') enention -> exention (將 'n' 替換為 'x') exention -> exection (將 'n' 替換為 'c') exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500 word1 和 word2 由小寫英文字母組成

分析
這題其實(shí)是有難度，筆者剛開始做的時(shí)候以為是最小公眾子序列(LCS),但是后來發(fā)現(xiàn)并不是但是還是有點(diǎn)聯(lián)系的，dp的思想很相似。

分析一下目的：

• word1字符串轉(zhuǎn)成word2字符串

分析一下操作：

• 插入一個(gè)字符
• 刪除一個(gè)字符
• 替換一個(gè)字符

即很可能兩個(gè)字符向上或者向下可能轉(zhuǎn)換成三種狀態(tài)(有三種方式至少)。如果從遞歸的思路思考這道題，從后往前遞推。

• 如果兩個(gè)字符相等，操作的次數(shù)直接向前推。
• 如果不相等，分別遞歸取最小的(修改，插入，刪除)

但是這樣明顯有很多次重復(fù)計(jì)算，超時(shí)，你可以使用記憶化：即用數(shù)組將對(duì)應(yīng)遞歸編號(hào)的值記錄下來，如果數(shù)組有值，那么不需要遞歸重復(fù)計(jì)算，否則計(jì)算完將值賦值到該位置。這樣可以避免大量重復(fù)計(jì)算。

但是我們這題可以使用動(dòng)態(tài)規(guī)劃的思路，從前往后看。用dp[i][j]表示word1的前i個(gè)轉(zhuǎn)成word2的前j個(gè)需要轉(zhuǎn)動(dòng)的次數(shù)。動(dòng)態(tài)規(guī)劃的核心就是初始化和狀態(tài)方程。

• 對(duì)于初始化，如果一個(gè)串串長(zhǎng)度為0，編程另一個(gè)串串，那么肯定只有插入和刪除這兩種操作。并且初始化次數(shù)和字符串的長(zhǎng)度一致。

• 對(duì)于狀態(tài)轉(zhuǎn)移方程

  如果a[i]==b[j]那么說明這個(gè)字符相等不需要操作，總次數(shù)還是前面a[0-(i-1)]和b[0-(j-1)]串操作的次數(shù)。

  如果a[i]！=b[j]那么就有三種可能取最小的啦并且加一 dp[i][j]=Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]))+1;

具體可以參考下圖：

實(shí)現(xiàn)代碼：

public int minDistance(String word1, String word2) {char ch1[]=word1.toCharArray();char ch2[]=word2.toCharArray();if(word1.length()==0)return word2.length();if(word2.length()==0)return word1.length();int dp[][]=new int[ch1.length+1][ch2.length+1];for(int i=1;i<ch1.length+1;i++){dp[i][0]=i;}for(int j=1;j<ch2.length+1;j++){dp[0][j]=j;}for(int i=1;i<ch1.length+1;i++){for(int j=1;j<ch2.length+1;j++){if(ch1[i-1]==ch2[j-1]){dp[i][j]=dp[i-1][j-1];}else {dp[i][j]=Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]))+1;}}}return dp[ch1.length][ch2.length]; }

結(jié)語

原創(chuàng)不易，bigsai請(qǐng)你幫兩件事幫忙一下:

star支持一下， 您的肯定是我在平臺(tái)創(chuàng)作的源源動(dòng)力。

微信搜索「bigsai」，關(guān)注我的公眾號(hào)，不僅免費(fèi)送你電子書，我還會(huì)第一時(shí)間在公眾號(hào)分享知識(shí)技術(shù)。加我還可拉你進(jìn)力扣打卡群一起打卡LeetCode。

記得關(guān)注、咱們下次再見！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 70爬楼梯71简化路径72编辑距离(dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。