LeetCode 簡略題解 - 201~300

02-07

#201 Bitwise AND of Numbers Range

// #201 區間按位與

描述：給定一個整數閉區間，求其所有數的按位與。

// Description: Bitwise AND of Numbers Range | LeetCode OJ

解法1：此解法很巧妙，我很欣慰。

// Solution 1: A clever solution, which took me about half an hour to figure out.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/bitwise-and-of-numbers-range_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/bitwise-and-of-numbers-range_1_AC.cpp

#202 Happy Number

// #202 幸福數

描述：給定一個數，不斷將此數變為此數各位數字的平方和。如果能夠終止於1，則稱為幸福數。所以，你幸福嗎？

// Description:

解法1：我姓朱。

// Solution 1: Im flappy.

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

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

#203 Remove Linked List Elements

// #203 去除鏈表元素

描述：刪除鏈表中某特定值的所有節點。

// Description: Remove Linked List Elements | LeetCode OJ

解法1：刪唄。

// Solution 1: Do it.

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

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

#204 Count Primes

// #204 數質數

描述：統計小於n的質數個數。

// Description: Count Primes | LeetCode OJ

解法1：篩法。

// Solution 1: Sieve of Eratosthenes.

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

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

#205 Isomorphic Strings

// #205 同構字元串

描述：給定倆字元串，判斷能否通過字元間的一一對應關係，把前者變成後者。

// Description: Isomorphic Strings | LeetCode OJ

解法1：既然是一一對應嘛，用兩個哈希表就行了。

// Solution 1: Two hash map for one bijection.

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

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

#206 Reverse Linked List

// #206 反轉鏈表

描述：如題。

// Description: Reverse Linked List | LeetCode OJ

解法1：要做到分分鐘搞定的程度。

// Solution 1: Basic training.

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

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

#207 Course Schedule

// #207 課程表

描述：有n門課，給定一些前置課規則和一份選課列表，判斷能否完成所有課程。

// Description: Course Schedule | LeetCode OJ

解法1：拓撲排序。

// Solution 1: Topological sort.

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

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

#208 Implement Trie (Prefix Tree)

// #208 實現字典樹（前綴樹）

描述：實現字典樹，能插入單詞，能查找單詞、前綴。

// Description: Implement Trie (Prefix Tree) | LeetCode OJ

解法1：空間申請了，就要釋放。對象構造了，就要析構。反觀我朱某人，許多事卻都半途而廢，慚愧啊。

// Solution 1: Finish what you started.

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

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

#209 Minimum Size Subarray Sum

// #209 最短子數組和

描述：給定一個數組和一個值，找出不小於該值得最短子數組。

// Description: Minimum Size Subarray Sum | LeetCode OJ

解法1：倆指針搞定。

// Solution 1: Two pointers will do.

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

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

#210 Course Schedule II

// #210 課程表2

描述：和之前一樣，不過這次要返回一種可行的上課順序。

// Description: Course Schedule II | LeetCode OJ

解法1：拓撲排序。

// Solution 1: Topological sort.

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

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

#211 Add and Search Word - Data structure design

// #211 添加查找單詞 - 數據結構設計

描述：設計一個數據結構，能夠插入單詞，能夠查找字元串，並支持正則表達式中的「.」單字元通配。

// Description: Add and Search Word - Data structure design | LeetCode OJ

解法1：DFS配合字典樹，效率其實並不高。有意思的事我居然一次AC了。

// Solution 1: DFS on a trie, works but not very efficient. Still, one shot one kill is good enough.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/add-and-search-word-data-structure-design_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/add-and-search-word-data-structure-design_1_AC.cpp

#212 Word Search II

// #212 找單詞2

描述：和之前一樣，不過這次要找出矩陣中所有的單詞。

// Description: Word Search II | LeetCode OJ

解法1：還是DFS。

// Solution 1: DFS.

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

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

#213 House Robber II

// #213 小偷2

描述：跟之前一樣，不過這次房子圍成一個圈，所以首尾也算是相鄰的。問該怎麼偷。

// Description: House Robber II | LeetCode OJ

解法1：既然首尾相鄰了，我們就把按照首尾，分兩種情況考慮。

// Solution 1: Since 0 and n - 1 are now considered adjacent, we cover both situations separately.

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

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

#214 Shortest Palindrome

// #214 最短迴文串

描述：給定字元串，允許你在開頭添加字母，將其變為一個迴文串。問最少需要添加幾個字母。

// Description: Shortest Palindrome | LeetCode OJ

解法1：用哈希可以將字元串匹配的時間複雜度降低一個維度，前提是你忽略碰撞的可能性。所以這個方法可以寫出O(N)的演算法。此外還要記住一點：KMP演算法中的next數組是非常有用的，不論是最長迴文前綴、最長迴文後綴、最短循環節等等問題，都可以用類似的思路搞定。因為，這些問題是可以相互轉換，舉一反三、融會貫通者，此之謂也。這題也一樣可以用類似方法搞定。

// Solution 1: String hashing can reduce the time complexity of matching by one dimension, thus you can write an O(N) solution if youre willing to ignore the possibility of hashing collision. Also, keep in mind that the "next" array in KMP Algorithm is very powerful. Whether its longest palindromic prefix, suffix or shortest repetend that you want, itll help you get the job done. Thats what I call "you see one, you see them all". The same works for this one, too.

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

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

#215 Kth Largest Element in an Array

// #215 數組中第k大的元素

描述：如題。

// Description: Kth Largest Element in an Array | LeetCode OJ

解法1：你能手寫快速排序吧？面試經常考哦。稍加修改就變成快速選擇演算法了。用此演算法可以找出第k小元素。

// Solution 1: Can you write by Quick Sort hand? They say its a popular problem. It can be easily modified to Quick Select algorithm which can be used to find the k-th smallest element.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/kth-largest-element-in-an-array_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/kth-largest-element-in-an-array_1_AC.cpp

#216 Combination Sum III

// #216 組合之和3

描述：用k個1~9加成一個數n，求所有組合方式。

// Description: Combination Sum III | LeetCode OJ

解法1：DFS。

// Solution 1: DFS.

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

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

#217 Contains Duplicate

// #217 數組查重

描述：如題。

// Description: Contains Duplicate | LeetCode OJ

解法1：哈希。

// Solution 1: Hash.

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

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

#218 The Skyline Problem

// #218 輪郭線問題

描述：給定一些矩形建築物的橫縱坐標，求出總體輪廓線的形狀。

// Description: The Skyline Problem | LeetCode OJ

解法1：這題解法可以很多，但關鍵都是一點：隨時獲取當前最高建築物的高度。用map或者priority_queue都行，只要保證有序。

// Solution 1: This problem can be handled in various ways, all focus but on one point: knowing the height of the current highest building. Using either map or priority_queue is OK, as both are sorted data structures.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/the-skyline-problem_1_AC.cpp

#219 Contains Duplicate II

// #219 數組查重2

描述：和之前一樣，不過這次要求兩重複元素必須距離不超過k。

// Description: Contains Duplicate II | LeetCode OJ

解法1：不就是滑動窗口嘛。

// Solution 1: So its sliding window this time.

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

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

#220 Contains Duplicate III

// #220 數組查重3

描述：和之前一樣，不過這次倆元素之間的差不超過t，下標距離不超過k。

// Description: Contains Duplicate III | LeetCode OJ

解法1：一樣的把戲。

// Solution 1: Same trick.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/contains-duplicate-iii_1_AC.cpp

#221 Maximal Square

// #221 最大方形

描述：和之前一樣，不過這題要求的方形，不是矩形。

// Description: Maximal Square | LeetCode OJ

解法1：和Maximal Rectangle一樣。

// Solution 1: Same as Maximal Rectangle.

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

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

#222 Count Complete Tree Nodes

// #222 統計完全二叉樹節點個數

描述：如題。

// Description: Count Complete Tree Nodes | LeetCode OJ

解法1：可以二分。

// Solution 1: Binary search.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/count-complete-tree-nodes_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/count-complete-tree-nodes_1_AC.cpp

#223 Rectangle Area

// #223 矩形面積

描述：給定兩個橫平豎直的矩形，求總覆蓋面積。

// Description: Rectangle Area | LeetCode OJ

解法1：求交。

// Solution 1: Find the intersection.

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

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

#224 Basic Calculator

// #224 簡易計算器

描述：實現支持加減括弧的計算器。

// Description: Basic Calculator | LeetCode OJ

解法1：這題是個考驗可擴展性的好例子。怎麼處理加減乘除括弧其實並不重要，規則說出來人人都懂。但要你額外支持%^&|等等運算，你的代碼能用幾行修改搞定嗎？這才是關鍵。

// Solution 1: This problem is a good test for code scalability. How we deal with arithmetics and parentheses is not the real challenge, its the ability to make your code adaptive to new operators like %^&| etc. at the cost of only a few lines of new code that really matters.

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

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

#225 Implement Stack using Queues

// #225 用棧實現隊列

描述：如題。

// Description: Implement Stack using Queues | LeetCode OJ

解法1：負負得正，很好。正正得負？很清真。這題就是吃飽了撐的。

// Solution 1: -1 x -1 = 1, correct. 1 x 1 = -1? Talos guide you. I dont see no reason to see such nonsense here no more.

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

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

#226 Invert Binary Tree

// #226 反轉二叉樹

描述：如題。

// Description: Invert Binary Tree | LeetCode OJ

解法1：不會這題，好像確實很難。

// Solution 1:

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

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

#227 Basic Calculator II

// #227 簡易計算器2

描述：和之前差不多，這次支持加減乘除，不用支持括弧。

// Description: Basic Calculator II | LeetCode OJ

解法1：之前已經全部實現了，所以不用修改代碼。

// Solution 1: Already taken care of.

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

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

#228 Summary Ranges

// #228 區間統計

描述：給定一個數組，統計其中元素的區間分布。

// Description: Summary Ranges | LeetCode OJ

解法1：哈希表。

// Solution 1: Hash table.

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

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

#229 Majority Element II

// #229 眾數2

描述：和之前一樣，不過這次是超過1/3的元素。

// Description: Majority Element II | LeetCode OJ

解法1：超過1/k的元素，至多有k - 1個，至少有0個。其實還是Boyer-Moore投票演算法，只不過是推廣後的。

// Solution 1: There can be at most k - 1 k-majority elements, at least 0. Its still a Boyer-Moore Voting Problem, just in a more generalized sense.

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

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

#230 Kth Smallest Element in a BST

// #230 二叉搜索樹第k小節點

描述：如題。

// Description: Kth Smallest Element in a BST | LeetCode OJ

解法1：統計以每個節點為根的子樹有多少節點，這樣就能清楚每走一步跳過了多少節點。對於數據結構經常更新，這種問題。不要老想著如何把數據結構和一堆計數器綁在一起，而要想著用時間戳等工具來判斷是否有必要重新計算結果。緩存緩存，目的是用來緩一緩，而不是一勞永逸。

// Solution 1: Keep the statistics of number of nodes for every node in the tree. If you need statistics of a data structure which changes quite often, dont try to bind them together too tight. Use things like timestamps to check if the results in cache needs updating. Its a cache, not history book or tombstone.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/kth-smallest-element-in-a-bst_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/kth-smallest-element-in-a-bst_1_AC.cpp

#231 Power of Two

// #231 2的冪

描述：給定一個整數，判斷是不是2的整次冪。

// Description: Power of Two | LeetCode OJ

解法1：注意邊界條件。

// Solution 1: Edge cases.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/power-of-two_1_AC.cpp

#232 Implement Queue using Stacks

// #232 用棧實現隊列

描述：如題。

// Description: Implement Queue using Stacks | LeetCode OJ

解法1：負負得正。

// Solution 1: -1 x -1 = 1

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

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

#233 Number of Digit One

// #233 1的個數

描述：統計1~n中數字1出現次數。

// Description: Number of Digit One | LeetCode OJ

解法1：我討厭數數。

// Solution 1: I hate counting.

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

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

#234 Palindrome Linked List

// #234 迴文鏈表

描述：給定鏈表，判斷是否對稱。

// Description: Palindrome Linked List | LeetCode OJ

解法1：對半分，反轉一個，判斷是否相同。

// Solution 1: Split in half, reverse one, check for a match.

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

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

#235 Lowest Common Ancestor of a Binary Search Tree

// #235 二叉搜索樹最近公共祖先

描述：如題。

// Description: Lowest Common Ancestor of a Binary Search Tree | LeetCode OJ

解法1：二分。

// Solution 1: Binary search.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/lowest-common-ancestor-of-a-binary-search-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/lowest-common-ancestor-of-a-binary-search-tree_1_AC.cpp

#236 Lowest Common Ancestor of a Binary Tree

// #236 二叉樹最近公共祖先

描述：如題。

// Description: Lowest Common Ancestor of a Binary Tree | LeetCode OJ

解法1：Naive。

// Solution 1: Naive.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/lowest-common-ancestor-of-a-binary-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/lowest-common-ancestor-of-a-binary-tree_1_AC.cpp

#237 Delete Node in a Linked List

// #237 刪除鏈表節點

描述：給定一個鏈表節點，把這節點刪掉。

// Description: Delete Node in a Linked List | LeetCode OJ

解法1：老題。

// Solution 1: Old.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/delete-node-in-a-linked-list_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/delete-node-in-a-linked-list_1_AC.cpp

#238 Product of Array Except Self

// #238 除了自身以外的數組元素乘積

描述：給定一個數組，計算出每個元素對應的除自己以外其他元素的乘積。

// Description: Product of Array Except Self | LeetCode OJ

解法1：從左往右，從右往左。

// Solution 1: Left to right, right to left.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/product-of-array-except-self_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/product-of-array-except-self_1_AC.cpp

#239 Sliding Window Maximum

// #239 滑動窗口最大值

描述：給定一個長度為k的滑動窗口不斷從左往右滑動，給出過程中的各個最大值。

// Description: Sliding Window Maximum | LeetCode OJ

解法1：滑動窗口嘛，哈希搞一個。

// Solution 1: Sliding window again, lets hash.

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

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

#240 Search a 2D Matrix II

// #240 二維數組查找

描述：給定一個楊氏矩陣，查找一個值。

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

解法1：倆指針，但這次在兩條坐標軸上。

// Solution 1: Two pointers as well but on different axes this time.

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

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

#241 Different Ways to Add Parentheses

// #241 添加括弧的不同方法

描述：給定一個包含加減乘的算數表達式，允許你任意加括弧，求可能有多少種不同結果。

// Description: Different Ways to Add Parentheses | LeetCode OJ

解法1：可以DFS，也可以DP。

// Solution 1: DFS or DP, either way you gotta work it out.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/different-ways-to-add-parentheses_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/different-ways-to-add-parentheses_1_AC.cpp

#242 Valid Anagram

// #242 合法的變位詞

描述：檢查兩詞是否字母構成相同。

// Description: Valid Anagram | LeetCode OJ

解法1：數數。

// Solution 1: Count it.

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

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

解法2：排序。

// Solution 2: Sort it.

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

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

解法3：哈希。

// Solution 3: Hash it.

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

// Code 3: https://github.com/zhuli19901106/leetcode-2/blob/master/valid-anagram_3_AC.cpp

#243 Shortest Word Distance

// #243 最短單詞距離

描述：給定一列單詞和倆單詞，求這倆單詞在一列中的最近距離。

// Description: Shortest Word Distance | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#244 Shortest Word Distance II

// #244 最短單詞距離2

描述：和之前一樣，不過這次對於同一單詞表，可能查詢多次最短距離。

// Description: Shortest Word Distance II | LeetCode OJ

解法1：基本思路和之前一樣，不過這次用哈希表統計下各個單詞出現的所有下標，方便後面查找。同時把查詢結果緩存下來，避免重複計算。

// Solution 1: The basic idea is the same, but this time we use a hash table to record all the indices of all distinct words, thus accelerating the search. The search results are cached to avoid redundant computation.

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

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

#245 Shortest Word Distance III

// #245 單詞最短距離3

描述：和之前一樣，不過這次倆單詞可以相同。

// Description: Shortest Word Distance III | LeetCode OJ

解法1：一樣。

// Solution 1: The same.

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

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

#246 Strobogrammatic Number

// #246 翻轉數

描述：一個數如果翻轉180度後還是不變，稱為「翻轉數」。判斷給定數是否為翻轉數。

// Description: Strobogrammatic Number | LeetCode OJ

解法1：無聊。

// Solution 1: Boring.

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

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

#247 Strobogrammatic Number II

// #247 翻轉數2

描述：給定一個長度n，找出所有長度為n的翻轉數。

// Description: Strobogrammatic Number II | LeetCode OJ

解法1：考慮每一位數字可以填哪些數就行了，這是個乘法問題。

// Solution 1: Think about the digits you can fill on each position. Its a matter of multiplication.

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

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

#248 Strobogrammatic Number III

// #248 翻轉數3

描述：給定一個區間，求此區間內所有翻轉數的個數。

// Description: Strobogrammatic Number III | LeetCode OJ

解法1：這題非常有挑戰性，也可能是因為看起來就比較難吧。我確實想了很久，而且寫樂好久才寫出能AC的代碼。大體的思路當然是從1~n數數著手，不過處理邊界情況倒是比想像中更棘手。還是看代碼吧，我都很難講清楚自己當時的思路。

// Solution 1: This is a very challenging problem, maybe because it looked like one and proved exactly to be one. Its among the last few problem I solved on LeetCode. It took me hours to think it through and another 1 or 2 to write an acceptable version of code. A rough idea would be a 1~n counting. This counting is no easier than I thought. Better read the code, because I cant even explain my solution clearly.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/strobogrammatic-number-iii_1_AC.cpp

#249 Group Shifted Strings

// #249 歸類移位字元串

描述：給定一堆字元串，將移位字元串歸類到一起。此處「移位字元串」的定義是將串中所有字元按照a~z的範圍循環移位某個固定值，如果兩個字元串可以通過移位變成同一串，則互為「移位字元串」。

// Description: Group Shifted Strings | LeetCode OJ

解法1：既然可以任意移位，我們就通過移位把首字元都變成某個固定字母比如a或z，這樣就可以將移位字元串聚類了。

// Solution 1: Since were free to make the shift by any offset, its OK to shift th string so that all the initials of the strings are shifted to a certain character like a or z. In this way, all shifted strings become one. Group them in this way.

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

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

#250 Count Univalue Subtrees

// #250 統計單值子樹

描述：給定一棵二叉樹，統計單值二叉樹的個數。單值二叉樹的定義是一棵非空，並且所有節點都同值的二叉樹。

// Description: Count Univalue Subtrees | LeetCode OJ

解法1：遍歷。

// Solution 1: Traverse it.

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

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

#251 Flatten 2D Vector

// #251 展開二維數組

描述：為一個長度可能不一的二維數組寫一個迭代器，以便像一維數組一樣是逐個訪問其中元素。

// Description: Flatten 2D Vector | LeetCode OJ

解法1：和演算法無關，注意細節就好。

// Solution 1: If its not about algorithms, its about discreetness.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/flatten-2d-vector_1_AC.cpp

#252 Meeting Rooms

// #252 會議室

描述：給定一些區間，判斷是否有重合。

// Description: Meeting Rooms | LeetCode OJ

解法1：排個序，掃一遍。

// Solution 1: Sort and scan.

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

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

#253 Meeting Rooms II

// #253 會議室2

描述：給定一系列會議起始時間，判斷需要多少個會議室才夠用。

// Description: Meeting Rooms II | LeetCode OJ

解法1：看代碼，不解釋。

// Solution 1: Let the code explain itself.

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

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

#254 Factor Combinations

// #254 因式組合

描述：給定正整數n，返回所有乘積等於n的不同組合，除了n = n。為避免重複，所有乘數單調遞增。

// Description: Factor Combinations | LeetCode OJ

解法1：DFS。

// Solution 1: DFS.

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

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

#255 Verify Preorder Sequence in Binary Search Tree

// #255 驗證二叉搜索樹前序遍歷

描述：給定一個數組，判斷其是否可能是有效地二叉搜索樹前序遍歷。

// Description: Verify Preorder Sequence in Binary Search Tree | LeetCode OJ

解法1：我們遍歷樹時要用棧，驗證的時候也可以這麼做。為什麼？因為你要檢驗正確性，一種可行的方法就是照做一遍。

// Solution 1: We use a stack when traversing a tree, we do the same when checking it. Why this? You wanna verify something, you gotta repeat the process yourself and see if it works.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/verify-preorder-sequence-in-binary-search-tree_1_AC.cpp

#256 Paint House

// #256 刷房子

描述：有一排房子共n間，現在允許用紅綠藍三色刷房子，要求相鄰房子不能同色。房子和顏色有一個對應的代價矩陣，求最小代價。

// Description: Paint House | LeetCode OJ

解法1：DP。

// Solution 1: DP.

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

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

#257 Binary Tree Paths

// #257 二叉樹路徑

描述：給定一棵二叉樹，求出所有根到葉的路徑。

// Description: Binary Tree Paths | LeetCode OJ

解法1：遍歷。

// Solution 1: Traverse it.

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

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

#258 Add Digits

// #258 數位相機

描述：Digital root聽過嗎？

// Description: Add Digits | LeetCode OJ

解法1：膜9同餘。

// Solution 1: The digital root is congruent with the original number modulo 9.

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

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

#259 3Sum Smaller

// #259 較小的三數之和

描述：給定一個數組和一個值target，求出三數之和小於target的所有組合個數。

// Description: https://leetcode.com/problems/3sum-smaller/#/description

解法1：排個序，三指針。

// Solution 1: Sort the array and run three pointers on it.

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

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

#260 Single Number III

// #260 孤獨數2

描述：給定一個數組，除了倆數出現一次以外，其他數都出現了兩次。求這倆數。

// Description: Single Number III | LeetCode OJ

解法1：所有元素異或，可以得到一個非0的值。從此值中隨便取一個1位，即可作為篩選的依據。所有元素會被分為兩部分。兩部分各自做異或操作，最後得到的就是結果。

// Solution 1: XOR every element to get a result S. Extract a 1 bit from S and use this bit as a filter to split the array into two parts. The XOR results of both parts are what we are looking for.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/single-number-iii_1_AC.cpp

#261 Graph Valid Tree

// #261 有效樹形圖

描述：給定一個無向圖，判斷其是否是一個有效地樹形結構。

// Description: Graph Valid Tree | LeetCode OJ

解法1：N節點的樹，必有N - 1條邊，而且無環。那麼，N = 0呢？

// Solution 1: What makes an undirected graph a tree? What about an empty graph?

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

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

#263 Ugly Number

// #263 丑數

描述：給定一個整數，判斷其是否為丑數。丑數的定義為1或者大於1且質因數只包含2、3、5的數。

// Description: Ugly Number | LeetCode OJ

解法1：用2、3、5去除就行了。

// Solution 1: Just divide it by 2, 3 and 5.

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

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

#264 Ugly Number II

// #264 丑數2

描述：根據丑數的定義，求第n個丑數。

// Description: Ugly Number II | LeetCode OJ

解法1：為每個質因數維護一個指針，每次比較三個乘積，取最小值。如此三個指針各自不斷前進，可以遞推下去。

// Solution 1: Maintain a pointer for every prime factor. Pick the smallest product each time and update the corresponding pointers, thus theyll keep pushing forward.

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

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

#265 Paint House II

// #265 刷房子2

描述：和之前一樣，不過這次有k種顏色，而不是3種，求最小代價。

// Description: Paint House II | LeetCode OJ

解法1：顯然還是DP，不過這次我們可以想想如何圍繞k進行優化。想想Product of Array Except Self吧。

// Solution 1: Apparently its still about DP, but this time we gotta focus on the optimization around k. Think about Product of Array Except Self.

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

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

#266 Palindrome Permutation

// #266 迴文排列

描述：給定一個字元串，判斷是否能通過適當排序將其變為迴文串。

// Description: Palindrome Permutation | LeetCode OJ

解法1：數數。

// Solution 1: Count it.

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

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

#267 Palindrome Permutation II

// #267 迴文排列2

描述：給定一個字元串，返回其能重排成的所有迴文串。

// Description: Palindrome Permutation II | LeetCode OJ

解法1：跟全排列是一個道理，你說對嗎？

// Solution 1: Its actually the same as covering different permuations of a string, right?

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

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

#268 Missing Number

// #268 缺少的數

描述：給定n個從0~n選出的不重複的數，找出缺的那個數。

// Description: Missing Number | LeetCode OJ

解法1：因為數據範圍的限制，原數組就可以作為一個標記數組來使用。

// Solution 1: Due to the limit of data range, the input array can serve as a marker array.

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

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

#269 Alien Dictionary

// #269 外星字典

描述：給定一組單詞，已知這些單詞的排列順序是符合某種奇怪的字典序的。請求出這種字典序下各個字母的排列順序，對於存在多種答案者，給出任一即可。

// Description: Alien Dictionary | LeetCode OJ

解法1：拓撲排序。

// Solution 1: Topological sort.

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

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

#270 Closest Binary Search Tree Value

// #270 二叉搜索樹中最近的值

描述：給定一棵二叉搜索樹和一個值，求出其節點中最接近的值。

// Description: Closest Binary Search Tree Value | LeetCode OJ

解法1：中序遍歷。其實這題是可以二分搜索。

// Solution 1: Inorder traversal. This problem can actually be solved by binary search.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/closest-binary-search-tree-value_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/closest-binary-search-tree-value_1_AC.cpp

#271 Encode and Decode Strings

// #271 編碼解碼字元串

描述：給定一個字元串，編寫編碼解碼演算法。字典包括所有256個ASCII字元。

// Description: Encode and Decode Strings | LeetCode OJ

解法1：方法隨便你怎麼寫，要考慮到網路傳輸中實際能接受的字典集合，考慮編解碼的壓縮比率等等。我就寫個Base64好了。

// Solution 1: Whatever scheme you choose for the encoding and decoding, take the dict set, ratio of compression etc. into account. Here I take Base64 for an instance.

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

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

#272 Closest Binary Search Tree Value II

// #272 二叉搜索樹中最近的值2

描述：和之前一樣，不過這次要找的是最接近的k個值。

// Description: Closest Binary Search Tree Value II | LeetCode OJ

解法1：最接近的k個值，一定分布在target的左和右。於是我們用二分搜索找到分界線，然後往兩邊遍歷即可。說到遍歷你想到什麼了？沒錯，迭代器。所以我手寫了兩個迭代器，一個正向，一個反向。你看，這不就是OOP么？這題很有挑戰性。

// Solution 1: Since we need the k closest values, a feasible way is to find the closet value to target by binary search and start traversing from this point in both directions. Thus well need a forward iterator and a reverse iterator. Here is an OOP solution. Try writing your own iterators, its basic training. A challenging problem.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/closest-binary-search-tree-value-ii_1_AC.cpp

#273 Integer to English Words

// #273 整數轉英文單詞

描述：給定一個整數，用英文讀出來。

// Description: Integer to English Words | LeetCode OJ

解法1：不難，但是很麻煩。

// Solution 1: Aint no big problem, but some hard labor indeed.

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

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

#274 H-Index

// #274 H指數

描述：給定一個學者的論著列表，我們定義H指數：該學者的N篇論著里有H篇引用數不小於H，並且剩餘的N - H篇引用數不大於H。滿足此條件的最大H稱為其H指數。求此人的H指數。

// Description: H-Index | LeetCode OJ

解法1：排序，二分。

// Solution 1: Sort and binary search.

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

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

#275 H-Index II

// #275 H指數2

描述：如果數組有序，又當如何？

// Description: H-Index II | LeetCode OJ

解法1：如出一轍。

// Solution 1: What a coincidence.

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

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

#276 Paint Fence

// #276 刷籬笆

描述：有n個籬笆栓子，每個刷一種顏色。你有k種顏色可選，要求至多相鄰倆栓子同色。問共有多少種不同刷法？

// Description: Paint Fence | LeetCode OJ

解法1：釐清遞推關係。

// Solution 1: Understand the recurrence relation.

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

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

#277 Find the Celebrity

// #277 找大腕兒

描述：有這麼一幫子人，只允許你問「誰認識誰」，想個法兒把腕兒給找出來。什麼叫腕兒？誰都認識TA老人家，TA老人家誰也不認。

// Description: Find the Celebrity | LeetCode OJ

解法1：按定義判斷，使用排除法。最壞時間複雜度O(N ^ 2)。

// Solution 1: Follow the process of elimination by the given definition of celebrities. Worst time can reach O(N ^ 2).

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-the-celebrity_1_AC.cpp

#278 First Bad Version

// #278 第一個壞版本

描述：某版本出了問題，後面跟著都壞了。找找。

// Description: First Bad Version | LeetCode OJ

解法1：二分。

// Solution 1: Binary search.

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

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

#279 Perfect Squares

// #279 完全平方數

描述：給定一個整數，求至少幾個完全平方數可以加成該數。

// Description: Perfect Squares | LeetCode OJ

解法1：此題的通解明顯要用DP，不過對於N很小的時候，貌似有數學解，需要組合數學知識。

// Solution 1: The general solution of this problem requires DP, but for small N there seems to be some mathematical solutions available, if you know combinatorial maths.

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

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

#280 Wiggle Sort

// #280 擺動排序

描述：給定一個無序數組，用O(1)的空間代價將數組排成「小大小大小...」的形式。

// Description: Wiggle Sort | LeetCode OJ

解法1：中位數是關鍵。這題代碼真心不好寫。

// Solution 1: Median is the key. Its not easy, I mean it.

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

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

#281 Zigzag Iterator

// #281 Z形迭代器

描述：給定兩個數組，按照「上下上下...」的方式逐個遍歷，要求寫成迭代器的形式。

// Description: Zigzag Iterator | LeetCode OJ

解法1：沒什麼意思，寫唄。

// Solution 1: Boring.

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

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

#282 Expression Add Operators

// #282 表達式添加運算符

描述：給定一個數字串S和一個值target，允許你在S中間添加加減乘符號，使得表達式結果為target，求所有添法。

// Description: Expression Add Operators | LeetCode OJ

解法1：暴力DFS，適當剪枝。

// Solution 1: Brute-force DFS with a little pruning.

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

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

#283 Move Zeroes

// #283 移0

描述：把數組中的0移到末尾去。

// Description: Move Zeroes | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#284 Peeking Iterator

// #284 預讀迭代器

描述：在已給定的迭代器基礎上，實現預讀功能。

// Description: Peeking Iterator | LeetCode OJ

解法1：好像沒什麼值得說的。

// Solution 1: Nothing worth mentioning.

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

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

#285 Inorder Successor in BST

// #285 二叉搜索樹的中序後繼節點

描述：如題。

// Description: Inorder Successor in BST | LeetCode OJ

解法1：右轉左下，左上右轉。

// Solution 1: Turn right and go down left, or go up left and turn right.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/inorder-successor-in-bst_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/inorder-successor-in-bst_1_AC.cpp

#286 Walls and Gates

// #286 牆和門

描述：給定一個矩陣，有門，有空房，有障礙物。求出每個空房到離它最近的門的距離。如果到不了，就用INF表示。

// Description: Walls and Gates | LeetCode OJ

解法1：思路當然是BFS，不過你不妨想像，從空房到門，和從門到空房，兩種搜索有什麼區別？區別就在於誰多誰少。以少搜多，效率更高。

// Solution 1: Its obviously a searching problem. You might as well think about the difference between searching from empty cells to gates, and the ways backwards. The key lies in whether therere more empty cells or more gates.

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

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

#287 Find the Duplicate Number

// #287 數組查重

描述：給定長度為n + 1的數組，其中元素都是1~n。求出重複元素。

// Description: Find the Duplicate Number | LeetCode OJ

解法1：這數組可以看成一個單鏈表，這鏈表肯定有環。

// Solution 1: This array is equivalent to a linked list, which is bound to have at least one loop.

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

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

解法2：思路類似，但這次連數組都不用修改。

// Solution 2: Similar thoughts, this time we dont even modify the array.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/find-the-duplicate-number_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/find-the-duplicate-number_2_AC.cpp

#288 Unique Word Abbreviation

// #288 不同單詞縮寫

描述：可以把一個單詞保留首尾字母，中間用長度代替，比如apple變成a3e。現在給定一個詞典，對於一個詞，判斷詞典里是否有和它縮寫一樣的。

// Description: Unique Word Abbreviation | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#289 Game of Life

// #289 生命遊戲

描述：康威生命遊戲 - 維基百科，自由的百科全書

// Description: Game of Life | LeetCode OJ

解法1：既然規則這麼複雜，咱們就照規矩辦。對於既然是01矩陣，數據類型又是int型，完全裝得下，就不必額外開矩陣了。

// Solution 1: The rule is well defined, so lets do things as told. Its a 01 matrix, with every element of int type, its more than enough to hold an extra bit, saving the trouble of allocating another matrix.

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

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

#290 Word Pattern

// #290 單詞模式

描述：給定一個字元串，和一句話。判斷字元串的每個字母和這句話中的單詞能否構成一一對應。

// Description: Word Pattern | LeetCode OJ

解法1：雙射嘛，倆哈希表搞定。

// Solution 1: Two hash tables for one bijection.

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

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

#291 Word Pattern II

// #291 單詞模式2

描述：和之前一樣，不過這次這句話的單詞之間沒有空格了。傻了吧？

// Description: https://leetcode.com/problems/word-pattern-ii/#/description

解法1：有空格分割，就是一道水題。這冷不丁兒沒了空格，本來一目了然的東西，咱就得摸著黑找嘍。當然，一一對應還得靠哈希表。

// Solution 1: With the spaces， its piece of cake. Without it, we gotta make a search for what we want. Still, verifying the bijection requires hash tables.

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

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

#292 Nim Game

// #292 拿石頭遊戲

描述：共N個石頭，倆人輪流，每次只能拿走1~3個。誰恰好拿光了，誰就贏。問先手贏還是後手贏。

// Description: Nim Game | LeetCode OJ

解法1：謎之博弈論，從這題開始。

// Solution 1: Youll never understand Game Theory.

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

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

#293 Flip Game

// #293 翻轉遊戲

描述：有一個由+-組成的字元串，每次允許把++變成--。現在給定一個串，請返回一次操作以後的結果。

// Description: Flip Game | LeetCode OJ

解法1：翻唄。

// Solution 1: Do it.

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

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

#294 Flip Game II

// #294 翻轉遊戲2

描述：按照上一題中給定的規則，倆人輪流進行翻轉。現在給定一個初始字元串，問先手是不是穩贏？

// Description: Flip Game II | LeetCode OJ

解法1：首先可以暴力搜，但這麼干不優雅。如果稍微考慮一下，就能看到子問題在哪兒。每一個連續的+串就是子問題。所以呢？所以肯定有動態規劃的解法。然而到這兒，我的思路就卡住了。一個聲音告訴我：SG定理。夫天將降大任於碼農，必先惡補數學。

// Solution 1: The first thought was to do a brute-force DFS. Itll do, but not very graceful. Later I found that every consecutive string of + can be considered a subproblem. Yes, thats the door to DP, but I couldnt find the key. As the prophecy comnends upon us: SG Theorem. You wanna be more than just a mere coding monkey? Learn some maths.

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

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

#295 Find Median from Data Stream

// #295 數據流的中位數

描述：設計一個數據結構，能向其中添加元素，並能隨時查詢中位數。

// Description: Find Median from Data Stream | LeetCode OJ

解法1：既然是中位數，就是放在中間的數。所以，我們每次添加數的時候，都要保證數按照大小分成兩堆，兩堆要盡量一樣多。不得不說，平衡樹是個好東西。

// Solution 1: Its the median we want, it must lie in the middle. So every time we add something, make sure we put things in two half, one pile large, one pile small. Both sizes be as close as possible. Gotta admit, balanced BST comes in really handy.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/find-median-from-data-stream_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-median-from-data-stream_1_AC.cpp

#296 Best Meeting Point

// #296 最佳見面地點

描述：給定一個01矩陣，1表示建築，0表示空地。現在要求選擇一處空地作為集合地點，要求離所有建築之和最小。求最小距離之和。距離計算以曼哈頓距離為準。

// Description: Best Meeting Point | LeetCode OJ

解法1：既然用的是曼哈頓距離，橫向和縱向的距離就完全獨立了。於是我們分別計算橫向和縱向各個點的距離之和。這倆距離都是可以O(N)時間求出的，注意不要重複計算。接下來就不用說了吧？

// Solution 1: Since its Manhattan Distance we use, the calculation of x- and y-axis are completely independent. Thus we compute the sum of distances for every x- and y- coordinates. The computation can be done in O(N) time, if you know how to avoid redundancy. Need I say more?

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/best-meeting-point_1_AC.cpp

#297 Serialize and Deserialize Binary Tree

// #297 二叉樹序列化

描述：設計一種序列化和反序列化二叉樹的演算法。

// Description: Serialize and Deserialize Binary Tree | LeetCode OJ

解法1：其實只要對空指針做適當的標記，任何一種遍歷都可以唯一地序列化一棵二叉樹。所以，更值得關心的，是如何使序列化後的字元串更短。

// Solution 1: As long as NULL pointer is marked with some special characters, any kind of traversal can unambiguously serialize a binary tree. The length of the serialization output is worth more attention.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/serialize-and-deserialize-binary-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/serialize-and-deserialize-binary-tree_1_AC.cpp

#298 Binary Tree Longest Consecutive Sequence

// #298 最長二叉樹連續序列

描述：給定一棵二叉樹，求從上到下最長連續序列的長度。「連續」指公差為1的等差數列。

// Description: Binary Tree Longest Consecutive Sequence | LeetCode OJ

解法1：遍歷唄。

// Solution 1: Traverse it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/binary-tree-longest-consecutive-sequence_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/binary-tree-longest-consecutive-sequence_1_AC.cpp

#299 Bulls and Cows

// #299 水牛和奶牛

描述：猜數字玩過吧？你猜，我告訴你有幾個完全猜對，有幾個數字對位置不對。現在，我猜你說。

// Description: Bulls and Cows | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#300 Longest Increasing Subsequence

// #300 最長遞增子序列

描述：如題。

// Description: Longest Increasing Subsequence | LeetCode OJ

解法1：DP。

// Solution 1: DP.

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

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