思路總結(jié)

數(shù)組：

數(shù)組內(nèi)順序：

• 是否有序？
• 如果排序，是否會(huì)有額外的性質(zhì)？
• 遞增、遞減在該題內(nèi)的含義？

• prefix sum（前綴數(shù)組）在該題內(nèi)是否有特殊含義？
• 如果是 continuous subarray 的問題
  1. dp 是否有用？
  2. 滑動(dòng)窗口 + hash map 是否有用？
  3. 考慮 prefix sum + hash map 是否有用？
  4. 雙指針相向而行是否有用？其實(shí)滑動(dòng)窗口也是雙指針類型的。因此2，4可以合并為：雙指針解法。

二維數(shù)組：

• 是否和圖有關(guān)系？如果有關(guān)系，則使用圖的思路來(lái)思考。

如果需要涉及單調(diào)棧（monotonic stack)，思考是否能夠用一個(gè)變量代替。

樹：

• 遍歷方式？DFS (pre order, in order, post order)，BFS (level order)。
• 如果是 DFS，是否有必要使用 stack 代替 recursion？一般在 in order 的使用。

String：

• 如果涉及的兩個(gè)字符串之間的轉(zhuǎn)換，可以思考是否能夠使用二維 dp，一個(gè)字符串當(dāng)行，另一個(gè)當(dāng)列。
• 涉及 String 的 拆分，可以考慮 dp。例題：139 word break。
• 如果需要使用 Map 記錄每個(gè)字符的信息，可以考慮是否能夠使用 數(shù)組 代替。

dfs：

• 首先先確定 dfs 的物理意義，并在每一層都嚴(yán)格維護(hù)。
• 如果發(fā)現(xiàn)過程可以使用 buffer，并且 buffer 的 key 是整數(shù)，則可以考慮使用 dp。
• 如果題目需要給出 “所有” 的可能情況，考慮 dfs。考慮剪枝的情況。

bfs：

• 如果需要記錄 最短距離，那么遍歷首選 bfs。

Union find

• 是否需要把數(shù)據(jù)進(jìn)行分組？例如 分郵件、large island 問題，都需要進(jìn)行分組。

算法需要回看歷史數(shù)據(jù)

• 如果算法中需要回看之前的數(shù)據(jù)（尤其是前一個(gè)訪問過的數(shù)據(jù)），可以考慮使用 Stack。
• 使用 HashMap 記錄遍歷過的數(shù)據(jù)，查找方便。例如 two sum，continuous subarray sum。

國(guó)版

31. Next Permutation

tag：遞增、遞減序列在題目中的特殊意義
尋找數(shù)組中遞增、遞減序列的含義。和之前“無(wú)序數(shù)組找任意peek”那道題一樣，需要找到遞增、遞減序列在其中具有的特殊意義才能解決問題。

426. Convert Binary Search Tree to Sorted Doubly Linked List

tag：經(jīng)典 dfs，將dfs函數(shù)物理意義定義清楚
非常經(jīng)典的dfs。只要把dfs的物理意義給定義好，實(shí)現(xiàn)dfs的過程嚴(yán)格按照物理意義來(lái)，那么解題就很簡(jiǎn)單。注意其中關(guān)于 null 的判斷與處理。

1762. Buildings With an Ocean View

tag：使用不斷更新的變量來(lái)代替單調(diào)棧dp數(shù)組 (Monotonic stack)
使用單獨(dú)的變量來(lái)代替單調(diào)棧數(shù)組（也即使用dp求得每個(gè)位置的最大值）。這個(gè)技巧使用在了“最大的雨水積累”、“除了自己之外的數(shù)字乘積”等需要使用單調(diào)棧的地方。單調(diào)棧英文：monotonic stack。

50. Pow(x, n)

tag：Integer.MIN_VALUE在取反時(shí)會(huì)超過 int 的取值范圍
注意需要先將 int n 轉(zhuǎn)化為 long n進(jìn)行計(jì)算，因?yàn)閚有可能是-2^31，它取反是超過int范圍的。這是一個(gè)坑，需要注意。

139. Word Break (Mark)

tag：帶 buffer 的 dfs，可以使用 dp 解決
帶buffer的dfs，可以轉(zhuǎn)化為動(dòng)態(tài)規(guī)劃。這種String類型的題目大多可以使用動(dòng)態(tài)規(guī)劃來(lái)解決。該題需要注意邊界條件的判斷。

美版

238. Product of Array Except Self

tag：使用變量代替單調(diào)棧dp數(shù)組
同國(guó)版1762。

199. Binary Tree Right Side View

tag：bfs進(jìn)行l(wèi)evel order traversal
經(jīng)典的 bfs level order traversal。

301. Remove Invalid Parentheses

tag：帶有剪枝的 dfs
由于題目中要求求出所有可能的情況，因此算法上選擇 dfs。首先定義好 dfs 的物理意義。對(duì)于本題，可以發(fā)現(xiàn)能夠剪枝的情況，即左括號(hào) <= 右括號(hào)時(shí)，如果再遇到一個(gè)右括號(hào)就可以直接丟棄。同時(shí)需要記住 dfs 里吃了吐的原則，一定要保證這點(diǎn)。

這道題和另一題很像，但那道題只要求返回最小removal中的任意一個(gè)就可以了，因此不用dfs，而用StringBuilder + Linear Scan 即可。題目之差幾個(gè)字，但是算法截然不同。

528. Random Pick with Weight

tag：隨機(jī)數(shù)，可以使用前綴和 prefixSum 解決
新的題型，根據(jù)數(shù)字大小按權(quán)重選擇數(shù)字。使用 prefixSum + binary search 來(lái)代替選擇過程。

827. Making A Large Island (Mark)

tag：dfs；union find；最多可以將一個(gè)1轉(zhuǎn)換成0
經(jīng)典的題目，組合了dfs + union find + 面對(duì)可轉(zhuǎn)換0->1時(shí)的解題思路。

1. 在進(jìn)行dfs的時(shí)候，如果是在一個(gè)二維數(shù)組上進(jìn)行dfs，那么可以直接使用一個(gè)boolean matrix 作為 visited，沒有必要使用Set<String>。

2. 解決這種“可以轉(zhuǎn)換內(nèi)容”的題目時(shí)，可以考慮先將轉(zhuǎn)換的機(jī)會(huì)用掉，然后在一個(gè)確定的情景下解題，這樣更容易。比如本題，最多允許將1個(gè)1轉(zhuǎn)換為0，那么可以直接掃描所有的0，對(duì)于掃描的0將其作為1看待，這樣就成為一個(gè)確定情景了。

3. Union find 是解決這類面積類為題的思路之一。使用 dfs 求得。

1650. Lowest Common Ancestor of a Binary Tree III (Mark)

tag：LCA變種，容易踩坑，從一個(gè)node一直往上道null后，需要從另一個(gè)node再重新開始
這道題和傳統(tǒng)的LCA不同，這道題的 Node 給了 parent 指針，并且 root 不再作為函數(shù)參數(shù)傳遞進(jìn)來(lái)了。

這道題需要注意一點(diǎn)的是，給的兩個(gè) Node 可能不在同一層，因此不能無(wú)腦的取 parent 判斷相不相等。

636. Exclusive Time of Functions

tag：linear scan + stack
對(duì)于這類linear scan過程需要會(huì)看之前內(nèi)容的題目，可以考慮使用 stack。加入 stack 之后算法的核心思想就是如何利用、維護(hù) stack 以及里面的內(nèi)容。

721. Accounts Merge (Mark)

tag：Union Find
對(duì)于需要“合并”類的題目，可以使用 Union-Find 算法。

Union Find 算法的大致思路是，給每個(gè)節(jié)點(diǎn)都設(shè)置一個(gè) parent，這個(gè) parent 也表示當(dāng)前節(jié)點(diǎn)和parent節(jié)點(diǎn)屬于同一個(gè) union。每一個(gè)union都有一個(gè)自己的特殊標(biāo)識(shí)，這個(gè)標(biāo)識(shí)可以是自己另外指定的（例如指定額外的index作為標(biāo)識(shí)），也可以將union中的某個(gè)節(jié)點(diǎn)作為標(biāo)識(shí)（對(duì)于該節(jié)點(diǎn)來(lái)說，parent就是它自己）。在掃描所有節(jié)點(diǎn)的過程中，不斷更新維護(hù) parent，最后就可以將整個(gè)集合分成若干 union。

Union Find 算法的核心函數(shù)是 find() 和 union()。find函數(shù)是找到給定節(jié)點(diǎn)所屬的 union，union()可以合并兩個(gè)union()。需要額外注意的是，當(dāng)前節(jié)點(diǎn)的 parent 并不是當(dāng)前節(jié)點(diǎn)的 union標(biāo)識(shí)，我們需要使用 find() 來(lái)找到 當(dāng)前節(jié)點(diǎn)的 union 標(biāo)識(shí)。

236. Lowest Common Ancestor of a Binary Tree

tag：recursion；傳統(tǒng)LCA
對(duì)于recursion，最重要的就是定義recursion函數(shù)的物理意義。對(duì)于傳統(tǒng)LCA，recursion函數(shù)的物理意義是：返回 LCA 或者 p,q 節(jié)點(diǎn)自己。

523. Continuous Subarray Sum

tag：prefix sum；two sum變種 (hash map)
首先看到 “continuous”，“subarray”，可以想到使用 prefix sum。但使用 prefix sum 會(huì)發(fā)現(xiàn)仍然需要求出每一個(gè) subarray 的值，單獨(dú)的 prefix sum無(wú)法降低時(shí)間復(fù)雜度。

這時(shí)候發(fā)現(xiàn)關(guān)鍵點(diǎn)：這種求組合為target的題目，都可以考慮使用 two sum 的邏輯，使用一個(gè) hash map 記錄下遍歷過的值，在訪問到新值的時(shí)候先從 map 中找找有沒有符合條件的已訪問過的元素。這可以有效降低時(shí)間復(fù)雜度。

另對(duì)于本題，由于題目需要subarry至少有兩個(gè)元素，因此還需要額外的邏輯確保這個(gè)。

124. Binary Tree Maximum Path Sum

tag：recursion，人字形結(jié)果，一字形定義
樹的題目除了 level order traversal 時(shí)需要使用 bfs，其他絕大部分都使用 recursion。

recursion 的題目最重要的步驟就是定義 recursion 的物理意義。一般情況下，recursion 的物理意義和題目的問題應(yīng)該是相同的。

但是這道題的難點(diǎn)就是在于 recursion 物理意義和題目所求的是不一樣的。題目要求求出最長(zhǎng)的“人字形”路徑，但是這樣的 recursion 是非常難以維護(hù)的，因此將 recursion 定義為求最長(zhǎng)的“一字形”路徑，而之字形路徑的維護(hù)在每一層 recursion 內(nèi)部進(jìn)行。

269. Alien Dictionary (Mark)

tag：graph problem；topological sort + bfs/dfs
本題是圖論的一道好題，涉及到了 topological sort，是一個(gè)之前沒有接觸過的思想。通過維護(hù)節(jié)點(diǎn)的入度 (in-degree) 來(lái)對(duì)節(jié)點(diǎn)進(jìn)行排序。每次選出入度為0的節(jié)點(diǎn)，加入結(jié)果集，刪除該節(jié)點(diǎn)，同時(shí)更新鄰居節(jié)點(diǎn)的入度，重復(fù)直到?jīng)]有入度為0的節(jié)點(diǎn)。這個(gè)描述很適合使用bfs來(lái)實(shí)現(xiàn)，也即 while(!queue.isEmpty()){...}。實(shí)現(xiàn) topological sort 的方法有 bfs 和 dfs，本題使用了 bfs，dfs還沒搞懂。

這道題除了學(xué)到了新的圖論算法，另外給我的啟示是，算法過程中維護(hù)的數(shù)據(jù)結(jié)構(gòu)越少越好，盡量能讓數(shù)據(jù)結(jié)構(gòu)復(fù)用。

65. Valid Number (Not complete)

tag：dfa（deterministic finite automation 有限狀態(tài)機(jī)）

273. Integer to English Words

tag：recursion + corner cases
由于這道題每個(gè)部分的轉(zhuǎn)換規(guī)則是有規(guī)律的，因此可以使用 recursion 來(lái)完成。

本題的難點(diǎn)有三個(gè)：1. 轉(zhuǎn)換過程中 num 的更新；2. parse 過程中 corner case 的考慮；3. 輸出字符串的空格問題。

56. Merge Intervals

tag：sort + linear scan
對(duì)于merge類的題目，除了 union find 之外，也可以考慮先將給定的數(shù)組進(jìn)行排序，然后再找規(guī)律。往往排序后的數(shù)組有很多特殊的性質(zhì)可以使用。注意輸入數(shù)組的有序性。

140. Word Break II

tag：dfs + limitation（剪枝）
由于題目需要求出所有的可能情況，因此首先考慮使用 dfs，同時(shí)發(fā)現(xiàn)有很多可以剪枝的地方。

這道題的一個(gè)坑是在于 StringBuilder 在吃完吐的時(shí)候，delete 的函數(shù)是刪除字符，而不是字符串的，因此在吐時(shí)需要從 sb.length() - word.length() 開始刪，而不是單純的減一。

987. Vertical Order Traversal of a Binary Tree

tag：dfs/bfs + Comparator
樹的問題首先想到 dfs 和 bfs。dfs：in order, pre order, post order。bfs：level order。

這道題主要是要讀懂題目，選用合適的數(shù)據(jù)結(jié)構(gòu)，算法層面的技巧不強(qiáng)。對(duì)于需要排序的題目，數(shù)據(jù)結(jié)構(gòu)可以考慮：PriorityQueue，TreeMap，TreeSet。方法：Arrays.sort()，Collections.sort()。

560. Subarray Sum Equals K

tag：prefix sum + hash map
看到 subarray，需要想到 prefix sum 與 dp。再看到 subarray sum，可以考慮使用 prefix sum。這道題是找組合和等于k，和 two sum 是很類似的，因此考慮使用 HashMap 來(lái)記錄下便利過的元素。由于題目要求求個(gè)數(shù)，而不要求index，因此 HashMap 里只需記錄某個(gè) prefix sum 值出現(xiàn)了多少次即可。

1249. Minimum Remove to Make Valid Parentheses

tag：StringBuilder + linear scan
這道題在scan原String時(shí)，使用StringBuilder來(lái)存放字符。這道題更多是算法層面的思想，也即如何處理多出來(lái)的左括號(hào)和右括號(hào)。對(duì)于多出來(lái)的右括號(hào)，可以不append進(jìn) StringBuilder 里；對(duì)于多出來(lái)的左括號(hào)，可以遍歷完后從右往左刪除多余的。

139. Word Break

tag：dp + String，帶 buffer 的 dfs 轉(zhuǎn) dp
這道題沒有一開始就想到用 dp，但是梳理一下思考過程，還是能有啟發(fā)。

首先想到的是暴力 dfs，但由于這道題只用找到一種 segmentation 情況就行，因此可以在 dfs 里加上 buffer 來(lái)存中間結(jié)果。我對(duì) dfs 函數(shù)的設(shè)計(jì)是：dfs(String s, int index, int[] buffer, List<String> wordDict)，帶 buffer 的單變量 dfs 可以很自然的變成 dp。對(duì)于 dfs(String s, int index, int[] buffer, List<String> wordDict) 這個(gè)函數(shù)，我的定義是：對(duì)于s，從index到最后一個(gè)字符所組成的字符串是否能夠被wordDict segment。

對(duì)于字符串的 dp 來(lái)說，dp[i] 一般定義為“以 s[i-1] 結(jié)尾的字符串 ...”，因此這里 dp[i] 定義為以 [0, i) 左閉右開區(qū)間的substring 是否能被 segment。

227. Basic Calculator II

tag：將字符串轉(zhuǎn)化為整數(shù)的巧妙方法
一個(gè)由數(shù)字組成的字符串，除了使用 Integer.valueOf() 之外，還可以這樣：

int num = 0;
for(char c : s.toCharArray()) {
  num += 10 * num + c - '0';
}
return num;

347. Top K Frequent Elements (Mark)

tag：counting sort / bucket sort，給數(shù)組的 index 賦予意義，利用 index 的值本身來(lái)存信息
這道題使用到了新的排序算法: counting sort 或 bucket sort。注意這道題需要返回 Top K 的所有元素，而不是找到第 K 個(gè)元素。

這道題的思路比較簡(jiǎn)單，就是遍歷整個(gè)數(shù)組，得到每個(gè)element出現(xiàn)的次數(shù)，然后根據(jù)次數(shù)從大到小選擇前K個(gè)返回。問題在于時(shí)間復(fù)雜度需要是O(n)，但基于比較的排序至少是 O(nlogn)，因此使用到 counting sort / bucket sort。

bucket sort 的適用場(chǎng)景是，所給的數(shù)字在一定范圍內(nèi)均勻分布，這種情況下 bucket sort 的性能是最好的。無(wú)論是 bucket sort 還是 counting sort，它們都有一個(gè)共同點(diǎn)：都用到了數(shù)組的 index 作為信息。

對(duì)于這道題來(lái)說，可以新建一個(gè) List<Integer>[]，其中 List[i] 里面存的是出現(xiàn)次數(shù)為 i 的所有元素。這里就將 index 賦予了有用的信息，如果我們從后往前遍歷這個(gè) List[]，那么自然是從次數(shù)最多向次數(shù)最少遍歷的。遍歷新數(shù)組的時(shí)間復(fù)雜度是 O(n)；生成這個(gè)新數(shù)組時(shí)，由于題目不要求相同frequency的元素的排序，因此時(shí)間復(fù)雜度也是 O(n)（如果返回的結(jié)果里相同的frequency也需要排序的話，那么時(shí)間復(fù)雜度會(huì)更高）。因此這道題的時(shí)間復(fù)雜度是 O(n)。

953. Verifying an Alien Dictionary

tag：提早對(duì) corner case 進(jìn)行判斷；善于使用提供的API
這道題是 easy 的題目，思路比較簡(jiǎn)單，代碼量也不多。

本題給我的啟發(fā)是，在邏輯處理過程中，如果有corner case，盡量先單獨(dú)列出來(lái)提前解決，能夠省去后面很多的麻煩。比如本題，有一個(gè) corner case 是，如果 word2 是 word1 的一個(gè)子串 (substring(0,x))，那么直接返回 false。把這個(gè) case 單獨(dú)拿出來(lái)處理，后續(xù)的邏輯就不用擔(dān)心這種情況了。

71. Simplify Path

tag：stack + 字符串處理 + corner cases
本題的數(shù)據(jù)結(jié)構(gòu)選用的是 stack，原因是存在 “.." 這種情況，能夠回到上一級(jí)目錄。

在參考答案和discussion里，都使用了 s.split("/") 函數(shù)來(lái)對(duì)字符串進(jìn)行預(yù)處理。這樣雖然代碼量會(huì)減少很多，但感覺避開了本題想考察的一個(gè)重點(diǎn)，就是如何處理字符串。因此在刷題的時(shí)候使用這樣的函數(shù)無(wú)可厚非，但是面試時(shí)需要經(jīng)過面試官的同意才行。

173. Binary Search Tree Iterator (Mark)

tag：使用 stack 模擬 recursion，可在 recursion 過程中暫停
本題的目標(biāo)是實(shí)現(xiàn)空間復(fù)雜度 O(h) 的算法，因此傳統(tǒng)遞歸實(shí)現(xiàn) in-order traversal 存放所有節(jié)點(diǎn)順序的方法并不適用。

對(duì)于 recursion 的題目，可以考慮使用 stack 來(lái)模擬遞歸的過程。本題是經(jīng)典的利用 stack 模擬遞歸的題目。利用 stack 模擬遞歸的好處在于，可以自己控制遞歸的過程。本題中，可以先將所有的左節(jié)點(diǎn)放入 stack 中，而不放右節(jié)點(diǎn)。隨著 next() 的調(diào)用，再將 pop 出來(lái)的節(jié)點(diǎn)的右節(jié)點(diǎn)的所有左節(jié)點(diǎn)放入 stack 中。這樣相當(dāng)于控制了遞歸的過程，空間復(fù)雜度是 O(h)，h 是樹的高度。

stack 模擬 recursion 需要注意的是 push stack 的順序。stack 是后進(jìn)先出，而對(duì)于當(dāng)前節(jié)點(diǎn)來(lái)說，節(jié)點(diǎn)的左孩子應(yīng)該是先出的，因此左孩子需要后放入 stack，先將自己 push stack。

1047. Remove All Adjacent Duplicates In String

tag：stack；利用 StringBuilder 代替 Deque
很多題目我們需要用到 stack 的思想，但并不每道題都需要使用 Deque 來(lái)實(shí)現(xiàn) stack，也可以考慮 int[]，StringBuilder 之類的數(shù)據(jù)結(jié)構(gòu)。本題利用 StringBuilder 來(lái)模擬 stack，代碼更加簡(jiǎn)潔。

339. Nested List Weight Sum

tag：讀懂題意 + dfs
這道題的難點(diǎn)之一在于讀懂題意以及對(duì)新給 API 作用的理解，在這兩方面必須花時(shí)間了解清楚題意。

由于題目中涉及到了“層”的概念，因此使用經(jīng)典的 dfs 來(lái)完成，注意定義清楚 dfs 的物理意義。

314. Binary Tree Vertical Order Traversal (Mark)

tag：樹的遍歷 + bfs + TreeMap
關(guān)于樹的題目，十有八九是離不開樹的遍歷的，因此確定按照什么樣的順序遍歷樹是至關(guān)重要的。常用的遍歷有 dfs (pre order, in order, post order) 與 bfs (level order)，這兩種遍歷方式的特點(diǎn)是不同的。

對(duì)于 dfs 來(lái)說，由于可以使用 recursion，因此適用于對(duì)每個(gè)節(jié)點(diǎn)都進(jìn)行類似操作的題目，是更常見的遍歷方法。

對(duì)于 bfs 來(lái)說，level order traversal 能夠保證遍歷過程中 樹的深度的有序性（深度+1）、同深度間節(jié)點(diǎn)的有序性（從左向右或從右向左）。

對(duì)于本題，由于題目中需要節(jié)點(diǎn)從左到右的順序，因此選用 bfs 來(lái)完成。由于需要按照 col 來(lái)排序，因此使用 TreeMap。

670. Maximum Swap

tag：monotonic stack + String API
一個(gè)題目是由 算法+數(shù)據(jù)結(jié)構(gòu) 組合而成的，有時(shí)候數(shù)據(jù)結(jié)構(gòu)可以為算法提供思路，有時(shí)候算法能為數(shù)據(jù)結(jié)構(gòu)的選擇進(jìn)行指導(dǎo)。這道題是需要先想清楚算法的細(xì)節(jié)，再選擇合適的數(shù)據(jù)結(jié)構(gòu)。

最開始做這道題時(shí)，算法是錯(cuò)誤的，以為是要找單調(diào)的遞增的序列，然后將peek和左側(cè)bottom交換。

正確的算法應(yīng)該是，找到自己右邊最大且離的最遠(yuǎn)的數(shù)，然后進(jìn)行交換。提到找自己右邊最大，就想到了單調(diào)棧 monotonic stack。

317. Shortest Distance from All Buildings (Mark)

tag：bfs
本題為 Hard，選擇合適的算法很關(guān)鍵。

遍歷算法的選擇：由于需要記錄到每個(gè)點(diǎn)的最短 steps，因此選擇 bfs 來(lái)實(shí)現(xiàn)（bfs 天生自帶最短路徑屬性，這是 dfs 不具備的）。對(duì)于遍歷，有兩種選擇：1. 從 0 開始遍歷，尋找到每個(gè) 1 的 steps；2. 從 1 開始遍歷，尋找到每個(gè) 0 的 steps。這兩種方式都是可行的，但是當(dāng) 0 更多的時(shí)候，從 1 開始效率更高；1 更多的時(shí)候，從 0 開始效率更高。這點(diǎn)可以在面試時(shí)提出。

數(shù)據(jù)結(jié)構(gòu)。如何判斷一個(gè)0是否能夠到達(dá)所有的1？可以針對(duì)每個(gè)位置設(shè)置一個(gè)counter，每bfs遍歷到一次該點(diǎn)，該點(diǎn)的 counter 就加一，最后看 counter 是否等于 grid 中 1 的總個(gè)數(shù)即可。

1382. Balance a Binary Search Tree

tag：in order traversal + dfs
對(duì)于 BST 的題目，首先想到 in order traversal。

這道題最開始的時(shí)候想復(fù)雜了，一直在想如何直接在原來(lái)的樹上 dfs/ bfs 從而生成新的 BST。最后沒想到。

正確做法是，先用 dfs 按照 in order 順序?qū)⒚總€(gè)節(jié)點(diǎn)放入一個(gè) list 中，然后基于這個(gè) sorted list 使用 dfs 來(lái)生成 BST。這里需要注意的是，在 in order traverse 原樹時(shí)，把節(jié)點(diǎn)放入 list 中之后需要將當(dāng)前節(jié)點(diǎn)的左右孩子置為 null，避免生成新樹時(shí)出現(xiàn)環(huán)。

list 生成 BST 的過程可以參考題目：108. Convert Sorted Array to Binary Search Tree。

1263. Minimum Moves to Move a Box to Their Target Location

tag：bfs
看到題目：Minimum Moves，再加上圖的題目，因此需要首先想到 bfs。

這道題的難點(diǎn)在于，在 bfs 遍歷的過程中，鄰居位置遍歷的合法性。除了沒有越界、不能是 ‘#’ 外，還需要保證推箱人能夠能夠到達(dá)對(duì)應(yīng)的推箱位置。同時(shí)，在 bfs 遍歷過程中，如何定義 “已經(jīng)訪問過的情況” 也是難點(diǎn)之一。平時(shí)的題目更多是單一變量的，即該位置是否有被訪問過。但是這道題 “已經(jīng)訪問過” 有兩個(gè)變量，一是箱子的位置，二是人的位置，只有這兩個(gè)情況都曾經(jīng)遍歷過時(shí)，才算是“訪問過”，可以剪枝。

249. Group Shifted Strings

tag：HashMap + String convert
本題更偏算法。思路是，將所有的String都轉(zhuǎn)化為以 a 開頭的 shifted string，如果屬于同一組的話，那么 a 開頭的 shifted string 會(huì)是相同的。

791. Custom Sort String

tag：int[] 代替 HashMap
這題的思路很有意思。先遍歷 待order 的數(shù)組，記錄每個(gè)字符出現(xiàn)了幾次，然后遍歷給定的 order 數(shù)組，根據(jù)記錄的字符次數(shù)加入到 StringBuilder 中。由于遍歷 order 數(shù)組已經(jīng)保證了順序，因此這個(gè)方法適用。剩余的字符再加入到 StringBuilder 后面就可以了。

記錄字符出現(xiàn)次數(shù)可以使用 int[] 來(lái)記錄，而不用HashMap，其中 index 即為 char c - 'a'。

863. All Nodes Distance K in Binary Tree （Mark）

tag：dfs + 思路
這道題的難點(diǎn)在于，如何得到 target 節(jié)點(diǎn)上方節(jié)點(diǎn)的 distance 信息，以及上方節(jié)點(diǎn)的其他孩子節(jié)點(diǎn)的信息。

1. 不要吝嗇使用數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)不要的信息。能夠使用一個(gè) HashMap 來(lái)儲(chǔ)存 target 上方節(jié)點(diǎn)的 distance，這個(gè) HashMap 能夠使用 dfs 來(lái)獲得。

2. 獲得 distance map 之后，可以使用 dfs 來(lái)遍歷這棵樹了。在定義 dfs 物理意義的時(shí)候，一定要找到規(guī)律，不要把 dfs 每一層的邏輯設(shè)計(jì)的過于復(fù)雜。這一步的 dfs 的難點(diǎn)在于，如何更新“與 target 之間的 distance” 這個(gè)信息?？梢韵胂瘳F(xiàn)在遍歷到了某個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的左孩子如果和 target 不在一邊，那么左孩子 distance 就是當(dāng)前節(jié)點(diǎn) distance + 1，因?yàn)?target 想抵達(dá)當(dāng)前節(jié)點(diǎn)的左孩子，需要先經(jīng)過當(dāng)前節(jié)點(diǎn)。同理右節(jié)點(diǎn)的 distance 也一樣。但問題在于，如果自己的某個(gè)孩子與 target 在一側(cè)，并且在 target 上方，那么孩子的 distance 應(yīng)該 -1 了，因?yàn)殡x target 近了一步。如果按照這個(gè)邏輯來(lái)想，每層的 dfs 邏輯會(huì)很復(fù)雜，既要判斷孩子在不在 target 的同一邊、在不在 target 上方，還會(huì)有不同的 distance 計(jì)算方式，這樣的設(shè)計(jì)就是不好的。

我們之前已經(jīng)得到了一個(gè) HashMap 用來(lái)儲(chǔ)存 target 同一邊的所有上方節(jié)點(diǎn)離 target 的 distance。這個(gè)數(shù)據(jù)結(jié)構(gòu)是至關(guān)重要的，它的出現(xiàn)能夠簡(jiǎn)化 2 中 dfs 的設(shè)計(jì)。到達(dá)某個(gè)節(jié)點(diǎn)時(shí)，我們先看自己在不在存 distance 的 Map 中（簡(jiǎn)稱 disMap），如果在的話，就把 Map 里的 distance 來(lái)作為自己的 distance。在 dfs 左右孩子時(shí)，也可以直接粗暴的將孩子的 distance 設(shè)置為 自己的 distance + 1，因?yàn)槿绻⒆釉趖arget 正上方，則孩子也會(huì)在 disMap 里，它那一層的 dfs 中會(huì)自己更新 distance；如果孩子不在 target 正上方，那么孩子的 distance 的確等于 當(dāng)前 distance + 1。這樣既保證了正確性，也極大簡(jiǎn)化了每層 dfs 的邏輯。

766. Toeplitz Matrix

tag：轉(zhuǎn)化題意，復(fù)雜問題簡(jiǎn)單化
這道題是道 easy 的題目，但是我看了答案才寫出來(lái)，而答案也是的確是 easy 的。

這道題需要判斷一個(gè)二維數(shù)組的各個(gè)對(duì)角線上的元素是否相等。我的思路是一次遍歷數(shù)組的每個(gè)對(duì)角線，查看同一對(duì)角線里的元素是否相同。但最后由于坐標(biāo)轉(zhuǎn)換沒有想清楚而失敗。

但這道題完全等價(jià)于：對(duì)于每個(gè)元素，判斷它和自己右下一格的元素是否相同。這個(gè)算法只需要兩個(gè)普通的 for 循環(huán)就完成了。但是我沒有想到這樣對(duì)題意進(jìn)行轉(zhuǎn)化。

1570. Dot Product of Two Sparse Vectors (Mark)

tag：hash map -> list of key-value pairs + two pointers -> binary search
這道題的首先反應(yīng)是，使用數(shù)據(jù)結(jié)構(gòu)儲(chǔ)存非零的 index 與 值，在相乘的時(shí)候能夠減少不必要的遍歷時(shí)間。

方法一是使用 HashMap 來(lái)儲(chǔ)存 index、value。這種方法可行，但是在 FB 面試過程中，面試官并不欣賞這個(gè)做法，原因是因?yàn)閿?shù)組大了之后，給每個(gè) index 進(jìn)行哈希運(yùn)算也需要花時(shí)間。

方法二是使用 List<int[]> 來(lái)存儲(chǔ) [index, value] 對(duì)，在計(jì)算 dot product 的時(shí)候使用 two pointers 的方法，分別遍歷兩個(gè)數(shù)組的 List<int[]>。由于生成 List 時(shí)是順序遍歷輸入數(shù)組的，因此 List 內(nèi)部是有序的。

這道題還有個(gè) follow up：如果只有一個(gè)是 sparse，另一個(gè)不是怎么辦？解決方案是，在進(jìn)行 dot product 的時(shí)候，使用 binary search 來(lái)找到非 sparse 數(shù)組的 List 的 非零值。

658. Find K Closest Elements

tag：continuous subarray + two pointers
這道題并沒有顯示的說明時(shí) subarray 的題目，但是可以通過題意分析出必須是 subarray 的題。

作為 subarray 的題目，可以考慮的解法有：雙指針、dp。其中雙指針也分為同向而行（滑動(dòng)窗口）、相向而行。本題在嘗試同向而行失敗后，發(fā)現(xiàn)相向而行才是正確的解法，因?yàn)檫@道題隱含的意思是從數(shù)組兩端逐個(gè)剔除不正確元素。

本題不選擇滑動(dòng)窗口的另一個(gè)原因是，我只對(duì)窗口的邊界值感興趣，而對(duì)窗口內(nèi)部的元素不感興趣，這樣其實(shí)就從滑動(dòng)窗口退化成了雙指針問題。在選擇雙指針方向的時(shí)候，注意到比較的是兩端的極值，于是選擇相向而行。

581. Shortest Unsorted Continuous Subarray

tag：continuous subarray + motonic stack -> 單指針代替
// TODO:

162. Find Peak Element

tag：binary search 的意義：嘗試可能的部分
這道題要求使用 logn 的解法，因此想到 binary search。binary search 的核心在于：淘汰不可能的部分。也可以換個(gè)理解：嘗試可能部分。

這道題初一看和 binary search 沒啥關(guān)系，但是分析：如果 mid 左小右小，則自己是 peek，返回；mid 左小右大，那么右邊一定有peek，則找右邊；mid 左大右小，左邊一定有 peek，找左邊；左大右大，兩邊都有peek，任意一邊就行。

1329. Sort the Matrix Diagonally (Mark)

tag：合理表達(dá) diagonal 元素 + heap 用于排序
這道題的難點(diǎn)有兩個(gè)，一個(gè)是如何按照下標(biāo)獲取對(duì)角線元素，二是如何排序?qū)蔷€元素。

對(duì)于第一個(gè)問題，同一對(duì)角線的坐標(biāo) (i, j) 有 i-j 的值是相等的。可以通過 i-j 相等在遍歷整個(gè) matrix 時(shí)將不同對(duì)角線的元素分開。

對(duì)于第二個(gè)問題，無(wú)論是sort API 還是 sort 算法，我們一般是在一維數(shù)組里進(jìn)行排序，沒有來(lái)排序過對(duì)角線。但實(shí)際上，我們可以用 heap 來(lái)進(jìn)行排序。不能只記住 heap 在 kth closest 類題目中的使用方法，它最原始的功能還是排序。

1008. Construct Binary Search Tree from Preorder Traversal (Mark)

tag：dfs 物理意義
本題是通過 preorder traversal 來(lái)構(gòu)建 BST，對(duì)于構(gòu)建 tree，首先想到的是 dfs，現(xiàn)在的問題在于如何定義 dfs 的物理意義，以及如何規(guī)定 base case。

可以回憶如何判斷BST是否合法的題目，解法dfs里加入了 low、high 信息用于判斷當(dāng)前節(jié)點(diǎn)是否合法。在本題中，也可以在 dfs 的里加入 low、high 的信息，用于判斷 preorder 的元素在當(dāng)前層的 recursion 中是否合法。通過 low、high 的信息來(lái)規(guī)定 base case。

1305. All Elements in Two Binary Search Trees

tag：使用 stack 代替 recursion 對(duì) BST 進(jìn)行 in-order traversal
這道題的核心就是 tag 中的內(nèi)容，能用 stack 代替 recursion 之后，就可以做誰(shuí)小移誰(shuí)了。當(dāng)然也可以先用 dfs 把兩個(gè) Tree 都遍歷一遍，然后再誰(shuí)小移誰(shuí)。

260. Single Number III

tag：bitmask + 位運(yùn)算
// TODO

1095. Find in Mountain Array

tag：binary search
本題是單純的 binary search。首先用binary search 找到 peek，其次在peek左側(cè)進(jìn)行 binary search，最后在 peek 右側(cè) 進(jìn)行 binary search。

唯一需要注意的是，由于這題對(duì) API 的調(diào)用有要求，因此在每一輪 binary search 的時(shí)候，先把值存在下來(lái)，而不要在 if 語(yǔ)句中調(diào)用 API。

105. Construct Binary Tree from Preorder and Inorder Traversal (Mark)

tag：dfs + map
典型的 dfs，使用 map 來(lái)加速查找 preorder 某個(gè)元素 在 inorder 數(shù)組中的 index。

763. Partition Labels

tag：greedy algorithm
找出每個(gè)元素最后出現(xiàn)的下標(biāo)，然后從頭到尾 scan。

419. Battleships in a Board

tag：局部代替整體
例如枚舉矩形的時(shí)候，我們將最左上的點(diǎn)作為錨點(diǎn)來(lái)遍歷舉行。這道題里，在計(jì)算個(gè)數(shù)時(shí)，也可以只數(shù)符合條件的最左上的點(diǎn)。

442. Find All Duplicates in an Array

tag：使用數(shù)組的 index 來(lái)存儲(chǔ)必要的信息
本題的目標(biāo)是使用 O(1) 的空間解決，因此不能使用額外的數(shù)據(jù)結(jié)構(gòu)，只能使用 input 數(shù)組，此時(shí)需要巧妙的使用數(shù)組的 index 來(lái)存儲(chǔ)信息。

由于題目的限制，數(shù)組中數(shù)的范圍是 1～n，剛好能夠使用 input 數(shù)組來(lái)存儲(chǔ)信息。每當(dāng)遍歷到 num 時(shí)，執(zhí)行 nums[Math.abs(num)-1] *= -1 ，將對(duì)應(yīng)位置的數(shù)置為負(fù)數(shù)。當(dāng)另一個(gè)num查看該位置為負(fù)數(shù)時(shí)，就知道之前已經(jīng)遍歷過了，自己出現(xiàn)了兩次。這里的關(guān)鍵是 Math.abs()。

1026. Maximum Difference Between Node and Ancestor

tag：recursion 從上到下傳遞信息
做多了從下往上傳遞信息的 recursion，突然遇到從上到下傳遞信息的題目還是不習(xí)慣。

這題的思想是，把當(dāng)前層的最大值和最小值傳遞給下一層，那么遞歸到 null 時(shí)，此時(shí)就維護(hù)著從根到該 null 節(jié)點(diǎn)路徑上的最大值和最小值，然后在 null 節(jié)點(diǎn)計(jì)算結(jié)果。

979. Distribute Coins in Binary Tree

tag：dfs物理意義
dfs 物理意義是 tree 類型題目最核心的要點(diǎn)。正確合理的物理意義能讓代碼簡(jiǎn)潔、思路清晰。

本題 dfs 的物理意義是：返回該節(jié)點(diǎn)多余的coin。每一層為了維護(hù)這個(gè)物理意義，需要先得到 left 多余的coin，再得到 right 多余的coin，那么本層多余的coin就是 root.val + right + left - 1。問題在于 movement 如何計(jì)算？當(dāng)前層的movement = Math.abs(left) + Math.abs(right)。因?yàn)榉祷刂禐檎龜?shù)時(shí)，表示子樹有多余的 coin 需要上移；如果返回值為負(fù)數(shù)時(shí)，表示子樹需要相應(yīng)的 coin。兩者絕對(duì)值相加即為經(jīng)過當(dāng)前節(jié)點(diǎn)的 movement。

695. Max Area of Island (Mark)

tag: dfs
這道題是經(jīng)典的圖遍歷題，之前一直都是用 bfs 寫，今天看了答案里 dfs 的寫法，被 dfs 的簡(jiǎn)潔所震撼。

dfs 中，所有的不合法情況全部在 base case 中處理了，recursion rule 就只需對(duì)四個(gè)方向進(jìn)行新的 dfs 而不用管是否合法。

451. Sort Characters By Frequency

tag：根據(jù)出現(xiàn)頻率排序 + bucket sort
與“出現(xiàn)頻率”有關(guān)的題目，首先想到 bucket sort（準(zhǔn)確的說是 counting sort），因?yàn)槌霈F(xiàn)的頻率是有上限的，即為輸入數(shù)據(jù)的長(zhǎng)度。在待排序數(shù)有上邊界的情況下，很適合使用 bucket sort。如果要求的輸出對(duì)相同 bucket 內(nèi)的順序不關(guān)心，那使用 List[] 即可；如果對(duì) bucket 內(nèi)部順序關(guān)心，可以考慮使用 PriorityQueue[]。

865. Smallest Subtree with all the Deepest Nodes

tag：lca 變種
本題是 lca 的變種，在 lca 的基礎(chǔ)上加上 depth 的元素。在 lca 中，dfs 的返回值是兩個(gè) tree node 中任意一個(gè)的 lca；在本題中，由于加入了 depth 的元素，因此每一層 dfs 的返回值中，不僅需要返回 tree node，也要返回 depth，因此返回值是一個(gè) Pair<Integer, TreeNode>。

739. Daily Temperatures (Mark)

tag：approach1: monotonic stack 的正確用法 / approach2: dp
本題有兩種做法：1. monotonic stack，2. dp。雖然用 dp 的做法從空間復(fù)雜度上會(huì)更優(yōu)秀 (O(1))，但是 monotonic stack 的方法也值得學(xué)習(xí)。

本題 dp 的本質(zhì)是，使用 dp 數(shù)組減少回看的次數(shù)。如果不用 dp，那么在位置 i 時(shí)，只能 linear scan 后面已經(jīng)遍歷過的元素。但如果維護(hù) dp 數(shù)組，在回看時(shí)可以很快跳到可能符合條件的位置，避免了linear scan。

本題 monotonic stack 的做法是：從左向右遍歷數(shù)組，讀到位置 i 的數(shù)時(shí)，將 monotonic stack 中所有小于的值的 index pop 出來(lái)，并更新對(duì)應(yīng) index 的 ans，然后將 i 放進(jìn)去。遍歷完成后將 monotonic stack 中剩余的 index 對(duì)應(yīng)的 ans 置為 0。這樣維護(hù)了一個(gè)單調(diào)遞減（準(zhǔn)確的說是單調(diào)不遞增）的單調(diào)棧。

1554. Strings Differ by One Character

tag：set + all possible combination that substitue a character with '*'
這道題的思路很巧妙，使用通配符代替原字符串當(dāng)中的一個(gè)字符，將一個(gè)字符串所有可能的通配符情況存儲(chǔ)在一個(gè) set 中。比如 "abcd" 的所有通配符情況是：“*bcd”, "a*cd", "ab*d", "abc*"。在遍歷 input 時(shí)，如果發(fā)現(xiàn)當(dāng)前字符串的某種通配符情況在 set 中出現(xiàn)過，則表示這兩者只差了一個(gè)字符，直接返回 true。如果遍歷到最后都沒有匹配的，返回 false。

本題的關(guān)鍵點(diǎn)在于 input 數(shù)組中所有的字符串都是不同的（unique），因此只要兩個(gè)字符串存在相同的通配符情況，則兩者必定差一個(gè)字符。如果 input 數(shù)組中有重復(fù)字符串，那么通配符相同時(shí)也可能是原字符串相同，遇到這種情況可以先用一個(gè) set 過濾掉 input 數(shù)組中相同的字符串，然后再操作。

518. Coin Change 2

tag：dp，完全想不到的 induction rule
這道題的第一想法是用 dfs 做，后來(lái)發(fā)現(xiàn)會(huì)超時(shí)，于是加上 buffer。buffer 本身便是一個(gè) int[][]，因此很自然能想到改寫為 dp，不過是一個(gè)二維 dp。

然而這道題并不需要二維 dp，只需要一維 dp 就能夠搞定。而一維 dp 的induction rule 確實(shí)難想，看了答案后又覺得理所應(yīng)當(dāng)。一維 dp 的物理意義是：dp[i] 表示組成 i money 有多少種方法。base case很簡(jiǎn)單想，dp[0] = 1。問題在于 induction rule。對(duì)于任意一個(gè) coin，dp[i] += dp[i-coin]，因此 induction rule 如下：

int[] dp = new int[amount + 1];
for(int coin : coins) {
  for(int i = coin; i < dp.length; i++) {
    dp[i] += dp[i - coin];
  }
}
return dp[amount];

這個(gè) induction rule 真是太妙了。

311. Sparse Matrix Multiplication (Mark)

tag：sparse matrix compression
本題的核心有兩個(gè)：一是如何壓縮 sparse matrix，二是壓縮后如何計(jì)算。

壓縮 sparse matrix 的方式為，將每個(gè)非零值用一個(gè) int[] 表示，其中 int[0]: row, int[1]: col, int[2]: val。使用一個(gè) List 存放每個(gè) int[]。由于遍歷過程的特殊性，能夠保證 int[] 之間是有序的。

基于壓縮 List 如何進(jìn)行乘法？可以發(fā)現(xiàn)，對(duì)于 matrix1 中的任意元素 m1，如果 matrix2 中的元素 m2 有 m1.col == m2.row，則需要相乘并更新 res[m1.row][m2.col]。使用雙指針 scan 兩個(gè)壓縮 List。

946. Validate Stack Sequences

tag：greedy algorithm
本題的思路是：每插入一個(gè)元素，都將所有符合 popped 的元素都 pop 出去，用一個(gè)指針記錄 pop 的index。最后看 popped 數(shù)組是否被全部 pop 掉。

1233. Remove Sub-Folders from the Filesystem

tag：sort input array?。?/em>
對(duì)于數(shù)組類的題目，沒有頭緒時(shí)試試 sort 一下，看看會(huì)有什么新發(fā)現(xiàn)。

// 2. swap diagonal
for(int i = 0; i < m; i++) {
    for(int j = i; j < n; j++) {  // 注意這里是 j = i
        swap(matrix, new int[]{i, j}, new int[]{j, i});
    }
}