26. 刪除有序數(shù)組中的重復(fù)項(xiàng)
后面的數(shù)等于前面的就continue,不等就賦給pre,pre++
25. K 個(gè)一組翻轉(zhuǎn)鏈表
迭代
24. 兩兩交換鏈表中的節(jié)點(diǎn)
迭代/遞歸
23. 合并K個(gè)升序鏈表
思路1
按合并兩個(gè)有序鏈表一輪一輪比對(duì)
思路2
將合并兩個(gè)有序鏈表作為方法，順序merge
思路3
兩兩合并 logK的方法，仔細(xì)處理n對(duì)折。
22. 括號(hào)生成
思路
- 使用dfs生成。
注意的點(diǎn)
- 結(jié)束條件寫在最前面
- 接下來是剪枝條件
- 左括號(hào)和右括號(hào)順序if。注意參數(shù)不能上下影響
21. 合并兩個(gè)有序鏈表
思路
- 簡單題，正常思路下來就可
18. 四數(shù)之和
思路
- 三數(shù)之和再加一層for循環(huán)，使用continue處理前兩個(gè)循環(huán)的重復(fù)問題，使用whle處理left right 重復(fù)問題，最后記得left++ right--
17. 電話號(hào)碼的字母組合
思路1
- 使用map，遞歸傳入str，以（“”，0）開始。index == digits.size()結(jié)束。
思路2
- map存數(shù)字和字符串的pair，將一個(gè)數(shù)字的字符串全push，通過q.size()確定循環(huán)次數(shù)
14. 最長公共前綴
思路1 橫向比對(duì)
比對(duì)相鄰兩個(gè)單詞的各個(gè)字符，截取最長公共前綴與接下來那個(gè)比。（感覺可以用遞歸來做）
思路2 縱向比對(duì)
比對(duì)字符串?dāng)?shù)組中各個(gè)單詞的第一個(gè)第二個(gè)……字符，直到某一位不同
面試題 17.21. 直方圖的水量
思路1
- 動(dòng)態(tài)規(guī)劃，左值，dp1存左側(cè)往右能接的水量，右值，dp2存右側(cè)往左能接的水量。取dp1.dp2的最小值為該下標(biāo)的真實(shí)水量
思路2
- 單調(diào)棧，
15. 三數(shù)之和
思路
- 排序定第一個(gè)i，后面使用
leftright移動(dòng)雙指針判斷和是否為0
值得注意的地方
- 在去重問題上把邊界條件放在
nums[left] = nums[left + 1]前 - 把去重移動(dòng)放在達(dá)成
==0條件的那個(gè)區(qū)域里
13. 羅馬數(shù)字轉(zhuǎn)整數(shù)
我的思路
- 用一個(gè)hashmap保存每一種羅馬數(shù)和整數(shù)的對(duì)，在一次循環(huán)中查找是兩個(gè)還是一個(gè)。優(yōu)先查兩個(gè)的。然后再把對(duì)應(yīng)數(shù)相加。
改進(jìn)思路
- 依然是使用哈希表，為了解決條件判斷語句（兩個(gè)還是一個(gè)的問題），將
s中的兩位羅馬數(shù)字替換("IV"換成"a"等等).
大佬思路
- 把一個(gè)小值例如
I放在大值V的左邊，就是做減法，否則為加法.另外,把由羅馬數(shù)字獲取數(shù)字封裝為一個(gè)函數(shù),使用switch.
12. 整數(shù)轉(zhuǎn)羅馬數(shù)字
思路
- 對(duì)羅馬數(shù)編碼，貪心減去最大的數(shù)。能減完1000就減完1000再減900.
11. 盛最多水的容器
難點(diǎn)
- 使用雙指針，長邊縮進(jìn)只會(huì)減少蓄水的容量，只有短邊縮進(jìn)（替換為長邊）才會(huì)有可能增加容量。所以只要嘗試縮進(jìn)短邊使用max就可
10. 正則表達(dá)式匹配
思路
-
*字符后的匹配情況分析
1)sa s*a 匹配對(duì)角線
2)s a 匹配0個(gè) 為左側(cè)狀態(tài)
3)saa sa 匹配重復(fù) 為上方狀態(tài)
9. 回文數(shù)
思路1
- 左右向中間移位1，比較每一位是否相等。（需要求解位數(shù)）
思路2
- 將原數(shù)組后半部分模擬成前半部分，處理一半長度。
6. Z 字形變換
我的思路
- 使用數(shù)學(xué)方法，將每一行與首列及numsrow的關(guān)系列清楚，再按行計(jì)算。
題解思路
- 使用string列表記錄每一行的str，使用flag控制列表下標(biāo)的方向轉(zhuǎn)換。
5. 最長回文子串
思路1
- 動(dòng)態(tài)規(guī)劃，轉(zhuǎn)移方程：
dp[i][j] = (s[i] == s[j]) && ((j - i) < 3 || dp[i + 1][j - 1])
思路2
- 使用中心擴(kuò)散的方法，針對(duì)回文串為奇數(shù)或偶數(shù)，基于
（i，i）和(i, i + 1)向兩邊擴(kuò)散
4. 尋找兩個(gè)正序數(shù)組的中位數(shù)
思路1
- 比較兩個(gè)正序數(shù)組中下標(biāo)為
[index + k / 2 - 1]的元素大小,去除較小元素及其左側(cè)元素,以k / 2的速度接近中位數(shù)
這個(gè)方法可以用于獲得兩個(gè)正序數(shù)組中第k個(gè)元素
需要注意的地方
-
k代表個(gè)數(shù),而非下標(biāo) - 使用左側(cè)向右延展
k / 2的方式,注意越界情況
思路2
- 中位數(shù)滿足條件——一條割線的兩側(cè)滿足交叉小于等于&& 左側(cè)元素個(gè)數(shù)==右側(cè)元素個(gè)數(shù)（+1 分奇偶）
有時(shí)間復(fù)雜度O(log min（m，n）)，在較短的那個(gè)數(shù)組上進(jìn)行二分查找。
1. 兩數(shù)之和
思路：哈希表
使用哈希表記錄需要匹配的數(shù)和數(shù)組下標(biāo)
2. 兩數(shù)相加
難點(diǎn)：
- 使用
l1 || l2 || add作為循環(huán)條件，在循環(huán)里判斷鏈表是否為空
3. 無重復(fù)字符的最長子串
思路：滑動(dòng)窗口
取一個(gè)遍歷的右指針，一個(gè)位于重復(fù)元素右側(cè)第一位的左指針，求兩指針之間的最大值。
難點(diǎn)
1.如何記錄重復(fù)字符？
- 使用字符哈希數(shù)組記錄字符的下標(biāo)，未重復(fù)使用-1作為val
2.如何找到重復(fù)元素的下標(biāo)？
- 使用字符哈希數(shù)組與left值作比較，大于等于left值則重復(fù)了，被記錄了一次過了。
3.使用下標(biāo)作為val而非（0/1）確定是否重復(fù)，免去了查找重復(fù)元素的過程。
知識(shí)點(diǎn)：
1.字符哈希數(shù)組的使用
2.memset
4. 尋找兩個(gè)正序數(shù)組的中位數(shù)
1.拼接兩個(gè)數(shù)組并找到中位數(shù)
相關(guān)題目:
35.二分搜索
7. 整數(shù)反轉(zhuǎn)
難點(diǎn)
如何判斷溢出情況？
- 輸入是十進(jìn)制的數(shù)，所以需滿足兩個(gè)判斷條件
1.最后一輪是否大于INT_MAX / 10或者小于INT_MIN / 10
2.在等于的情況下,需要判斷最后一位 - 過程是在單while循環(huán)中實(shí)時(shí)模擬的方法
需要解釋的地方
討論一下輸入的第一位
以256為例
輸入反轉(zhuǎn)后的257/258/259都是溢出的，但是752、852、952均不可能作為輸入（>256），所以不需要判斷等于的情況
以856為例
輸入反轉(zhuǎn)后的857/858/859均是溢出的，且758可以作為輸入(<856)，所以要討論758這個(gè)數(shù)的第一位(while的最后一次循環(huán))是否大于MAX的最后一位6
