LeetCode 簡略題解 - 301~400

#301 Remove Invalid Parentheses

// #301 去除無效括弧

描述：給定一個可能包含其他字元的括弧序列，通過刪除最少的字元，使括弧成功匹配。要求返回所有可行的解法。

// Description: Remove Invalid Parentheses | LeetCode OJ

解法1：難題。試想，如果多出了)，我們如何處理？沒錯，刪掉。那麼多出了(，怎麼辦呢？能刪嗎？不能，因為後面可能用得著。這就是一大難點。要求返回所有結果，這是另一大難點。為了處理這兩點，我的代碼寫得非常繁瑣，而且始終沒通過。最終找了網上的解法，發現其中有一個絕妙的解法：對於多餘的(，我們把問題反過來看。看看代碼，你就知道怎麼「反」了。

// Solution 1: A hard problem indeed. If therere redundant (s, what you gonna do? Remove it. If its )s, what then? We cant remove them, because they might be needed later. This is the first challenge. The problem requests we find all possible solutions, thats the second challenge. It took me lots of time and efforts to put up a long and sloppy solution, which never got accepted. Here the solution is from the Internet. A major difference from mine is the way it deals with redundant (s: switch the role of () to )(. Read the code and youll see how and why.

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

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

#302 Smallest Rectangle Enclosing Black Pixels

// #302 包圍黑點的最小矩形

描述：給定一個01矩陣，1表示黑點。求能蓋住所有黑點的最小矩形面積。

// Description: Smallest Rectangle Enclosing Black Pixels | LeetCode OJ

解法1：無聊。

// Solution 1: Boring.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/smallest-rectangle-enclosing-black-pixels_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/smallest-rectangle-enclosing-black-pixels_1_AC.cpp

解法2：真無聊。

// Solution 2: Really boring.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/smallest-rectangle-enclosing-black-pixels_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/smallest-rectangle-enclosing-black-pixels_2_AC.cpp

#303 Range Sum Query - Immutable

// #303 區間求和 - 不變

描述：給定一個元素不變的數組，處理多次區間求和。

// Description: Range Sum Query - Immutable | LeetCode OJ

解法1：前綴和。

// Solution 1: Prefix sum.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-immutable_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-immutable_1_AC.cpp

#304 Range Sum Query 2D - Immutable

// #304 二維區間求和 - 不變

描述：給定元素不變的矩陣，求各種子矩陣和。

// Description: Range Sum Query 2D - Immutable | LeetCode OJ

解法1：還是前綴和。

// Solution 1: Still prefix sum.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-2d-immutable_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-2d-immutable_1_AC.cpp

#305 Number of Islands II

// #305 島嶼個數2

描述：給定一個01矩陣，開始全都是0。允許兩種操作：1. 查詢「1」連通分量的個數，2. 把某位置變成1。

// Description: Number of Islands II | LeetCode OJ

解法1：並查集。

// Solution 1: Union-find set.

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

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

#306 Additive Number

// #306 加性數

描述：斐波那契數列知道吧？現在給定這麼一個數列，開頭倆數可以不是1，把這個數列連成一個數，我們稱其為「加性數」。現在給定一個數，判斷是不是加性數。

// Description: Additive Number | LeetCode OJ

解法1：一看就得搜，不過要注意剪枝，否則妥妥的藥丸。

// Solution 1: It looks like DFS, but make sure you got some pruning in stock. Otherwise, youre going down.

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

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

#307 Range Sum Query - Mutable

// #307 區間求和 - 可變

描述：給定允許改變元素的數組，處理各種區間求和。

// Description: Range Sum Query - Mutable | LeetCode OJ

解法1：樹狀數組。

// Solution 1: BIT.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-mutable_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-mutable_1_AC.cpp

#308 Range Sum Query 2D - Mutable

// #308 二維區間求和 - 可變

描述：給定元素可變的矩陣，處理子矩陣求和。

// Description: Range Sum Query 2D - Mutable | LeetCode OJ

解法1：二維樹狀數組。

// Solution 1: 2D BIT.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-2d-mutable_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/range-sum-query-2d-mutable_1_AC.cpp

#309 Best Time to Buy and Sell Stock with Cooldown

// #309 最佳炒股時機帶CD

描述：給定股價，每次買賣股票有1天的冷卻期，求最大收益。

// Description: Best Time to Buy and Sell Stock with Cooldown | LeetCode OJ

解法1：用一個有限狀態機來考慮，昨天今天、有股沒股。這兩者的組合和狀態轉換搞清楚了，題目就做出來了。

// Solution 1: Use a finite state machine to deal with the problem. Today or yesterday, got stocks in hand or not, the state transitions among these are the key to the solution.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/best-time-to-buy-and-sell-stock-with-cooldown_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/best-time-to-buy-and-sell-stock-with-cooldown_1_AC.cpp

#310 Minimum Height Trees

// #310 最小高度樹

描述：給定一個樹形的無向圖，允許你選一個節點作為根。請找出使得樹最矮的根節點。

// Description: Minimum Height Trees | LeetCode OJ

解法1：關鍵在於找出圖中最長的一條路徑。做法就是兩次遍歷。這條最長的路徑也叫作圖的直徑。

// Solution 1: The key is to find the longest path in the graph. Two traversals will suffice. This path is called the diameter of the graph.

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

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

#311 Sparse Matrix Multiplication

// #311 稀疏矩陣相乘

描述：給定兩個很稀疏的矩陣，做乘法。

// Description: https://leetcode.com/problems/sparse-matrix-multiplication/#/description

解法1：很稀疏，有多稀疏？你輸入是完整矩陣，輸出也是，有謀搞錯？

// Solution 1: Sparse matrix? I dont see no sparse matrix.

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

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

#312 Burst Balloons

// #312 爆氣球

描述：給定n個氣球排成一排，每個上面標了個數a[i]。如果爆掉某個氣球，就獲得左右倆球和該球的乘積作為獎分，之後左右倆球就相鄰了。求爆掉所有氣球獲得的最高得分。

// Description: Burst Balloons | LeetCode OJ

解法1：記憶化搜索，動態規劃的常見玩法。

// Solution 1: DFS with memorization, a common feat in DP.

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

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

#313 Super Ugly Number

// #313 超級丑數

描述：和之前一樣，不過這次的質數是由輸入欽點，不一定是2、3、5。求第n個。

// Description: Super Ugly Number | LeetCode OJ

解法1：看代碼。

// Solution 1: Read the code.

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

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

#314 Binary Tree Vertical Order Traversal

// #314 二叉樹垂直遍歷

描述：按照從左往右，從上往下的順序，遍歷二叉樹。

// Description: Binary Tree Vertical Order Traversal | LeetCode OJ

解法1：我倒看看你還有多少種遍歷方式。

// Solution 1: Show me what you got on binary tree traversals.

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

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

#315 Count of Smaller Numbers After Self

// #315 後面小於自身的元素個數

描述：給定一個數組，對於每個元素，求在其後比其小的元素個數。

// Description: Count of Smaller Numbers After Self | LeetCode OJ

解法1：凡是這種限定數據範圍、下標範圍，統計個數的問題，都可以用樹狀數組來做。必要時可以用哈希表對離散化的數據進行連續化映射。

// Solution 1: Problems as such, that put restrictions on data range and index range and focus on counting, can be solved with BIT. Use a hash table to map a discretized sequence to a consecutive one.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/count-of-smaller-numbers-after-self_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/count-of-smaller-numbers-after-self_1_AC.cpp

#316 Remove Duplicate Letters

// #316 去除重複字母

描述：給定一個字元串，去除重複字母，使得所有字母只出現一次，並要求所得結果是字典序最小的。

// Description: Remove Duplicate Letters | LeetCode OJ

解法1：貪婪。

// Solution 1: Greed is good.

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

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

#317 Shortest Distance from All Buildings

// #317 最短距離之和

描述：和之前那一樣，不過這次建築物不能穿過了，而且還有一些障礙物也不能穿過。依然求最短距離之和。如果找不到，返回-1。

// Description: Shortest Distance from All Buildings | LeetCode OJ

解法1：因為涉及到連通性，簡單的求和就不管用了。搜吧。

// Solution 1: Since connectivity problem is involved, simple summation no longer works. Lets search.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/shortest-distance-from-all-buildings_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/shortest-distance-from-all-buildings_1_AC.cpp

#318 Maximum Product of Word Lengths

// #318 單詞長度最大乘積

描述：給定一堆單詞，要求找出倆單詞長度的最大乘積，要求倆單詞不能有相同字母。

// Description: Maximum Product of Word Lengths | LeetCode OJ

解法1：對於如何判斷倆單詞有沒有相同字母，只要用位向量表示每個字母是否出現即可，倆位向量異或即可得出是否有相同字母。

// Solution 1: Use a bit vector to mark the occurrence of each letter. The XOR of two bit vectors will reveal if two words share a same letter.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-product-of-word-lengths_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-product-of-word-lengths_1_AC.cpp

#319 Bulb Switcher

// #319 開關燈

描述：有N盞燈，開始都關著。從1到N，數到K時，就把所有K的倍數的開關都按一次。如此N輪後，問有多少盞燈亮著。

// Description: Bulb Switcher | LeetCode OJ

解法1：這是個數學題。

// Solution 1: Its about math.

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

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

#320 Generalized Abbreviation

// #320 縮寫（廣義的）

描述：定義一種廣義的縮寫：允許你把一個單詞中的一個或多個部分替換成長度，但各部分不能相鄰。給定一個單詞，給出所有可能的替換方法。

// Description: https://leetcode.com/problems/generalized-abbreviation/#/description

解法1：搜。

// Solution 1: DFS.

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

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

#321 Create Maximum Number

// #321 構成最大數

描述：給定倆長度為m和n的數組，元素全都是0~9數字。現要求從中選出k個數字，組成最大的數。要求選數的過程保持倆數組中元素的各自先後順序。

// Description: Create Maximum Number | LeetCode OJ

解法1：這很像歸併排序，對吧？不過沒那麼簡單，因為有些元素是要跳過的。仔細看dropOne()函數的作用，就會發現其作用是每次捨棄一個數字，使得結果儘可能大。我們之後的歸併則是通過comp()保證結果儘可能大。兩者配合，得到最終結果。

// Solution 1: Its like Merge Sort, right? Aint that simple, because some digits are to be discarded. Read the function dropOne() carefully and youll find it drops one digit to make the result as large as possible. The largest merge result is guaranteed by comp(). Useem both, youll get the correct result.

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

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

#322 Coin Change

// #322 找零錢

描述：給你足夠多的幾種面值的錢，問最少用幾張能湊出某個金額。

// Description: Coin Change | LeetCode OJ

解法1：背包問題。

// Solution 1: Knapsack Problem.

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

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

#323 Number of Connected Components in an Undirected Graph

// #323 無向圖連通分量個數

描述：如題。

// Description: Number of Connected Components in an Undirected Graph | LeetCode OJ

解法1：並查集。

// Solution 1: Union-find set.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/number-of-connected-components-in-an-undirected-graph_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/number-of-connected-components-in-an-undirected-graph_1_AC.cpp

#324 Wiggle Sort II

// #324 搖擺排序2

描述：和之前一樣，但這次要求相鄰元素不能相等。

// Description: Wiggle Sort II | LeetCode OJ

解法1：O(1)的空間複雜度還是算了，有功夫我還多睡會兒，操這閑心幹嘛？

// Solution 1: O(1) space? Forget about it.

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

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

#325 Maximum Size Subarray Sum Equals k

// #325 和為k的最長子數組

描述：給定數組，求和為k的最長子數組的長度。

// Description: Maximum Size Subarray Sum Equals k | LeetCode OJ

解法1：用哈希表記錄前綴和。

// Solution 1: Record prefix sums with a hash table.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-size-subarray-sum-equals-k_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-size-subarray-sum-equals-k_1_AC.cpp

#326 Power of Three

// #326 3的冪

描述：判斷一個數是否是3的冪。

// Description: Power of Three | LeetCode OJ

解法1：循環。

// Solution 1: Loop.

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

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

解法2：對數。

// Solution 2: Logarithm.

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

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

#327 Count of Range Sum

// #327 統計區間和

描述：給定一個數組，求有多少區間和在[low, high]之間。

// Description: Count of Range Sum | LeetCode OJ

解法1：參考Count of Smaller Number After Self，用樹狀數組搞定。想想1和-1是幹嘛用的。

// Solution 1: Refer to the solution of Count of Smaller Number After Self. Use a BIT and think about the meaning of 1 and -1.

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

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

#328 Odd Even Linked List

// #328 奇偶鏈表

描述：給定一個鏈表，按照單雙數位置把鏈表重排成單在前，雙在後。注意，是位置，不是值。

// Description: Odd Even Linked List | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#329 Longest Increasing Path in a Matrix

// #329 矩陣最長遞增路徑

描述：給定一個矩陣，允許從某點出發，上下左右走。請找出能走出的單調遞增序列的最大長度。

// Description: Longest Increasing Path in a Matrix | LeetCode OJ

解法1：可以搜，也可以DP，道理其實是一樣的。

// Solution 1: BFS or DP, different means, same goal.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/longest-increasing-path-in-a-matrix_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-increasing-path-in-a-matrix_1_AC.cpp

#330 Patching Array

// #330 數組補丁

描述：給定一個數組和一個值target，允許你添加一些數，使得數組中的數能加成target。問最少添加多少個數？

// Description: Patching Array | LeetCode OJ

解法1：代碼非常短，思路卻很聰明。貪婪。

// Solution 1: Very short code and bright idea. Its greedy.

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

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

#331 Verify Preorder Serialization of a Binary Tree

// #331 驗證二叉樹前序序列化

描述：給定一個前序遍歷的序列化字元串，判斷其是否能夠成一棵有效地二叉樹。

// Description: Verify Preorder Serialization of a Binary Tree | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/verify-preorder-serialization-of-a-binary-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/verify-preorder-serialization-of-a-binary-tree_1_AC.cpp

#332 Reconstruct Itinerary

// #332 重建行程

描述：給你一堆機票，請重建整個行程。如果有多種可能，選字典序最小的那個。

// Description: Reconstruct Itinerary | LeetCode OJ

解法1：拓撲排序。

// Solution 1: Topological sort.

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

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

#333 Largest BST Subtree

// #333 最大二叉搜索樹子樹

描述：給定二叉樹，找出最大的二叉搜索樹子樹。

// Description: Largest BST Subtree | LeetCode OJ

解法1：跟判斷BST一樣。

// Solution 1: Same as validating a BST.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/largest-bst-subtree_1_AC.cpp

#334 Increasing Triplet Subsequence

// #334 遞增三元組

描述：給定數組，問是否存在長度為3的遞增子序列。

// Description: Increasing Triplet Subsequence | LeetCode OJ

解法1：看代碼。

// Solution 1: Read the code.

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

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

#335 Self Crossing

// #335 自交叉

描述：給定一系列長度，從(0, 0)出發按照「上左下右...」順序依長度逐個走下去。問走過的軌跡是否存在交叉？碰上就算。

// Description: Self Crossing | LeetCode OJ

解法1：謎之解法，很聰明。

// Solution 1: A clever solution, not mine.

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

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

#336 Palindrome Pairs

// #336 迴文對

描述：給定一堆字元串，問哪兩個連起來是迴文串。求所有可能的迴文對。

// Description: Palindrome Pairs | LeetCode OJ

解法1：字元串哈希，正向反向一起用。

// Solution 1: String hashing, both forward and reverse.

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

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

#337 House Robber III

// #337 小偷3

描述：這回房子構成一棵二叉樹，依然不能偷相鄰倆房子，求怎麼偷最來錢。

// Description: House Robber III | LeetCode OJ

解法1：搜唄。

// Solution 1: Search it.

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

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

#338 Counting Bits

// #338 數位數

描述：給定一個非負整數num，求0~num每個數中二進位1的個數。

// Description: Counting Bits | LeetCode OJ

解法1：DP。

// Solution 1: DP.

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

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

#339 Nested List Weight Sum

// #339 嵌套列表加權和

描述：如題。

// Description: https://leetcode.com/problems/nested-list-weight-sum/#/description

解法1：手動遞歸。

// Solution 1: Manual recursion.

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

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

#340 Longest Substring with At Most K Distinct Characters

// #340 包含至多K個不同字母的最長子串

描述：如題。

// Description: Longest Substring with At Most K Distinct Characters | LeetCode OJ

解法1：倆指針。

// Solution 1: Two pointers.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/longest-substring-with-at-most-k-distinct-characters_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-substring-with-at-most-k-distinct-characters_1_AC.cpp

#341 Flatten Nested List Iterator

// #341 展開嵌套列表的迭代器

描述：像訪問一個一維列表一樣訪問嵌套列表。

// Description: Flatten Nested List Iterator | LeetCode OJ

解法1：手動遞歸。

// Solution 1: Manual recursion.

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

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

#342 Power of Four

// #342 4的冪

描述：判斷一個數是否為4的冪。

// Description: Power of Four | LeetCode OJ

解法1：循環。

// Solution 1: Loop.

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

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

解法2：對數。

// Solution 2: Logarithm.

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

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

#343 Integer Break

// #343 整數分解

描述：將一個正整數分解為至少兩個正整數，使其乘積最大。

// Description: Integer Break | LeetCode OJ

解法1：DP。

// Solution 1: DP.

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

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

#344 Reverse String

// #344 反轉字元串

描述：如題。

// Description: Reverse String | LeetCode OJ

解法1：轉。

// Solution 1: Do it.

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

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

解法2：轉。

// Solution 2: Do it.

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

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

#345 Reverse Vowels of a String

// #345 反轉母音

描述：給定一個串，只反轉母音。

// Description: Reverse Vowels of a String | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-vowels-of-a-string_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/reverse-vowels-of-a-string_1_AC.cpp

#346 Moving Average from Data Stream

// #346 滑動窗口平均值

描述：如題。

// Description: https://leetcode.com/problems/moving-average-from-data-stream/#/description

解法1：滑唄。

// Solution 1: Slide it.

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

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

#347 Top K Frequent Elements

// #347 K個最常見元素

描述：給定數組，求其中出現頻率最高的K個元素。

// Description: Top K Frequent Elements | LeetCode OJ

解法1：沒意思。

// Solution 1: Dull.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/top-k-frequent-elements_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/top-k-frequent-elements_1_AC.cpp

#348 Design Tic-Tac-Toe

// #348 井字棋

描述：設計井字棋遊戲。

// Description: Design Tic-Tac-Toe | LeetCode OJ

解法1：模擬題。

// Solution 1: Simulation problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/design-tic-tac-toe_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/design-tic-tac-toe_1_AC.cpp

#349 Intersection of Two Arrays

// #349 數組交集

描述：如題。

// Description: Intersection of Two Arrays | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#350 Intersection of Two Arrays II

// #350 數組交集2

描述：如題，不去重。

// Description: Intersection of Two Arrays II | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/intersection-of-two-arrays-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/intersection-of-two-arrays-ii_1_AC.cpp

#351 Android Unlock Patterns

// #351 安卓解鎖圖案

描述：手機的解鎖手勢知道吧？找出經過格點數在m~n之間的所有解鎖手勢個數。手勢中如果經過一個未訪問的點，是不允許直接跳過的。

// Description: Android Unlock Patterns | LeetCode OJ

解法1：搜。

// Solution 1: DFS.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/android-unlock-patterns_1_AC.cpp

#352 Data Stream as Disjoint Intervals

// #352 數據流表示為離散區間

描述：設計一個數據結構，允許添加數據，允許統計元素的分布區間。

// Description: Data Stream as Disjoint Intervals | LeetCode OJ

解法1：哈希。

// Solution 1: Hash.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/data-stream-as-disjoint-intervals_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/data-stream-as-disjoint-intervals_1_AC.cpp

#353 Design Snake Game

// #353 貪食蛇

描述：設計貪食蛇遊戲。

// Description: Design Snake Game | LeetCode OJ

解法1：很明顯，用鏈表表示蛇比較合適，因為移動一格只需要改變頭尾節點。

// Solution 1: Apparently, its appropriate to represent the snake with a linked list, as moving one step requires only changing the head and the tail node.

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

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

#354 Russian Doll Envelopes

// #354 俄羅斯套娃

描述：給定一堆矩形，問最多能嵌套幾層。

// Description: Russian Doll Envelopes | LeetCode OJ

解法1：O(N ^ 2) DP。

// Solution 1: O(N ^ 2) DP.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/russian-doll-envelopes_1_AC.cpp

解法2：LIS。

// Solution 2: LIS.

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

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/russian-doll-envelopes_2_AC.cpp

#355 Design Twitter

// #355 設計推特

描述：太長不寫。

// Description: Design Twitter | LeetCode OJ

解法1：麻煩的一塌糊塗，這叫演算法題？這叫系統設計題還差不多。

// Solution 1: You call this algorithmic problem? I think system design suits better.

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

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

#356 Line Reflection

// #356 對稱軸

描述：給定N個點，看是否存在一條豎直線，使得全圖關於這條線對稱。

// Description: https://leetcode.com/problems/line-reflection/#/description

解法1：挺無聊的一題。

// Solution 1: Relatively boring.

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

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

#357 Count Numbers with Unique Digits

// #357 數字不重複的數的個數

描述：給定整數N，求不超過N位的數字不重複的數的個數。

// Description: Count Numbers with Unique Digits | LeetCode OJ

解法1：這是個數學題。

// Solution 1: Math problem.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/count-numbers-with-unique-digits_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/count-numbers-with-unique-digits_1_AC.cpp

#358 Rearrange String k Distance Apart

// #358 重排字元串使相同字元至少相距k位

描述：如題。

// Description: Rearrange String k Distance Apart | LeetCode OJ

解法1：總是從剩餘最多的字母開始考慮。

// Solution 1: Always start looking from the letter with the highest remaining count.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/rearrange-string-k-distance-apart_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/rearrange-string-k-distance-apart_1_AC.cpp

#359 Logger Rate Limiter

// #359 日誌限速器

描述：設計一個數據結構，能列印日誌。但如果相同的日誌在過去10s內已經列印過了，就不打。

// Description: Logger Rate Limiter | LeetCode

解法1：模擬題。

// Solution 1: Simulation problem.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/logger-rate-limiter_1_AC.cpp

#360 Sort Transformed Array

// #360 排序變換後的數組

描述：給定一個數組，對每個元素執行f(x) = ax2 + bx + c的映射，求映射後結果，要求將結果排序，但不能使用排序演算法。

// Description: https://leetcode.com/problems/sort-transformed-array/#/description

解法1：這就叫沒事找事，吃飽了撐的。

// Solution 1: Dont you have better things to do?

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

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

#361 Bomb Enemy

// #361 轟炸敵人

描述：炸彈人玩過吧？假設炸彈只能放在空地，不能炸穿牆，可以貫穿多個敵人，求一個炸彈最多能炸死多少敵人。

// Description: https://leetcode.com/problems/bomb-enemy/#/description

解法1：也算是DP吧。

// Solution 1: I guess this is DP after all.

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

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

#362 Design Hit Counter

// #362 設計命中計數器

描述：設計一個計數器，可以在某個時間點命中，也可以統計以某個時間點截止的5分鐘內的命中總次數。

// Description: https://leetcode.com/problems/design-hit-counter/#/description

解法1：用map。

// Solution 1: Use a map.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/design-hit-counter_1_AC.cpp

#363 Max Sum of Rectangle No Larger Than K

// #363 和不超過K的最大子矩陣

描述：給定一個矩陣，求和不超過K的最大子矩陣。

// Description: Max Sum of Rectangle No Larger Than K | LeetCode OJ

解法1：首先你要知道最大子矩陣和的求法，然後你要知道不超過K的最大子數組和的求法，然後就沒有然後了。

// Solution 1: Know how to get maximal submatrix sum, know how to get maximal subarray sum no larger than K, know no more.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/max-sum-of-sub-matrix-no-larger-than-k_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/max-sum-of-sub-matrix-no-larger-than-k_1_AC.cpp

#364 Nested List Weight Sum II

// #364 嵌套列表加權和2

描述：和之前一樣，不過這次權值反著來，越深的權值越小。

// Description: https://leetcode.com/problems/nested-list-weight-sum-ii/#/description

解法1：稍微變化一下。

// Solution 1: Minor change.

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

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

#365 Water and Jug Problem

// #365 水和罐子問題

描述：給定兩個罐子和足夠多的水。每次允許你倒水，但要求要麼倒空，要麼倒滿，要麼來回倒。給定倆罐子容積v1、v2，和一個體積v3，問能夠得到v3體積的水。

// Description: Water and Jug Problem | LeetCode OJ

解法1：注意邊界情況。

// Solution 1: Edge cases.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/water-and-jug-problem_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/water-and-jug-problem_1_AC.cpp

#366 Find Leaves of Binary Tree

// #366 撿樹葉

描述：逐層移除二叉樹的葉節點。

// Description: https://leetcode.com/problems/find-leaves-of-binary-tree/#/description

解法1：注意每個節點的高度，發現規律了嗎？

// Solution 1: Note the height of each node, see?

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

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

#367 Valid Perfect Square

// #367 驗證完全平方數

描述：如題。

// Description: Valid Perfect Square | LeetCode OJ

解法1：匪開方，如之何？

// Solution 1: Any way around the square root?

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

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

#368 Largest Divisible Subset

// #368 最大整除子集

描述：給定一個集合，找出最大的子集，使得子集中任意兩數都有整除關係。

// Description: Largest Divisible Subset | LeetCode OJ

解法1：DP.

// Solution 1: DP.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/largest-divisible-subset_1_AC.cpp

#369 Plus One Linked List

// #369 鏈表加一

描述：給定一個鏈表表示高精度數，給加個1。

// Description: Plus One Linked List | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

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

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

#370 Range Addition

// #370 區間增加

描述：給定一個數組，開始全0.每次允許對一個區間統一加上某值。執行完一系列加法後，返回數組。

// Description: Range Addition | LeetCode OJ

解法1：樹狀數組的另一應用。

// Solution 1: Another application of BIT.

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

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

#371 Sum of Two Integers

// #371 整數加法

描述：不準用+-。

// Description: Sum of Two Integers | LeetCode OJ

解法1：想想加法器的原理。

// Solution 1: Think about how an adder works.

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

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

#372 Super Pow

// #372 超級冪

描述：底數小，指數非常大，結果膜。

// Description: Super Pow | LeetCode OJ

解法1：快速冪，不過這次是十進位的。

// Solution 1: Denary exponentiation, not binary.

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

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

#373 Find K Pairs with Smallest Sums

// #373 找出和最小的前K對

描述：給定兩個有序數組，允許從倆數組各選一個數組成數對。求和最小的前K對。

// Description: Find K Pairs with Smallest Sums | LeetCode OJ

解法1：最小堆。

// Solution 1: Min heap.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/find-k-pairs-with-smallest-sums_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-k-pairs-with-smallest-sums_1_AC.cpp

#374 Guess Number Higher or Lower

// #374 高了低了

描述：猜吧。

// Description: Guess Number Higher or Lower | LeetCode OJ

解法1：二分。

// Solution 1: Binary search.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/guess-number-higher-or-lower_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/guess-number-higher-or-lower_1_AC.cpp

#375 Guess Number Higher or Lower II

// #375 高了低了

描述：還是猜數字，不過這次如果你猜x，而且猜錯了，就要罰款x元。問至少要帶多少錢才能保證贏？

// Description: Guess Number Higher or Lower II | LeetCode OJ

解法1：改個玩法，難度就完全不一樣了。將[1, n]間猜數字作為總問題，則各種[i, j]可視為子問題，我們的目的是盡量少帶錢，所以就要使罰款盡量少。由此，DP的根據就形成了。

// Solution 1: A small change in the rule create a whole new problem. If we view the guess among [1, n] as the whole problem, any [i, j] can be considered a subproblem. The goal is to bring as little money as possible, thus we need to minimize the cost of each subproblem. With these points clarified, the ground for DP is solid, now start coding.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/guess-number-higher-or-lower-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/guess-number-higher-or-lower-ii_1_AC.cpp

#376 Wiggle Subsequence

// #376 擺動子序列

描述：按照「大小大小...」或者「小大小大...」的定義。找出數組中最長擺動序列的長度。

// Description: Wiggle Subsequence | LeetCode OJ

解法1：看代碼。

// Solution 1: Read the code.

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

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

#377 Combination Sum IV

// #377 組合之和4

描述：給定集合，每個元素可使用任意多次。求加起來等於一個值target的所有組合種數，不同順序也算數。

// Description: Combination Sum IV | LeetCode OJ

解法1：根本不用搜，DP就好。

// Solution 1: Dont resort to brute-force when therere more elegant ways.

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

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

#378 Kth Smallest Element in a Sorted Matrix

// #378 楊氏矩陣第K小元素

描述：如題。

// Description: Kth Smallest Element in a Sorted Matrix | LeetCode OJ

解法1：最小堆。

// Solution 1: Min heap.

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

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

#379 Design Phone Directory

// #379 設計手機路徑

描述：設計一個電話簿，能夠分配、釋放號碼，或檢查號碼是否存在。

// Description: https://leetcode.com/problems/design-phone-directory/#/description

解法1：模擬題，懶得多說。

// Solution 1: Simulation problem.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/design-phone-directory_1_AC.cpp

解法2：用哈希表代替位向量。

// Solution 2: Replace the bit vector with a hash table.

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

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/design-phone-directory_2_AC.cpp

#380 Insert Delete GetRandom O(1)

// #380 插入、刪除、隨機讀取O(1)

描述：設計一個數據結構，能夠插入、刪除數據，並能夠以均等的機會隨機讀取一個元素。

// Description: Insert Delete GetRandom O(1) | LeetCode OJ

解法1：數組 + 哈希表。

// Solution 1: Array + hash table.

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

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

#381 Insert Delete GetRandom O(1) - Duplicates allowed

// #381 插入、刪除、隨機讀取O(1)

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

// Description: Insert Delete GetRandom O(1) - Duplicates allowed | LeetCode OJ

解法1：還是數組+哈希表，不過哈希表的內容稍加變化。

// Solution 1: Still array + hash table, just the value in the hash table needs a little change.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/insert-delete-getrandom-o1-duplicates-allowed_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/insert-delete-getrandom-o1-duplicates-allowed_1_AC.cpp

#382 Linked List Random Node

// #382 鏈表隨機節點

描述：隨機讀取鏈表的一個節點。

// Description: Linked List Random Node | LeetCode OJ

解法1：水庫採樣。

// Solution 1: Reservoir Sampling.

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

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

#383 Ransom Note

// #383 贖金紙條

描述：判斷一個字元串的字母是否是另一個字元串的子集。

// Description: Ransom Note | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

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

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

#384 Shuffle an Array

// #384 洗牌

描述：如題。

// Description: Shuffle an Array | LeetCode OJ

解法1：O(N)時間搞定。

// Solution 1: O(N) time.

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

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

#385 Mini Parser

// #385 迷你解析器

描述：給定一個嵌套字元串，將其解析成嵌套列表。

// Description: Mini Parser | LeetCode OJ

解法1：解唄。

// Solution 1: Solve it.

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

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

#386 Lexicographical Numbers

// #386 字典序數

描述：給定整數n，將1~n按字典序排序。

// Description: Lexicographical Numbers | LeetCode OJ

解法1：想想相鄰倆數之間有什麼規律？

// Solution 1: What regularities do lexicographically adjacent numbers hold?

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

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

#387 First Unique Character in a String

// #387 第一個不重複字母

描述：如題。

// Description: First Unique Character in a String | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/first-unique-character-in-a-string_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/first-unique-character-in-a-string_1_AC.cpp

#388 Longest Absolute File Path

// #388 最長絕對路徑

描述：給定文件樹，求最長絕對文件路徑。

// Description: Longest Absolute File Path | LeetCode OJ

解法1：這題測試數據有問題。

// Solution 1: The test cases of this problem are bugged.

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

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

#389 Find the Difference

// #389 找不同

描述：給定兩個字元串，其中一個多了個字母，找出該字母。

// Description: Find the Difference | LeetCode OJ

解法1：數數。

// Solution 1: Count them.

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

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

解法2：排序。

// Solution 2: Sort them.

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

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

#390 Elimination Game

// #390 消除遊戲

描述：從左到右1~n共n個數字，輪流按照「所有奇位置」「所有偶位置」的規則，去掉當前序列中對應的數，直到只剩一個數為止。問這個數是幾？

// Description: Elimination Game | LeetCode OJ

解法1：不管進行幾輪，剩下的數列始終是個等差數列。算好首項和公差，一切就真相大白了。

// Solution 1: No matter how the elimination is done, the left sequence is always arithmetic. Thus we calculate the initial term and the common difference, everything else is brought to light.

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

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

#391 Perfect Rectangle

// #391 完美矩形

描述：給定一堆矩形，問能不能恰好覆蓋成一個矩形，要求嚴絲合縫、不多不少。

// Description: Perfect Rectangle | LeetCode OJ

解法1：如果恰好能覆蓋成完整矩形，那麼面積、頂點會不會有什麼規律呢？

// Solution 1: If there happens to be an exact cover, would anything special be in the vertices and areas?

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

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

#392 Is Subsequence

// #392 是否為子序列

描述：給定一長一短倆串兒，判斷短的是不是長的的子序列。

// Description: Is Subsequence | LeetCode OJ

解法1：掃一遍就行了。

// Solution 1: Scan it.

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

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

#393 UTF-8 Validation

// #393 UTF-8驗證

描述：告訴你UTF-8的編碼規則，請驗證一段數據的合法性。

// Description: UTF-8 Validation | LeetCode OJ

解法1：按規矩來。

// Solution 1: By the book.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/utf-8-validation_1_AC.cpp

#394 Decode String

// #394 字元串解碼

描述：給定遊程碼字元串，進行解碼。

// Description: Decode String | LeetCode OJ

解法1：遞歸解碼。

// Solution 1: Decode recursively.

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

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

#395 Longest Substring with At Least K Repeating Characters

// #395 字母至少重複K次的最長子串

描述：如題，子串中的每個字母都要有至少K個，求最長子串。

// Description: Longest Substring with At Least K Repeating Characters | LeetCode OJ

解法1：還是倆指針，不過代碼稍微複雜些。

// Solution 1: Still needs two pointers. The code looks more complicated, though.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/longest-substring-with-at-least-k-repeating-characters_1_AC.cpp

#396 Rotate Function

// #396 旋轉函數

描述：懶得說。

// Description: Rotate Function | LeetCode OJ

解法1：小把戲。

// Solution 1: Small trick.

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

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

#397 Integer Replacement

// #397 整數替換

描述：如果n是偶數，則變成n / 2；否則，變成n - 1或者n + 1。問至少多少次操作，能把n變成1。

// Description: Integer Replacement | LeetCode OJ

解法1：DP。

// Solution 1: DP.

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

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

#398 Random Pick Index

// #398 隨機選下標

描述：給定一個可能有重複的數組，給定一個值，隨機輸出一個該值的下標。

// Description: https://leetcode.com/problems/random-pick-index/#/description

解法1：水庫採樣，時間換空間。

// Solution 1: Reservoir Sampling, trading time for space.

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

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

#399 Evaluate Division

// #399 變數相除

描述：給你一些變數相除的結果，要你求出另一些變數相除的結果。

// Description: Evaluate Division | LeetCode OJ

解法1：帶權並查集？

// Solution 1: Weighted union-find set?

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

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

#400 Nth Digit

// #400 第N位數

描述：把1、2、3、...寫成一串。求第N位數是什麼？

// Description: Nth Digit | LeetCode OJ

解法1：我討厭數數。

// Solution 1: I hate counting.

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

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