本周我們繼續來看5道磨人的小妖精，圖解leetcode6-10～
多說一句，leetcode10 殺死了233醬不少腦細胞...
另：
沉迷算法，無法自拔。快來加入我們吧！
别忘了233醬的一條龍服務：
公衆号文章題解 -> 私信答疑 -> 刷題群答疑 -> 視訊講解
我們的目的是成為套路王～
嘿嘿，廣告完畢 , Let's go!
leetcode6: Z 字形變換
題目描述：
将一個給定字元串根據給定的行數，以從上往下、從左到右進行 Z 字形排列。
題目示例:
輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"
解釋:
L D R
E O E I I
E C I H N
T S G
解題思路:
相信小夥伴看到這道題目，也和233一樣覺得Z字形排列的
字元串
冥冥中有些
規律
。為了友善解釋 ，我們假設輸入：
字元串s="0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15"
numRows=4
注意： s中的輸入字元依次為：為0-15，中間的空格是我為了展示清楚額外加的。
那麼s的Z字形排列如下：
需要輸出的結果是：“0 6 12 15 7 11 13 2 4 8 10 14 3 9 15”
假設我們将Z字形排列後的字元串每一行i 用一個數組arr[i]存起來，最後按行數i的順序輸出arr[i]中的值，那麼就可以得到最終的輸出結果。
如何知道字元串s中的各個字元在哪個arr數組的哪個索引位置呢？這就是我們用數字字元的字元串來舉例子的好處了，因為數字的值就對應着字元在字元串s中的下标。當我們周遊字元串s時，是我們可以用
pointer
表示目前周遊的字元所對應的行數i，代表這個字元是要放到arr[i]中的。
我們可以發現每當周遊numRows=4 個字元，pointer就從 0->3 轉化為 3->0。是以我們可以用一個
flag
記錄pointer的變化量。
思路有了，我們來看一下時間空間複雜度：
- 時間複雜度：周遊一遍字元串s: O(n)。
- 空間複雜度：數組arr的存儲：O(n)。
可以寫出代碼嗎：）
Java版本
class Solution {
public String convert(String s, int numRows) {
if(numRows <= 1){
return s;
}
List<StringBuilder> arr = new ArrayList<>();
for(int i = 0 ;i< numRows;i++){
arr.add(new StringBuilder());
}
int flag = -1;
int pointer = 0;
for(int i =0;i<s.length();i++){
char ch = s.charAt(i);
arr.get(pointer).append(ch);
if(pointer == 0 || pointer == numRows -1) flag = - flag;
pointer += flag;
}
StringBuilder res = new StringBuilder();
for(StringBuilder row : arr) res.append(row);
return res.toString();
}
}
leetcode7: 整數反轉
題目描述：
給出一個 32 位的有符号整數，你需要将這個整數中每位上的數字進行反轉。
題目示例:
輸入: 123
輸出: 321
輸入: -123
輸出: -321
輸入: 120
輸出: 21
注意:
假設我們的環境隻能存儲得下 32 位的有符号整數，則其數值範圍為 [−231, 231 − 1]。請根據這個假設，如果反轉後整數溢出那麼就傳回 0。
解題思路:
這道題考的還是 數學運算。
Step1:
需要分别取出十進制數字的個位，十位，百位..一直到最高位的數字。
阿姨來教你國小數學的除法運算：
是以當我們 取餘再取模 就可以得到高位的數字。
Step2:
将取出來的個位，十位，百位..一直到最高位的數字 依次放到 最高位,...,百位，十位，個位。
阿姨來教你國小數學的乘法運算：
至于示例中列舉的幾個邊界條件，Java中的整數是帶有符号的。剛好符合我們的乘除運算。
另外，需要判斷乘法計算時正負數字的越界問題。當然如果res用long表示，也就不需要考慮這個問題了。代碼如下：
Java版本
class Solution {
public int reverse(int x) {
int res = 0;
while(x!=0){
if(x>0 && res > ((Integer.MAX_VALUE-x%10)/10)) return 0;
if(x<0 && res < ((Integer.MIN_VALUE-x%10)/10)) return 0;
res = res*10 + x%10;
x/=10;
}
return res;
}
}
leetcode8: 字元串轉換整數(atoi)
題目描述：
請你來實作一個 atoi 函數，使其能将字元串轉換成整數。
首先，該函數會根據需要丢棄無用的開頭空格字元，直到尋找到第一個非空格的字元為止。接下來的轉化規則如下：
如果第一個非空字元為正或者負号時，則将該符号與之後面盡可能多的連續數字字元組合起來，形成一個有符号整數。
假如第一個非空字元是數字，則直接将其與之後連續的數字字元組合起來，形成一個整數。
該字元串在有效的整數部分之後也可能會存在多餘的字元，那麼這些字元可以被忽略，它們對函數不應該造成影響。
注意：假如該字元串中的第一個非空格字元不是一個有效整數字元、字元串為空或字元串僅包含空白字元時，則你的函數不需要進行轉換，即無法進行有效轉換。
在任何情況下，若函數不能進行有效的轉換時，請傳回 0 。
提示：
本題中的空白字元隻包括空格字元 ' ' 。
假設我們的環境隻能存儲 32 位大小的有符号整數，那麼其數值範圍為 [−231, 231 − 1]。如果數值超過這個範圍，請傳回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
題目示例:
示例 1:
輸入: "42"
輸出: 42
示例 2:
輸入: " -42"
輸出: -42
解釋: 第一個非空白字元為 '-', 它是一個負号。
我們盡可能将負号與後面所有連續出現的數字組合起來，最後得到 -42 。
示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉換截止于數字 '3' ，因為它的下一個字元不為數字。
示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個非空字元是 'w', 但它不是數字或正、負号。
是以無法執行有效的轉換。
示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 數字 "-91283472332" 超過 32 位有符号整數範圍。
是以傳回 INT_MIN (−231) 。
解題思路:
放這麼多 題目示例 阿姨并不是為了湊字數，而是這類問題就是屬于考邊界情況的問題，邊界情況拎清了，就不會被磨到了～
假設輸入一個字元串 " -4193 with words" ， 我們可以從左到右周遊這個字元串，用k 表示目前周遊到的字元：
另外，我們還需要注意 示例5的情況，當乘法計算時的值超過
INT_MAX or INT_MIN
時，結束并傳回 INT_MAX or INT_MIN.
Java版本
class Solution {
public int myAtoi(String str) {
int res = 0;
int k = 0;
while(k< str.length() && ' ' == str.charAt(k))k++;
int minus = 1;
if(str.length() == k) return res;
if('-' == str.charAt(k)) {
minus = -1;
k++;
}else if('+' == str.charAt(k)){
k++;
}
while(k<str.length() && str.charAt(k) >= '0' && str.charAt(k) <='9'){
int x = str.charAt(k) - '0';
if(minus >0 && res> (Integer.MAX_VALUE - x)/ 10){
return Integer.MAX_VALUE;
}
//-res * 10 - str.charAt(k) < Integer.MIN_VALUE
if(minus <0 && -res < (Integer.MIN_VALUE + x)/10)
return Integer.MIN_VALUE;
//最大的負數是存不下來的
if((-res * 10 - x) == Integer.MIN_VALUE ) {
return Integer.MIN_VALUE;
}
res = res* 10 + x;
k++;
}
res *= minus;
return res;
}
}
leetcode9: 回文數
題目描述：
判斷一個整數是否是回文數。回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。
題目示例:
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。是以它不是一個回文數。
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。是以它不是一個回文數。
解題思路:
上篇文章中我們講過最長回文子串的查找。再來看這道題就很easy了。這道題的解法也很多：
比如我們可以把它變為字元串。然後reverse一下，判斷前後兩個字元串是否相等。
但是我們用一種更簡單的方式，隻需要反轉整數，然後判斷兩個整數是否相等，就可以确定是不是回文整數。又回到leetcode7了，有沒有覺得阿姨的乘除法運算還是有幫助的：）
Java版本
class Solution {
public boolean isPalindrome(int x) {
if(x<0) return false;
if(x<=9) return true;
int oringin = x;
int res = 0;
while(x>0){
//如果越界了說明不對稱
res = res*10 + x%10;
x/=10;
}
return oringin == res;
}
}
leetcode10: 正規表達式比對
題目描述：
給你一個字元串 s 和一個字元規律 p，請你來實作一個支援 '.' 和 '*' 的正規表達式比對。
'.' 比對任意單個字元
'*' 比對零個或多個前面的那一個元素
所謂比對，是要涵蓋 整個 字元串 s的，而不是部分字元串。
說明:
- s 可能為空，且隻包含從 a-z 的小寫字母。
- p 可能為空，且隻包含從 a-z 的小寫字母，以及字元 . 和 *。
題目示例:
示例 1:
輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因為 '*' 代表可以比對零個或多個前面的那一個元素, 在這裡前面的元素就是 'a'。是以，字元串 "aa" 可被視為 'a' 重複了一次。
示例 2:
輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可比對零個或多個（'*'）任意字元（'.'）。
神奇的
.*
來了，Hard模式，大家坐好～
判斷 字元串s 是否與 一個 可能還有“.” or "*" 的字元規律 p 比對，其實就是從 p 代表的所有的字元串中枚舉出一個 比對值。 簡單暴力枚舉的時間複雜度是指數級的。我們需要考慮對于求解一個最優解 或 比對解的類似問題，有哪些可以降低時間複雜度的方案？
好了，不饒彎子了，動态規劃 要來了。
溫馨後記：寫着寫着就列舉了一堆動态規劃的理論，比較了解的朋友可以直接翻過這段看後面這一題的圖解。
解題之前，我們先了解下：動态規劃是什麼？為什麼動态規劃能降低時間複雜度？什麼類型的問題又能用動态規劃去解決？如何構造解題步驟？
動态規劃是什麼
動态規劃與分治方法相似，都是通過組合子問題的解來求解原問題。
分治算法将問題劃分為互不相交的子問題，遞歸地求解子問題，再将他們的解組合起來，求出原問題的解。如歸并排序，劃分的左右排序子問題是對不同的數字序列進行排序的，最後再把他們合并起來。
而動态規劃應用于子問題重疊的情況，即不同的子問題具有公共的子子問題。這種情況下分治算法需要對子子問題反複求解，而動态規劃算法隻對子子問題求解一次，将其結果儲存到備忘錄中 or 按照 自底向下 的順序 求解每個子問題（也就是保證在求解子問題時，它所依賴的子子問題的解已經求出來了）這兩種方式，避免不必要的計算工作，降低時間複雜度。
舉一個簡單的斐波那契數列的例子：
斐波那契數列指的是這樣一個數列：
1、1、2、3、5、8...
相信小夥伴們都知道，它的遞推規律是：
假設求f(10),則遞推公式展開為：
可以看到其中有大量的重複子問題：f(6),f(5) 等。
動态規劃的兩種做法就是：
1.用 遞歸的代碼求解時，将第一次計算的f(6)儲存起來，如f(8)中的f(6). 這樣再求解f(7)中的f(6)就可以直接擷取到結果了
2.按照求f(3), ->(4)->...->f(10)的自底向下的順序求解，這樣再求 f(8)時，隻需要儲存下來 f(7) 和 f(6)的值，就可以求出了，f(10)同理。這種方式大多是循環的寫法。
動态規劃解決的問題類型
初步明白後，我們再來看下動态規劃解決問題的類型：
極客時間的王争大佬 概括為： 一個模型，三個特征。
一個模型：多階段決策最優解模型
我們一般是用動态規劃來解決最優問題。而解決問題的過程，需要經曆多個決策階段。每個決策階段都對應着一組狀态。然後我們尋找一組決策序列，經過這組決策序列，能夠産生最終期望求解的最優值。
特征1:最優子結構
指的是，問題的最優解包含子問題的最優解。反過來說就是，我們可以通過子問題的最優解，推導出問題的最優解。如果我們把最優子結構，對應到我們前面定義的動态規劃問題模型上，那我們也可以了解為，後面階段的狀态可以通過前面階段的狀态推導出來。
特征2:無後效性
無後效性有兩層含義，第一層含義是，在推導後面階段的狀态的時候，我們隻關心前面階段的狀态值，不關心這個狀态是怎麼一步一步推導出來的。第二層含義是，某階段狀态一旦确定，就不受之後階段的決策影響。無後效性是一個非常“寬松”的要求。隻要滿足前面提到的動态規劃問題模型，其實基本上都會滿足無後效性。
特征3. 重複子問題
這個就是我們前面提到的，不同的決策序列，到達某個相同的階段時，可能會産生重複的狀态。
動态規劃的解題步驟
Step1.刻畫一個最優解的結構特征
也就是能夠把問題抽象轉化為一種數學描述，通俗說 就是 狀态的定義。如上述斐波那契數列 中 f(n）就是狀态的定義。
Step2.遞歸地定義最優解的值。
就是問題與子問題之間的遞推表達式是什麼，通俗說 就是 狀态轉移方程的定義。如上述斐波那契數列 中的f(n) = f(n-1) + f(n-2)
Step3.計算最優解的值
就是采用的動态規劃具體計算的做法，包括 遞歸+備忘錄 or 循環+自底向下 求解兩種方式。
Step4.利用計算出的資訊構造一個最優解
因為我們步驟一定義的狀态有時并不是我們直接要求的最優解，是以這一步就是利用狀态和狀态轉移方式 表達出我們最終要求的最優解怎麼得到。
我們會根據leetcode10來了解這些理論知識。
解題思路:
Step1.抽象出狀态
這個問題實際求的是字元串s能否從字元規律p代表的所有字元串集合中找出一個比對值。一般求兩個字元串的比對問題的狀态用二維的數組來定義，為什麼。。聽大佬說：靠經驗，靠悟。我們定義：
dp[i,j] :
代表 所有 字元串s[0,i-1] (前i個字元) 和 字元規律p[0,j-1] （前j個字元）的比對方案 集合。
dp[i,j] 的值：
代表是否存在一種方案 使得 字元規律p 比對 字元串s。這個值就是我們這個問題的解。true：存在。false：不存在。
Step2.遞歸地定義最優解的值。
這一步其實就是求狀态遞推式，找出問題dp[i,j] 和子問題之間的關系。
對于字元串s[i] 和 p[j] 是否比對，因為p[j] 可能是* or . 。我們需要枚舉出p所代表的所有字元串。我們我們可以從最後的字元 s[i] 和 p[j]來考慮。
可分為p[j] == * or p[j] != * 兩種情況。因為 '*' 代表着0-多個字元，會影響p的枚舉數。'.' 我們隻需要把它當成一個萬能字元就好，'.' 不會影響p的枚舉數量。
- 當
p[j] != '*'
s[i] 是否等于 p[j] && dp[i][j] 是否為true
圖解leetcode5-10 | 和233醬一起刷leetcode系列(2) - 當
p[j] == '*'
如圖所示，考慮
p[j] == '*'
所代表的字元數，我們需要列舉出 組成dp[i+1,j+1] 的所有可能情況，同時我們其實靠yy也能推斷出：
dp[i+1,j+1] 和 它的子問題：dp[i,j+1] 的關系，圖中我也有列舉出公式推導來源。
這裡有一點需要注意： dp[i+1,j+1]才表示s[0,i] 和 p[0,j] 比對。因為s[0]就代表了第一個字元。而我們也需要表示 s長度為0的dp[0,..]的值。不然會影響到我們遞推公式的求值。
好了，到這裡我們先總結下 這個問題動态規劃解法的狀态和狀态轉移方程：
Step3.計算最優解的值。
這個步驟就是具體計算遞推公式dp[i+1,j+1]的過程了，我們可以采用 循環+ 自底向下的方式來求解，也就是對于二維數組先填第0行的值，再填第0列的值，以此類推。
假設s="aa", p="a*" 。則它的二維填狀态表的順序和結果為：
Step4.利用計算出的資訊構造一個最優解
在Step1的時候，我們其實就定義了。 s與p是否比對 等價于 dp[i+1][j+1] 的值 是否為 true。 是以我們隻需要傳回 dp[i+1][j+1]的值 就是這道題的結果。
徹底完了，看懂了沒，上代碼吧。
Java版本
class Solution {
public boolean isMatch(String s, String p) {
int slen = s.length();
int plen = p.length();
//需要分别取出s和p為空的情況，是以dp數組大小+1
boolean[][] dp = new boolean[slen + 1][plen + 1];
//初始化dp[0][0]=true,dp[0][1]和dp[1][0]~dp[s.length][0]預設值為false是以不需要顯式初始化
dp[0][0] = true;
//填寫第一行dp[0][2]~dp[0][p.length]
for (int k = 2; k <= plen; k++) {
//p字元串的第2個字元是否等于'*',此時j元素需要0個，是以s不變p減除兩個字元
dp[0][k] = p.charAt(k - 1) == '*' && dp[0][k - 2];
}
//填寫dp數組剩餘部分
for (int i = 0; i < slen; i++) {
for (int j = 0; j < plen; j++) {
//p第j個字元是否為*
if (p.charAt(j) == '*') {
//兩種情況:1.s不變[i+1],p移除兩個元素[j+1-2]。
// 2.比較s的i元素和p的j-1(因為此時j元素為*)元素,相等則移除首元素[i+1-1],p不變。
dp[i + 1][j + 1] = dp[i + 1][j - 1] ||
(dp[i][j + 1] && headMatched(s, p, i, j - 1));
} else {
//s的i元素和p的j元素是否相等,相等則移除s的i元素[i+1-1]和p的j元素[j+1-1]
dp[i + 1][j + 1] = dp[i][j] && headMatched(s, p, i, j);
}
}
}
return dp[slen][plen];
}
//判斷s第i個字元和p第j個字元是否比對
public boolean headMatched(String s, String p, int i, int j) {
return s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
}
}
能看到這裡看來是真愛了，233醬都要對你豎起大拇指，要不要也
在看，轉發
對233醬豎起大拇指 …… ^ _ ^。不管對文章是否有疑問，都歡迎可愛的你加入我們的刷題群，有疑問233醬會在群裡答疑哦～
參考資料：
[1].《算法導論》
[2].https://time.geekbang.org/column/article/75702