LeetCode 簡略題解 - 1~100

#1 Two Sum

// #1 兩數之和

描述：給定一個整數數組和一個值target，求兩個下標i、j，使得a[i] + a[j] = target，返回下標。

// Description: Two Sum | LeetCode OJ

解法1：可以用哈希表不斷記錄每個元素對應的下標，然後查找target - a[i]就行了，查到了就有，查不到就沒有。時間空間複雜度都是O(N)。中規中矩。

// Solution 1: Use a hash table to record the index of every element and look for target - a[i] in the hash table. Positive, bingo; negative, keep looking. Time and space are both O(N). Will do.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/two-sum_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/two-sum_1_AC.cpp

解法2：把數組排序，然後前後兩指針向中間靠攏。如果數組本身有序，此方法更好。時間O(N * logN)，空間O(1)。

// Solution 2: Sort the array and let two pointers close in on each other from both ends. This works better when the array is already sorted. O(N * logN) time and O(1) space.

代碼2：太懶不寫

// Code 2: Too lazy to write.

#2 Add Two Numbers

// #2 兩數相加

描述：兩個大數，用鏈表表示。您給做個加法。

// Description: Add Two Numbers | LeetCode OJ

解法1：加唄。

// Solution 1: Just get it done.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/add-two-numbers_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/add-two-numbers_1_AC.cpp

#3 Longest Substring Without Repeating Characters

// #3 字母不帶重樣兒的最長子串

描述：給定一個字元串，看標題。

// Description: Longest Substring Without Repeating Characters | LeetCode OJ

解法1：用一個數組實時統計每個字母的出現次數，邊走邊數就行了。

// Solution 1: Maintain a counter array to keep the statistics of letters. Keep two pointers on watch and count as you go.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/longest-substring-without-repeating-characters_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-substring-without-repeating-characters_1_AC.cpp

#4 Median of Two Sorted Arrays

// #4 倆有序數組的中位數

描述：給定倆有序數組，找出把它倆合併後所得數組的中位數。要求對數時間搞定。

// Description: Median of Two Sorted Arrays | LeetCode OJ

解法1：暴力歸併，O(N)時間。

// Solution 1: Brute-force merge, O(N) time.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/median-of-two-sorted-arrays_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/median-of-two-sorted-arrays_1_AC.cpp

解法2：二分思想，遞歸實現。你要迭代也可以，不過代碼更複雜些就是了。然而這個解法不是O(logN)，而是O(log ^ 2 N)時間。更好的解法我還沒想出來。

// Solution 2: Binary search solution by recursion. Iterative solution is OK, but requires more sophisticated measures. Yet this is not an O(logN), but an O(log ^ 2 N) solution. Im still working on a better one.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/median-of-two-sorted-arrays_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/median-of-two-sorted-arrays_2_AC.cpp

#5 Longest Palindromic Substring

// #5 最長迴文子串

描述：如題。

// Description: Longest Palindromic Substring | LeetCode OJ

解法1：暴力過。

// Solution 1: Brute-force.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/longest-palindromic-substring_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-palindromic-substring_1_AC.cpp

解法2：Manacher演算法，動態規劃的經典實例。

// Solution 2: Manacher Algorithm, one of most classical application of dynamic programming.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/longest-palindromic-substring_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-palindromic-substring_2_AC.cpp

#6 ZigZag Conversion

// #6 字元串Z形排列

描述：給定字元串，按某種奇怪的方式排列一下。

// Description: ZigZag Conversion | LeetCode OJ

解法1：不涉及演算法，小心行事即可。

// Solution 1: Got nothing to do with algorthms, just beware of any bugs.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/zigzag-conversion_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/zigzag-conversion_1_AC.cpp

#7 Reverse Integer

// #7 反轉整數

描述：給定一個10進位整數，翻轉它。

// Description: Reverse Integer | LeetCode OJ

解法1：能用整數就別用浮點，能用數值就別用字元串。

// Solution 1: Make do with integer or numberic whenever possible. Extra type conversion means extra overhead.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-integer_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-integer_1_AC.cpp

#8 String to Integer (atoi)

// #8 字元串轉整數

描述：atoi，你懂的。

// Description: String to Integer (atoi) | LeetCode OJ

解法1：轉唄。

// Solution 1: Just do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/string-to-integer-atoi_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/string-to-integer-atoi_1_AC.cpp

#9 Palindrome Number

// #9 迴文數

描述：如題。

// Description: Palindrome Number | LeetCode OJ

解法1：跟迴文串一個道理。

// Solution 1: Same as palindromic strings.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/palindrome-number_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/palindrome-number_1_AC.cpp

#10 Regular Expression Matching

// #10 正則匹配

描述：如題。

// Description: Regular Expression Matching | LeetCode OJ

解法1：理解「回溯」二字。

// Solution 1 Try to understand the word "backtracking".

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/regular-expression-matching_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/regular-expression-matching_1_AC.cpp

#11 Container With Most Water

// #11 存水最多的容器

描述：給定一堆高矮不一的平行的牆，選擇其中兩堵作為兩壁，問最多能存多少水。

// Description: Container With Most Water | LeetCode OJ

解法1：O(N)演算法的思想很巧妙，需要一點推理。

// Solution 1: The O(N) solution is clever. Youll need a little reasoning to get ahold of it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/container-with-most-water_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/container-with-most-water_1_AC.cpp

#12 Integer to Roman

// #12 整數轉羅馬數字

描述：如題。

// Description: Integer to Roman | LeetCode OJ

解法1：模擬題。

// Solution 1: Simulation problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/integer-to-roman_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/integer-to-roman_1_AC.cpp

#13 Roman to Integer

// #13 羅馬數字轉整數

描述：如題。

// Description: Roman to Integer | LeetCode OJ

解法1：模擬題。

// Solution 1: Simulation problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/roman-to-integer_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/roman-to-integer_1_AC.cpp

#14 Longest Common Prefix

// #14 最長公共前綴

描述：給定一組字元串，找出最長公共前綴。

// Description: Longest Common Prefix | LeetCode OJ

解法1：找唄。

// Solution 1: Dont bother with trie or something.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/longest-common-prefix_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-common-prefix_1_AC.cpp

#15 3Sum

// #15 三數之和

描述：給定一個數組和一個值target，找出所有三數加起來等於target的組合。

// Description: 3Sum | LeetCode OJ

解法1：將數組排序，一維度自由，剩下兩維度按Two Sum來搞。時間O(N ^ 2)，空間O(1)。

// Solution 1: Sort the array. Set one dimension free and do Two Sum with the other two.O(N ^ 2) time and O(1) space.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/3sum_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/3sum_1_AC.cpp

#16 3Sum Closest

// #16 最接近的三數之和

描述：給定一個數組和一個值target，找出其中仨元素，使其加起來最接近target。

// Description: 3Sum Closest | LeetCode OJ

解法1：和3Sum思路類似，不過這次不斷更新結果即可。

// Solution 1: Similar to 3Sum, but this time we keep updating the result as we go.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/3sum-closest_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/3sum-closest_1_AC.cpp

#17 Letter Combinations of a Phone Number

// #17 手機鍵盤的字母組合

描述：Nokia手機，給定一個數字串，看看有多少種對應的字母串。

// Description: Letter Combinations of a Phone Number | LeetCode OJ

解法1：搜唄。

// Solution 1: Just make a search for it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/letter-combinations-of-a-phone-number_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/letter-combinations-of-a-phone-number_1_AC.cpp

#18 4Sum

// #18 四數之和

描述：不用多說了。

// Description: 4Sum | LeetCode OJ

解法1：兩維度自由，兩維度Two Sum。當然，該排序排序。

// Solution 1: Set two dimensions free, do a Two Sum on the other two. Sort the array if you have to.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/4sum_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/4sum_1_AC.cpp

#19 Remove Nth Node From End of List

// #19 刪除鏈表倒數第N個節點

描述：如題。

// Description: Remove Nth Node From End of List | LeetCode OJ

解法1：鏈表題，小心駛得萬年船。

// Solution 1: Cant be too careful with a linked list.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/remove-nth-node-from-end-of-list_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/remove-nth-node-from-end-of-list_1_AC.cpp

#20 Valid Parentheses

// #20 有效括弧序列

描述：給定一個括弧序列，判斷其是否合法。

// Description: Valid Parentheses | LeetCode OJ

解法1：用了個棧。

// Solution 1: Use a stack.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/valid-parentheses_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/valid-parentheses_1_AC.cpp

#21 Merge Two Sorted Lists

// #21 歸併兩個有序鏈表

描述：如題。

// Description: Merge Two Sorted Lists | LeetCode OJ

解法1：只要是鏈表題，就要極力避免new新節點。你可以從操作系統的角度去考慮一次new操作背後發生的事情，尤其是內核態的部分。知其然，弗若知其所以然。

// Solution 1: Avoid using 「new」 whenever dealing with a linked list problem. Think about the things behind a "new" operation, especially the kernel-space part. It takes more to get to the "how" and "why" than a mere "what".

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/merge-two-sorted-lists_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/merge-two-sorted-lists_1_AC.cpp

#22 Generate Parentheses

// #22 生成括弧。

描述：給定一個長度，生成所有此長度的合法括弧序列。

// Description: Generate Parentheses | LeetCode OJ

解法1：Catalan數知道吧？搜。

// Solution 1: Ever heard of the Catalan Numbers? Just DFS.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/generate-parentheses_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/generate-parentheses_1_AC.cpp

#23 Merge k Sorted Lists

// #23 歸併k個有序鏈表

描述：如題。

// Description: Merge k Sorted Lists | LeetCode OJ

解法1：快使用最小堆，紅紅火火。

// Solution 1: Yo, Min heap. Check it out, dogg.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/merge-k-sorted-lists_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/merge-k-sorted-lists_1_AC.cpp

#24 Swap Nodes in Pairs

// #24 交換節點對

描述：給定一個鏈表，每兩個節點做一下交換。

// Description: Swap Nodes in Pairs | LeetCode OJ

解法1：換唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/swap-nodes-in-pairs_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/swap-nodes-in-pairs_1_AC.cpp

#25 Reverse Nodes in k-Group

// #25 每k個節點反轉一下

描述：給定一個鏈表，每k個節點一組，做一次反轉。尾巴湊不齊的，自己看著辦。

// Description: Reverse Nodes in k-Group | LeetCode OJ

解法1：很容易出bug的題，小心行事。把常用操作單獨寫成函數是個好習慣。強行壓縮代碼長度，遲早是要栽跟頭的。

// Solution 1: A tricky problem, proceed with caution. Its good practice to wrap what you do frequently in a function. Excessive obsession with shortest code length is gonna bring you down, one of these days.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-nodes-in-k-group_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-nodes-in-k-group_1_AC.cpp

#26 Remove Duplicates from Sorted Array

// #26 去除有序數組的重複元素

描述：如題。

// Description: Remove Duplicates from Sorted Array | LeetCode OJ

解法1：水題。以後會經常寫這個的，就跟打字一樣。

// Solution 1: Piece of cake, youll be seeing a lot of this in the future.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-array_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-array_1_AC.cpp

#27 Remove Element

// #27 刪除元素

描述：刪除數組中所有等於某個值的元素。

// Description: Remove Element | LeetCode OJ

解法1：刪唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/remove-element_1.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/remove-element_1.cpp

#28 Implement strStr()

// #28 實現strStr()

描述：字元串匹配，經典問題。

// Description: Implement strStr() | LeetCode OJ

解法1：暴力過，O(N ^ 2)時間。

// Solution 1: Brute-force solution with O(N ^ 2) time.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/implement-strstr_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/implement-strstr_1_AC.cpp

解法2：Rabin-Karp演算法。對字元串做哈希是一種非常巧妙的做法，這種思想在很多情景下可以大大提高匹配效率。有必要的話，可以複查以嚴格保證匹配的正確性。

// Solution 2: Rabin-Karp Algorithm. Hashing a string is clever way to immensely accelerate pattern matching. Double check if you cant tolerate false positives.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/implement-strstr_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/implement-strstr_2_AC.cpp

解法3：傳說中的KMP演算法，一個我寫了不下十次還是很難獨立一次性寫對的演算法。next數組堪稱藝術品，很清真。

// Solution 3: The legendary KMP Algorithm, which I cant possibly write down perfectly even after using a dozen of it. The "next" array is simply a great work of art, as beautiful as it is powerful.

代碼3：https://github.com/zhuli19901106/leetcode-2/blob/master/implement-strstr_3_AC.cpp

// Code 3: https://github.com/zhuli19901106/leetcode-2/blob/master/implement-strstr_3_AC.cpp

#29 Divide Two Integers

// #29 兩整數相除

描述：不準乘除，不準膜。

// Description: Divide Two Integers | LeetCode OJ

解法1：加減配合移位。照搞不誤。

// Solution 1: +-&|<<, nomsayin?

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/divide-two-integers_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/divide-two-integers_1_AC.cpp

#30 Substring with Concatenation of All Words

// #30 由所有單詞連成的子串

描述：給定一個無重複單詞的字典D，和一個長字元串S。找出S中的子串，該子串恰好是D中所有單詞連接而成。

// Description: Substring with Concatenation of All Words | LeetCode OJ

解法1：碰見這種字典多而短的問題，本能地會想到字典樹。其實用也可以，不用也可以。反正都要搜索一番。然而我閑字典樹麻煩，所以想到用哈希值來代替字元串，這樣能夠O(1)時間進行匹配。結果確實很不錯。哈希大法好，但有一點要記住：雖然哈希碰撞很難發生，但墨菲定律在那兒擺著，不檢查的話遲早要完。

// Solution 1: Its intuitive to think of trie when dealing with a large dictionary of short words. Use it or not, youll figure out a solution yourself. I chose string hashing to accelerate my string matching, which worked out just fine. Hashing it powerful, but keep Murphys Law in mind, that hashing collisons do happen. You dont do a double check, your call.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/substring-with-concatenation-of-all-words_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/substring-with-concatenation-of-all-words_1_AC.cpp

#31 Next Permutation

// #31 下一個排列

描述：給定一個排列，按照字典序把下一個弄出來。

// Description: Next Permutation | LeetCode OJ

解法1：O(N)時間，注意要從後往前找。

// Solution 1: O(N) time. Search from back to front.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/next-permutation_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/next-permutation_1_AC.cpp

#32 Longest Valid Parentheses

// #32 最長合法括弧子串

描述：給定一個括弧序列，找出最長的合法括弧子串。

// Description: Longest Valid Parentheses | LeetCode OJ

解法1：碰見這種子串問題，基本都是一前一後兩個指針，不過寫法倒是各有不同。看代碼。

// Solution 1: These "substring" problems can usually be solved with two running pointers. Although they come in various forms. Find more in the code.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/longest-valid-parentheses_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-valid-parentheses_1_AC.cpp

#33 Search in Rotated Sorted Array

// #33 旋轉過有序數組的查找問題

描述：一個有序數組，可能進行了循環移位，在裡面進行查找。

// Description: Search in Rotated Sorted Array | LeetCode OJ

解法1：先把旋轉的偏移量算出來，再二分查找。兩部分都是O(logN)，所以還行。

// Solution 1: Find the rotation offset and do an offsetted binary search. Both parts are O(logN), works for me.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/search-in-rotated-sorted-array_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/search-in-rotated-sorted-array_1_AC.cpp

#34 Search for a Range

// #34 找區間。

描述：給定一個有序數組，找出某個值的起始和終止區間。

// Description: Search for a Range | LeetCode OJ

解法1：lower_bound和upper_bound一起用。

// Solution 1: lower_bound and upper_bound will suffice.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/search-for-a-range_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/search-for-a-range_1_AC.cpp

#35 Search Insert Position

// #35 尋找插入位置

描述：給定有序數組和一個值，尋找合適的插入位置。

// Description: Search Insert Position | LeetCode OJ

解法1：二分。

// Solution 1: Binary search.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/search-insert-position_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/search-insert-position_1_AC.cpp

#36 Valid Sudoku

// #36 檢查數獨

描述：如題。

// Description: Valid Sudoku | LeetCode OJ

解法1：按規矩來唄。

// Solution 1: Routine.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/valid-sudoku_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/valid-sudoku_1_AC.cpp

#37 Sudoku Solver

// #37 解數獨

描述：如題。

// Description: Sudoku Solver | LeetCode OJ

解法1：標準遞歸回溯問題，注意遞歸寫法，不要增加不必要的複雜度。跳舞鏈神馬的，還是算了吧，太複雜。

// Solution 1: A typical DFS + backtracking problem. Write it carefully though, dont incur unnecessary time complexity. As for Dancing Links, Ill forget about it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/sudoku-solver_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/sudoku-solver_1_AC.cpp

#38 Count and Say

// #38 數數

描述：給定一個數字串，讀出來。並把讀的方法也表示成一個數字串。如此計算出第N個串。

// Description: Count and Say | LeetCode OJ

解法1：不知道有沒有什麼數學解法？

// Solution 1: Is there any analytical solution? I mean, mathematically?

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/count-and-say_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/count-and-say_1_AC.cpp

#39 Combination Sum

// #39 組合之和

描述：給定一個集合以及一個值target，找出所有加起來等於target的組合，要不帶重樣兒的。每個元素可以用無數次。

// Description: Combination Sum | LeetCode OJ

解法1：搜。

// Solution 1: DFS.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/combination-sum_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/combination-sum_1_AC.cpp

#40 Combination Sum II

// #40 組合之和2

描述：和之前差不多，區別是每個元素只能用一次。

// Description: Combination Sum II | LeetCode OJ

解法1：搜。

// Solution 1: DFS.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/combination-sum-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/combination-sum-ii_1_AC.cpp

#41 First Missing Positive

// #41 第一個未出現的正數

描述：給定無序數組，找出第一個未出現的正整數。

// Description: First Missing Positive | LeetCode OJ

解法1：數組本身就可以用於標記。

// Solution 1: The input array itself can be used as marker array.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/first-missing-positive_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/first-missing-positive_1_AC.cpp

#42 Trapping Rain Water

// #42 雨水積水問題

描述：給定一個地形，計算能存多少雨水。

// Description: Trapping Rain Water | LeetCode OJ

解法1：不要考慮一個水坑能存多少水，而要考慮每一條能存多少雨水，這種違背直觀的思考方式反而更容易編程。

// Solution 1: Dont try to calculate how much water can be trapped in a water pit. Think about how much water can be stored in each "stripe". This counter-intuitive way of thinking is actually better suited for programming.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/trapping-rain-water_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/trapping-rain-water_1_AC.cpp

#43 Multiply Strings

// #43 高精度乘法

描述：如題。

// Description: https://github.com/zhuli19901106/leetcode-2/blob/master/multiply-strings_1_AC.cpp

解法1：暴力。FFT解法我沒寫。

// Solution 1: Brute-force. I didnt write the FFT solution myself, too much trouble.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/multiply-strings_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/multiply-strings_1_AC.cpp

#44 Wildcard Matching

// #44 通配符

描述：模式匹配的另一個基礎示例。

// Description: Wildcard Matching | LeetCode OJ

解法1：還是回溯。值得注意的是如何想辦法剪枝。

// Solution 1: Use backtracking. How to do the pruning is one of the things worth noting.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/wildcard-matching_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/wildcard-matching_1_AC.cpp

#45 Jump Game II

// #45 青蛙跳2

描述：和Jump Game一樣，這次計算最小步數。

// Description: Jump Game II | LeetCode OJ

解法1： 掃一遍就行了。

// Solution 1: Sweep it over.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/jump-game-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/jump-game-ii_1_AC.cpp

#46 Permutations

// #46 全排列

描述：列印全排列。

// Description: Permutations | LeetCode OJ

解法1：用next_permutation迭代。

// Solution 1: Iterate with next_permutation.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/permutations_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/permutations_1_AC.cpp

解法2：DFS。

// Solution 2: DFS.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/permutations_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/permutations_2_AC.cpp

#47 Permutations II

// #47 全排列2

描述：和Permutations一樣，不過序列可能有重複元素。

// Description: Permutations II | LeetCode OJ

解法1：用next_permutation迭代，不過函數自己寫。

// Solution 1: Iterate with next_permutation, but write your own this time.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/permutations-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/permutations-ii_1_AC.cpp

#48 Rotate Image

// #48 旋轉圖像

描述：順時針旋轉90度，盡量不用額外空間。

// Description: Rotate Image | LeetCode OJ

解法1：矩陣分四塊兒就行。輪換著賦值，可保證O(1)空間。

// Solution 1: Segment the matrix into 2 by 2. By doing the value reassignments in a rotated manner, O(1) space is thus achieved.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/rotate-image_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/rotate-image_1_AC.cpp

#49 Group Anagrams

// #49 變位詞歸類

描述：給定一堆單詞，把變位詞放一塊兒去。

// Description: Group Anagrams | LeetCode OJ

解法1：變位詞排序之後就一樣了。

// Solution 1: Anagrams become one after sorting.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/anagrams_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/anagrams_1_AC.cpp

#50 Pow(x, n)

// #50 冪

描述：求冪。

// Description: Pow(x, n) | LeetCode OJ

解法1：快速冪。

// Solution 1: Binary exponentiation.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/powx-n_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/powx-n_1_AC.cpp

#51 N-Queens

// #51 N皇后

描述：NxN棋盤擺N個棋子，要求不能同行、同列、同對角線、同反對角線，返回所有擺法。

// Description: N-Queens | LeetCode OJ

解法1：DFS + 回溯.

// Solution 1: DFS + backtracking.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/n-queens_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/n-queens_1_AC.cpp

#52 N-Queens II

// #52 N-Queens II

描述：N皇后問題，輸出解的個數。

// Description: N-Queens II | LeetCode OJ

解法1：目前並沒有數學解，所以還是搜。

// Solution 1: Theres currently no known formula for N-queen problem. So well do it the old way.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/n-queens-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/n-queens-ii_1_AC.cpp

#53 Maximum Subarray

// #53 最大子數組和

描述：如題。

// Description: Maximum Subarray | LeetCode OJ

解法1：教材經典例子。

// Solution 1: Algo 101 on the textbook.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-subarray_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-subarray_1_AC.cpp

#54 Spiral Matrix

// #54 螺旋矩陣

描述：按螺旋方式遍歷矩陣。

// Description: Spiral Matrix | LeetCode OJ

解法1：模擬題。

// Solution 1: Simulation problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/spiral-matrix_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/spiral-matrix_1_AC.cpp

#55 Jump Game

// #55 青蛙跳

描述：給定一個數組A，每個A[i]表示你最遠能跳的距離。從0出發問是否能跳到終點。

// Description: Jump Game | LeetCode OJ

解法1：掃一遍就行了。

// Solution 1: Jump ahead, dont look back.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/jump-game_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/jump-game_1_AC.cpp

#56 Merge Intervals

// #56 歸併區間

描述：給定一些區間，該合併合併。

// Description: Merge Intervals | LeetCode OJ

解法1：排個序，歸併。

// Solution 1: Sort and merge.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/merge-intervals_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/merge-intervals_1_AC.cpp

#57 Insert Interval

// #57 插入區間

描述：給定一堆區間，插入一個新區間。

// Description: Insert Interval | LeetCode OJ

解法1：跟Merge Intervals一個思路。

// Solution 1: Similar to Merge Intervals.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/insert-interval_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/insert-interval_1_AC.cpp

#58 Length of Last Word

// #58 最後一個詞的長度

描述：如題。

// Description: Length of Last Word | LeetCode OJ

解法1：無聊。

// Solution 1: Boring.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/length-of-last-word_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/length-of-last-word_1_AC.cpp

#59 Spiral Matrix II

// #59 旋轉矩陣2

描述：把1之n ^ 2按照螺旋順序填入方陣。

// Description: Spiral Matrix II | LeetCode OJ

解法1：模擬題。

// Solution 1: Simulation problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/spiral-matrix-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/spiral-matrix-ii_1_AC.cpp

#60 Permutation Sequence

// #60 排列序列

描述：1~n有n!個排列，找出其中字典序排第k的排列。

// Description: Permutation Sequence | LeetCode OJ

解法1：看代碼吧。

// Solution 1: Just read the code.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/permutation-sequence_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/permutation-sequence_1_AC.cpp

#61 Rotate List

// #61 旋轉鏈表

描述：給定一個鏈表， 循環移位k次。

// Description: Rotate List | LeetCode OJ

解法1：要面面俱到。

// Solution 1: Mind the edge cases.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/rotate-list_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/rotate-list_1_AC.cpp

#62 Unique Paths

// #62 不同路徑

描述： 給定MxN棋盤，只允許從左上往右下走，每次走一格。共有多少種走法？

// Description: Unique Paths | LeetCode OJ

解法1：排列組合。

// Solution 1: Combination.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/unique-paths_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/unique-paths_1_AC.cpp

#63 Unique Paths II

// #63 不同路徑2

描述：和之前一樣，不過這次有些格子不讓走。

// Description: Same as before, only in that some grids are blocked.

解法1：動態規劃。

// Solution 1: Dynamic programming.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/unique-paths-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/unique-paths-ii_1_AC.cpp

#64 Minimum Path Sum

// #64 最小路徑和

描述：和Unique Paths一樣，不過這次每個點有權值，求最小路徑和。

// Description: Same as Unique Paths, but this time we assign a weight to each grid and calculate minimum weight sum for the path.

解法1：DP。

// Solution 1: DP.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-path-sum_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-path-sum_1_AC.cpp

#65 Valid Number

// #65 數值判斷

描述：給定一個字元串，判斷是否符合數值類型的格式。

// Description: Valid Number | LeetCode OJ

解法1：典型的面試題，考察思維是否足夠縝密。照理說一個正則表達式可以搞定，不過編譯直接超時了，說明伺服器對這個做了限制。所以只得手寫各種判斷。此題無須奇技淫巧，惟「認真」二字足矣。

// Solution 1: A typical filter for discreet thinkers. I thought a regular expression would suffice, but the compilation simply timed out. It appears the OJ servers discourage such attempt. Som no fancy tricks needed, just think it through and do it carefully.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/valid-number_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/valid-number_1_AC.cpp

#66 Plus One

// #66 加一

描述：高精度加一。

// Description: Plus One | LeetCode OJ

解法1：加唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/plus-one_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/plus-one_1_AC.cpp

#67 Add Binary

// #67 二進位加法

描述：二進位高精度加法。

// Description: Add Binary | LeetCode OJ

解法1：加唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/add-binary_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/add-binary_1_AC.cpp

#68 Text Justification

// #68 文字對齊

描述：給定一列單詞，按照指定寬度將其排成格式工整的洋文。

// Description: Text Justification | LeetCode OJ

解法1：注意邊界條件。

// Solution 1: Edge cases.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/text-justification_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/text-justification_1_AC.cpp

#69 Sqrt(x)

// #69 開方

描述：整數開方

// Description: Sqrt(x) | LeetCode OJ

解法1：二分吧，你要牛頓法也行。

// Solution 1: Binary search will do. Newton-Raphson method is OK but a bit overpowered.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/sqrtx_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/sqrtx_1_AC.cpp

#70 Climbing Stairs

// #70 爬樓梯

描述：爬樓梯，每次能往上爬一或兩級，問總共有多少種爬法。

// Description: Climbing Stairs | LeetCode OJ

解法1：斐波那契。

// Solution 1: Fibonacci.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/climbing-stairs_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/climbing-stairs_1_AC.cpp

#71 Simplify Path

// #71 簡化路徑

描述：如題。

// Description: Simplify Path | LeetCode OJ

解法1：棧。

// Solution 1: Stack.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/simplify-path_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/simplify-path_1_AC.cpp

#72 Edit Distance

// #72 編輯距離

描述：最短編輯距離，也叫Levenshtein距離。

// Description: Edit Distance | LeetCode OJ

解法1：動態規劃經典問題。

// Solution 1: A classic DP problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/edit-distance_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/edit-distance_1_AC.cpp

#73 Set Matrix Zeroes

// #73 矩陣置0

描述：給定一個矩陣，只要某個元素為0，就把對應的整行整列都置0。

// Description: Set Matrix Zeroes | LeetCode OJ

解法1：巧妙的地方在於如何避免外開闢空間，看代碼吧。

// Solution 1: The tricky part is to do it in-place. Read the code for more detail.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/set-matrix-zeroes_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/set-matrix-zeroes_1_AC.cpp

#74 Search a 2D Matrix

// #74 二維矩陣查找

描述：給定一個二維數組，balabala。

// Description: Search a 2D Matrix | LeetCode OJ

解法1：說白了，就是個一維有序數組。

// Solution 1: Expand it into an 1-d array, youll see.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/search-a-2d-matrix_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/search-a-2d-matrix_1_AC.cpp

#75 Sort Colors

// #75 顏色排序

描述：給定三中間色，分別標號為012， 按這個標號排序。

// Description:

解法1：這種題除了用來面試，簡直狗屁不通。正所謂千年科舉，牢籠人才。天下讀書人，一門心思都給了八股制藝，倒沒幾個人去富國強兵、振興科教。這種為出題而出題的腦殘面試題，豈不如出一轍？實乃可笑！你喜歡出這種賣弄奇技淫巧的面試題，我就如你所願，寫這麼個「聰明」的解法。你說把0、1、2的個數都數出來不就得了？我偏要玩兒出個花兒來。否則，怎麼顯示我琢磨面試題下的苦功？倘若天下人都一門心思琢磨怎麼考試，這國家也就藥丸了。

// Solution 1: F* this problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/sort-colors_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/sort-colors_1_AC.cpp

#76 Minimum Window Substring

// #76 最小窗口子串

描述：給定一個長串S和一個短串T。求S中包含T所有字母的最短字串。

// Description: Minimum Window Substring | LeetCode OJ

解法1：凡是這種滑動窗口的問題，都是兩個指針一前一後，你追我趕。

// Solution 1: All such "sliding window" problems can be tackled with two running pointers, one after the other.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-window-substring_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-window-substring_1_AC.cpp

#77 Combinations

// #77 組合

描述：從1~N里選K個數，輸出所有選法。

// Description: Combinations | LeetCode OJ

解法1：DFS。

// Solution 1: DFS.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/combinations_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/combinations_1_AC.cpp

解法2：類似next_permutation。

// Solution 2: Similar to next_permutation.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/combinations_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/combinations_2_AC.cpp

#78 Subsets

// #78 子集

描述：冪集。

// Description: Subsets | LeetCode OJ

解法1：DFS。

// Solution 1: DFS.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/subsets_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/subsets_1_AC.cpp

解法2：冪集中的元素和0~2 ^ n - 1可構成雙射。

// Solution 2: There exists a bijection between the power set and {0, 1, ..., 2 ^ n - 1}, where n is the cardinality of the set S.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/subsets_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/subsets_2_AC.cpp

#79 Word Search

// #79 找單詞

描述：給定一個字母矩陣，允許從任一點出發四處走。看軌跡能否構成一個單詞。

// Description: Word Search | LeetCode OJ

解法1：DFS。

// Solution 1: DFS.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/word-search_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/word-search_1_AC.cpp

#80 Remove Duplicates from Sorted Array II

// #80 有序數組去重2

描述：和之前一樣，不過這次允許元素重複一次。

// Description: Remove Duplicates from Sorted Array II | LeetCode OJ

解法1：小把戲。

// Solution 1: Small trick.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-array-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-array-ii_1_AC.cpp

#81 Search in Rotated Sorted Array II

// #81 有序旋轉數組查找2

描述：和之前一樣，不過這次數組裡可能有重複元素。

// Description: Search in Rotated Sorted Array II | LeetCode OJ

解法1：對於相等元素，必須跳過，否則無從得知，這有序的部分究竟在重複元素的左側還是右側。所以時間複雜度最壞可以達到O(N)。

// Solution 1: The duplicates must be skipped one by one, or else theres no way to know which way to go during the binary search. Thus the worst-case time complexity can be O(N).

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/search-in-rotated-sorted-array-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/search-in-rotated-sorted-array-ii_1_AC.cpp

#82 Remove Duplicates from Sorted List II

// #82 有序鏈表去重2

描述：給定有序鏈表，凡有重複元素者，盡數去除。

// Description: Remove Duplicates from Sorted List II | LeetCode OJ

解法1：去唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-list-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-list-ii_1_AC.cpp

#83 Remove Duplicates from Sorted List

// #83 有序鏈表去重

描述：和之前一樣，這次只去掉重複部分。

// Description: Remove Duplicates from Sorted List | LeetCode OJ

解法1：去唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-list_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/remove-duplicates-from-sorted-list_1_AC.cpp

#84 Largest Rectangle in Histogram

// #84 直方圖中的最大矩形

描述：給定一個直方圖，求其能覆蓋的最大矩形。

// Description: Largest Rectangle in Histogram | LeetCode OJ

解法1：和Trapping Rain Water那題一樣，從每一條的角度來考慮問題。看向左向右各能延伸多長，用DP可以O(N)時間解決。

// Solution 1: Same as Trapping Rain Water, consider the problem from each single stripe. Calculate the left and right boundary for the stripes using DP in O(N) time, then we have the answer.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/largest-rectangle-in-histogram_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/largest-rectangle-in-histogram_1_AC.cpp

#85 Maximal Rectangle

// #85 最大矩形

描述：給定一個01矩陣，找出其中全由1構成的最大矩形。

// Description: Maximal Rectangle | LeetCode OJ

解法1：這題有意思，可以利用Largest Rectangle in Histogram那題的思路來做，請看代碼。把一個問題化歸為另一個問題，是復用代碼的常見手段。

// Solution 1: An interesting problem. We can use Largest Rectangle in Histogram to solve this one. Please read the code. Its common practice to convert one problem to another, so that we can reuse existing code.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/maximal-rectangle_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/maximal-rectangle_1_AC.cpp

#86 Partition List

// #86 劃分鏈表

描述：給定一個鏈表和一個值，把小於等於和大於該值的部分分別放到鏈表的一前一後去。

// Description:

解法1：分為兩個鏈表，然後合併即可。

// Solution 1: Split in two and concatenate as one.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/partition-list_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/partition-list_1_AC.cpp

#87 Scramble String

// #87 亂序字元串

描述：給定一個字元串S，允許遞歸地將其分為左右兩部分並調換位置，稱其為「亂序」。現給定兩字元串，判斷其是否互為「亂序」。

// Description: Scramble String | LeetCode OJ

解法1：DP。不知道有沒有O(N^3)時間的解法？

// Solution 1: DP. I wonder if theres an O(N ^ 3) solution?

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/scramble-string_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/scramble-string_1_AC.cpp

#88 Merge Sorted Array

// #88 歸併有序數組

描述：給定有序數組a1和a2，把a2歸併到a1中。

// Description: Merge Sorted Array | LeetCode OJ

解法1：並唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/merge-sorted-array_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/merge-sorted-array_1_AC.cpp

#89 Gray Code

// #89 格雷碼

描述：生成N位格雷碼。

// Description: Gray Code | LeetCode OJ

解法1：想想N - 1位格雷碼和N位格雷碼的關係。

// Solution 1: Think about the relationship between (N - 1)-bit gray code and N-bit gray code.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/gray-code_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/gray-code_1_AC.cpp

#90 Subsets II

// #90 子集2

描述：還是冪集，不過這次是多重集的冪集。

// Description: Subsets II | LeetCode OJ

解法1：因為是多重集，所以這次咱還是搜吧。其實雙射還是存在的，不過代碼沒那麼好寫了，所以我懶得寫。

// Solution 1: Id prefer DFS this time. Although the bijection still exists, the code isnt as easy to write. Never mind.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/subsets-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/subsets-ii_1_AC.cpp

#91 Decode Ways

// #91 解碼方式

描述：將A~Z和1~26一一映射，現在給定一個數字串，請計算有多少種不同的解碼方式。

// Description: Decode Ways | LeetCode OJ

解法1：這個可以DP。

// Solution 1: DP will do.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/decode-ways_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/decode-ways_1_AC.cpp

#92 Reverse Linked List II

// #92 反轉鏈表2

描述：給定一個鏈表，反轉第m~n個節點。

// Description: Reverse Linked List II | LeetCode OJ

解法1：分前中後三部分完成。

// Solution 1: Split in three.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-linked-list-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-linked-list-ii_1_AC.cpp

#93 Restore IP Addresses

// #93 還原IP地址

描述：給定一個沒加點的IP地址，返回所有可能的合法IP地址。

// Description: Restore IP Addresses | LeetCode OJ

解法1：加唄。

// Solution 1: Do it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/restore-ip-addresses_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/restore-ip-addresses_1_AC.cpp

#94 Binary Tree Inorder Traversal

// #94 二叉樹中序遍歷

描述：如題。

// Description: Binary Tree Inorder Traversal | LeetCode OJ

解法1：遞歸。

// Solution 1: Recursive.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/binary-tree-inorder-traversal_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/binary-tree-inorder-traversal_1_AC.cpp

解法2：迭代。

// Solution 2: Iterative.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/binary-tree-inorder-traversal_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/binary-tree-inorder-traversal_2_AC.cpp

#95 Unique Binary Search Trees II

// #95 不同二叉搜索樹2

描述：輸出中序遍歷是{1, 2, ..., n}的所有二叉搜索樹。

// Description: Unique Binary Search Trees II | LeetCode OJ

解法1：DFS。

// Solution 1: DFS.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/unique-binary-search-trees-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/unique-binary-search-trees-ii_1_AC.cpp

#96 Unique Binary Search Trees

// #96 不同二叉搜索樹

描述：輸出中序遍歷是{1, 2, ..., n}的所有二叉搜索樹個數。

// Description: Unique Binary Search Trees | LeetCode OJ

解法1：Catalan數。為什麼呢？自己想。

// Solution 1: Catalan Number.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/unique-binary-search-trees_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/unique-binary-search-trees_1_AC.cpp

#97 Interleaving String

// #97 交叉字元串

描述：給定仨字元串S1、S2、S3，判斷S3是否可以由S1和S2交叉而成。

// Description: Interleaving String | LeetCode OJ

解法1：DP。

// Solution 1: DP.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/interleaving-string_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/interleaving-string_1_AC.cpp

#98 Validate Binary Search Tree

// #98 驗證二叉搜索樹

描述：給定二叉樹，判斷是否為二叉搜索樹。

// Description: Validate Binary Search Tree | LeetCode OJ

解法1：針對「有序」二字做文章即可。

// Solution 1: Dig around the word 「order」.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/validate-binary-search-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/validate-binary-search-tree_1_AC.cpp

#99 Recover Binary Search Tree

// #99 恢復二叉搜索樹

描述：二叉搜索樹中的兩個節點被調換了，麻煩給調回來。

// Description: Recover Binary Search Tree | LeetCode OJ

解法1：執行中序遍歷，找出兩個節點。注意邊界情況。

// Solution 1: Perform an inorder traversal to locate target nodes. Watch for edge cases.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/recover-binary-search-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/recover-binary-search-tree_1_AC.cpp

解法2：應出題者裝逼要求，強行寫了個Morris中序遍歷。難道現在面試都要求會寫Morris遍歷了？真乃世道艱危，國將不國啊。你敢再讓寫一遍這破玩意兒，我豬某寧死也要投降。

// Solution 2: Is this showing off or zhuangbi?

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/recover-binary-search-tree_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/recover-binary-search-tree_2_AC.cpp

#100 Same Tree

// #100 同一棵樹

描述：同一個夢想。

// Description: Same Tree | LeetCode OJ

解法1：遞歸或者迭代，甚至序列化都行，烯烴尊便。

// Solution 1:

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/same-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/same-tree_1_AC.cpp