LeetCode 簡略題解 - 401~500

#401 Binary Watch

// #401 二進位手錶

描述：有一個手錶，假設小時範圍是0~11，分鐘範圍是0~59。如果時和分的二級製表示總共有N個1，求所有可能的時間。

// Description: Binary Watch | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#402 Remove K Digits

// #402 移除K個數字

描述：給定一個數字串，從中刪除K個數字，使得剩下的數最小。

// Description: Remove K Digits | LeetCode OJ

解法1：你可以一位一位地刪，但這麼干時間複雜度就是O(N^2)。你也可以一位位不停地刪，區別在哪兒？就在於「局部性」三個字。雖然最壞時間複雜度還是O(N ^ 2)，但平均起來則是O(N)，性能明顯提高了。

// Solution 1: You can remove the digits one by one, which results in a total of O(N ^ 2) time. You can also remove them in a row. The difference lies in "locality", here it means spatial locality. Although the worst case stays in O(N ^ 2), the average case is improved to O(N), good progress indeed.

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

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

#403 Frog Jump

// #403 青蛙跳

描述：一隻青蛙站在0點，有一些石頭分布在前面。第一步必須跳1格，之後每步距離可以比上一步多1或少1。只能跳石頭上，不能掉水裡。問能否成功跳到最後一顆石頭上。

// Description: Frog Jump | LeetCode OJ

解法1：從數據範圍看，我猜是個O(N ^ 2)的問題。於是我選擇BFS。為什麼不用DP？因為DP的代碼寫起來也未必多簡潔。

// Solution 1: Judging from the number of stones, I think O(N ^ 2) is tolerable. Thus I chose BFS. Why not DP instead. With the constraints in the jumping distance, I dont think using DP can make your code any cleaner.

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

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

#404 Sum of Left Leaves

// #404 左葉子之和

描述：給定二叉樹，求左葉節點之和。

// Description: Sum of Left Leaves | LeetCode OJ

解法1：水題。

// Solution 1: Piece of date cake.

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

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

#405 Convert a Number to Hexadecimal

// #405 十進位轉十六進位

描述：如題。

// Description: Convert a Number to Hexadecimal | LeetCode OJ

解法1：碰見負數怎麼辦？看著辦。

// Solution 1: What about negative numbers? What about it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/convert-a-number-to-hexadecimal_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/convert-a-number-to-hexadecimal_1_AC.cpp

#406 Queue Reconstruction by Height

// #406 按高度重建隊列

描述： 有N個人排成一條隊。現在給你每個人的高度，以及站他前面不比他矮的人的個數。請把整個隊列重建出來。

// Description: Queue Reconstruction by Height | LeetCode OJ

解法1：直接看代碼吧。注意兩點，第一是排序方式，第二是插入方式。

// Solution 1: Just read the code. Two points worth noting, one is the sorting comparator, one is the insertion process.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/queue-reconstruction-by-height_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/queue-reconstruction-by-height_1_AC.cpp

解法2：這個解法很巧妙，我鼓搗了一個多鐘頭才想明白。首先，這題除了O(N ^ 2)的暴力解法，肯定有更高效的解法。為什麼？因為這是個關於「排序」的問題，你們都知道O(N * logN)是比較排序的下界。而且這題涉及到了數數。所以，我決定用樹狀數組試試，結果還真搞出來了。雖然實際複雜度不是O(N * logN)，而是O(N * log ^2 N)。但總體的思想，還是二分搜索。用樹狀數組，只是為了區間求和。

// Solution 2: This is a clever solution. (Im not saying its a short solution.) Took me more than an hour to figure out. First of all, I believed theres a better solution to this problem than an O(N ^ 2) brute-force one. Because its about "order", and you know theres a lower bound of O(N * logN) for any comparative sorting algorithm. This problem also involved counting, which led me to BIT. It worked, as expected. The overall time complexity is actually O(N * log ^ 2 N) instead of O(N * logN), due to the binary search in a BIT. Using a BIT here is because I need range summation.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/queue-reconstruction-by-height_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/queue-reconstruction-by-height_2_AC.cpp

#407 Trapping Rain Water II

// #407 雨水積水問題

描述：跟之前一樣，但這次的地形是二維的。

// Description: Trapping Rain Water II | LeetCode OJ

解法1：首先，你不能像之前一樣，還用幾層for循環搞定。因為水只往低處流，不管東西南北，而for循環的方向，總是固定的。那怎麼辦呢？BFS。

// Solution 1: First, you cant get it done with just a few nested for-loops. Because water flows downhill, no matter which direction it might be, while the direction inside a for-loop is pre-defined. So how do we deal with it? BFS.

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

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

#408 Valid Word Abbreviation

// #408 合法單詞縮寫

描述：給定一個單詞，允許把其中一個或多個部分替換成對應長度，但替換的部分不能相鄰。先給定一個單詞和一個對應縮寫，判斷縮寫是否合法。

// Description: Valid Word Abbreviation | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

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

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

#409 Longest Palindrome

// #409 最長迴文串

描述：給定一個串，允許從其中選一些字母，問能拼成的最長迴文串有多長？

// Description: Longest Palindrome | LeetCode OJ

解法1：不是判斷迴文子串，水題。

// Solution 1: This is not palindromic substring. Piece of zaogao.

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

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

#410 Split Array Largest Sum

// #410 分割子數組最大和

描述：給定一個數組，要求分割為M段，求其中最大子數組和的最小值。

// Description: Split Array Largest Sum | LeetCode OJ

解法1：要求最大值最小，這種問題是演算法中經常研究的問題。決策理論里不也有Minimax問題么。因為這題是分割子數組，所以可以用DP搞定。那麼，如果是分成M堆，不要求元素連續的話，又當如何求解？那就是集裝箱問題嘍，誰愛做誰做。

// Solution 1: To minimize the maximum, these sort of problems are widely studied in computer science. Isnt there something called "Minimax" in Decision Thoery, for instance? As this problem is about splitting subarrays, we can do it with DP. Say, if the problem is about partitioning the set into M subsets. What do we do? I guess its then a combinatorial problem, anyway, not mine to worry about.

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

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

解法2：省點空間。

// Solution 2: Save some space, for the rainy days.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/split-array-largest-sum_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/split-array-largest-sum_2_AC.cpp

#411 Minimum Unique Word Abbreviation

// #411 最短唯一單詞縮寫

描述：按照之前給定的縮寫規則，現在給你一個詞和一個詞典。為該詞找一個長度最短的縮寫，要求該縮寫不能和詞典里的其他單詞對上號兒。

// Description: https://leetcode.com/problems/minimum-unique-word-abbreviation/#/description

解法1：首先，基本思路就是搜。怎麼搜呢？隨便，反正代碼都挺難看的。重要的是，怎麼判斷一個縮寫是否和詞典里的縮寫發生重合呢？請看markBit函數。

// Solution 1: Firstly, this is about DFS. How? Doesnt matter. The code cant possibly look any better. What really matters is the way we check if an abbreviation collides with one in the dictionary. See markBit() for more details.

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

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

#412 Fizz Buzz

// #412 報數

描述：從1~N依次報數，3的倍數說Fizz，5的倍數說Buzz，15的倍數說FizzBuzz。

// Description: Fizz Buzz | LeetCode OJ

解法1：水題。

// Solution 1: Most trivial.

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

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

#413 Arithmetic Slices

// #413 等差數列片段

描述：給定數組，找出最長的滿足等差數列條件的子數組長度。

// Description: Arithmetic Slices | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#414 Third Maximum Number

// #414 第三大的數

描述：給定一個數組，找出第三大的數。

// Description: Third Maximum Number | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#415 Add Strings

// #415 高精度加法

描述：如題。

// Description: Add Strings | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#416 Partition Equal Subset Sum

// #416 平分集合

描述：給定一堆數，判斷能否分為兩堆，使得兩堆的和相等。

// Description: Partition Equal Subset Sum | LeetCode OJ

解法1：背包問題。

// Solution 1: Knapsack Problem.

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

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

#417 Pacific Atlantic Water Flow

// #417 太平洋大西洋水流

描述：給定mxn矩陣，左上挨著太平洋，右下挨著大西洋。已知水能流向等高或者更低的地方。 請找出所有兩大洋的位置。

// Description: Pacific Atlantic Water Flow | LeetCode OJ

解法1：搜。

// Solution 1: Flood it.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/pacific-atlantic-water-flow_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/pacific-atlantic-water-flow_1_AC.cpp

#418 Sentence Screen Fitting

// #418 屏幕文字填充

描述：給定一句話，和一個尺寸固定的屏幕。單詞之間至少要用一個空格分割，行尾的空格可以省略。求這句話能在屏幕里完整重複多少次。

// Description: https://leetcode.com/problems/sentence-screen-fitting/#/description

解法1：網上有的解法， 是找循環節。我覺得這辦法雖然可行，但會存在bad case，使得複雜度接近O(N ^ 2)。於是我琢磨了個二分搜索的辦法。對於屏幕上的每一行，每一次都通過二分查找，盡量填充到行尾，然後換行。

// Solution 1: Some of the solutions from the Internet focus on determining the length of the cycle. This is a feasible, but vulnerable one, as there might be bad cases that lead to an O(N ^ 2) running time. Mine here is devised from the idea of binary search. For each line, fill as many words as you can with one binary search and go to the next.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/sentence-screen-fitting_1_AC.cpp

#419 Battleships in a Board

// #419 棋盤上的戰艦

描述：棋盤上有一些戰艦，都是橫平豎直的，而且相互不接觸。求總共有多少條。

// Description: Battleships in a Board | LeetCode OJ

解法1：O(1)空間，很好。

// Solution 1: O(1) space, good.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/battleships-in-a-board_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/battleships-in-a-board_1_AC.cpp

#420 Strong Password Checker

// #420 高安全性密碼檢查

描述：給定一個密碼字元串，要求通過最少的「編輯」（還記得最短編輯距離嗎？）使密碼具有高安全性。怎麼才算安全呢，第一長度要6~20，第二要有大寫有小寫有數字，第三連續重複字母不能達到3個。

// Description: Strong Password Checker | LeetCode OJ

解法1：難題。這題搞了我將近兩個鐘頭，所以我一句都不想說。面試碰見這種題，你就認倒霉吧。

// Solution 1: A hard problem. It took me almost two hours to get it done. Too tired to say a word. Just pray you dont meet it in a real battle, because chances are that youre gonna be f*ed up.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/strong-password-checker_1_AC.cpp

#421 Maximum XOR of Two Numbers in an Array

// #421 倆數組元素異或的最大值

描述：如題。

// Description: Maximum XOR of Two Numbers in an Array | LeetCode OJ

解法1：暴力解法就不說了。這個解法不是我想出來的，非常精妙。

// Solution 1: Brute-force solution is trivial. This one here is not by me, very clever and concise.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-xor-of-two-numbers-in-an-array_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-xor-of-two-numbers-in-an-array_1_AC.cpp

#422 Valid Word Square

// #422 有效字母方陣

描述：給定幾排字元串，判斷是不是按對角線對稱的。

// Description: https://leetcode.com/problems/valid-word-square/#/description

解法1：注意邊界。

// Solution 1: Mind the edge.

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

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

#423 Reconstruct Original Digits from English

// #423 根據英語重建數字串

描述：給定一個數字串，把它用英語說出來，然後字母全連一塊兒，再打亂順序。現在給你這個亂序的字母串，把數字串重建出來。

// Description: Reconstruct Original Digits from English | LeetCode OJ

解法1：介尼瑪是個腦筋急轉彎，嘛玩意兒。

// Solution 1: I got a name for problems like this: brain teasers.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/reconstruct-original-digits-from-english_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/reconstruct-original-digits-from-english_1_AC.cpp

#424 Longest Repeating Character Replacement

// #424 替換後的最長重複子串

描述：給定一個字元串，允許你任選最多K個字元進行任意替換。問替換以後，能得到的包含同一字母的子串最長能有多長？

// Description: Longest Repeating Character Replacement | LeetCode OJ

解法1：還是倆指針。這種最長XX子串問題都見了一堆了，還有多少個？

// Solution 1: Still two pointers. Ive seen enough of these problems, just how many more to go?

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

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

#425 Word Squares

// #425 單詞方陣

描述：給定一堆長度相同的單詞，從中選出一些構成方陣，要求方陣依對角線對稱。求出所有可能的方陣。

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

解法1：題目雖然不簡單，但思路倒是很簡單，搜唄。

// Solution 1: The problem is rated "hard", but the solution is simple. Run a DFS.

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

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

#432 All O`one Data Structure

// #432 全O(1)數據結構

描述：設計一個類似hash map的計數器，但要提供最大值對應鍵值、最小值對應鍵值的功能。

// Description: All O`one Data Structure | LeetCode OJ

解法1：哈希表 + 雙向鏈表，想想都覺得麻煩。碰見這種破題，面試能給多長時間？藥丸。

// Solution 1: Hash table + doubly linked list, the very thought is tiring enough. How long do you think you can spare for this one?

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/all-oone-data-structure_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/all-oone-data-structure_1_AC.cpp

#434 Number of Segments in a String

// #434 單詞個數

描述：給個句子，數詞兒。

// Description: Number of Segments in a String | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/number-of-segments-in-a-string_1_AC.cpp

#435 Non-overlapping Intervals

// #435 不重合區間

描述：給定一堆區間，進行適當合併，使結果互不重疊。緊鄰不算重合。

// Description: Non-overlapping Intervals | LeetCode OJ

解法1：DP。

// Solution 1: DP.

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

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

解法2：貪婪。

// Solution 2: Be greedy.

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

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/non-overlapping-intervals_2_AC.cpp

#436 Find Right Interval

// #436 找右區間

描述：給定一系列區間，對每個區間，找出其右側（不是下標，而是區間值）最近的區間。

// Description: Find Right Interval | LeetCode OJ

解法1：先排序，後二分。

// Solution 1: Sort and binary search.

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

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

#437 Path Sum III

// #437 路徑和3

描述：給定一棵二叉樹，允許從任意點出發，到任意點為止，但要求必須從上往下走。對於給定的值target，求路徑和等於target的路徑有多少條？

// Description: Path Sum III | LeetCode OJ

解法1：搜。

// Solution 1: Traverse it.

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

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

解法2：加個緩存。

// Solution 2: Cache it.

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

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/path-sum-iii_2_AC.cpp

#438 Find All Anagrams in a String

// #438 找出所有變位詞

描述：給定字元串S和P，找出S中所有和P字母構成相同（變位詞）的子串，返回下標。

// Description: Find All Anagrams in a String | LeetCode OJ

解法1：倆指針。

// Solution 1: Two pointers.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-anagrams-in-a-string_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-anagrams-in-a-string_1_AC.cpp

#439 Ternary Expression Parser

// #439 三元表達式解析器

描述：如題。

// Description: Ternary Expression Parser | LeetCode OJ

解法1：想清楚運算規則，分好詞，用棧鼓搗去吧。

// Solution 1: Figure out the rules, tokenize it and see what you can do with the stacks.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-anagrams-in-a-string_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-anagrams-in-a-string_1_AC.cpp

#440 K-th Smallest in Lexicographical Order

// #440 字典序第K小的數

描述：將1~N按照字典序排序，找出第K個。

// Description: K-th Smallest in Lexicographical Order | LeetCode OJ

解法1：這倒是個難題，剛開始毫無頭緒。後來看了看討論區里大家的說法，其中「tree」一詞讓我茅塞頓開。什麼樹？十叉樹。所以，你明白了嗎？我們為什麼要學各種抽象數據結構？因為這些東西能讓你的思維形象化、具體化。

// Solution 1: This one seemed like tough. I got no lead at all for the first few minutes. After looking around the Discuss section, the word "tree" hit me. What tree? A denary tree. So, you got it? Why do we need those ADS? Because they help visualize and substantiate our thoughts.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/k-th-smallest-in-lexicographical-order_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/k-th-smallest-in-lexicographical-order_1_AC.cpp

#441 Arranging Coins

// #441 擺硬幣

描述：你有N枚硬幣，你想把它們擺成1、2、3、...的樓梯形。問最多能擺多少級樓梯？

// Description: Arranging Coins | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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

#442 Find All Duplicates in an Array

// #442 找出所有重複元素

描述：給定一個長度為N的數組，所有元素都在[1, N]之間。所有數要麼出現一次，要麼出現兩次。找出出現兩次的元素。

// Description: Find All Duplicates in an Array | LeetCode OJ

解法1：數數。

// Solution 1: Count them.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-duplicates-in-an-array_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-duplicates-in-an-array_1_AC.cpp

#444 Sequence Reconstruction

// #444 序列重建

描述：給你一個序列org，再給你一堆序列seqs。按照seqs每個序列中元素的先後順序，問是否能重建出唯一一個序列來，而且該序列就是org。

// Description: https://leetcode.com/problems/sequence-reconstruction/#/description

解法1：拓撲排序。

// Solution 1: Topological sort.

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

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

#445 Add Two Numbers II

// #445 兩數相加2

描述：倆數用鏈表表示，做個加法。

// Description: Add Two Numbers II | LeetCode OJ

解法1：無聊。

// Solution 1: Boring.

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

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

#446 Arithmetic Slices II - Subsequence

// #446 等差數列片段2 - 子序列

描述：和之前一樣，不過這次是子序列。

// Description: Arithmetic Slices II - Subsequence | LeetCode OJ

解法1：一看就是DP，不過不能用二維數組表示，因為公差你不知道是多少。所以呢，咱們搞個哈希表。哈希大法好。

// Solution 1: It should be DP at first sight, but not to be done with a 2-d array, because you dont know how big the common differences can be. So, lets hash. Hashing rocks.

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

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

#447 Number of Boomerangs

// #447 迴旋鏢的個數

描述：給定平面上N個不重合的點，如果有ABC三點使得AB=AC，則稱ABC是個迴旋鏢（等腰三角形嘛），求迴旋鏢的個數。

// Description: Number of Boomerangs | LeetCode OJ

解法1：一看就是哈希。

// Solution 1: Hash at first sight.

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

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

#448 Find All Numbers Disappeared in an Array

// #448 找出數組中所有失蹤的數

描述：和442題一樣，這次找的是沒出現的數。

// Description: Find All Numbers Disappeared in an Array | LeetCode OJ

解法1：數數。

// Solution 1: Count them.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-numbers-disappeared-in-an-array_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-numbers-disappeared-in-an-array_1_AC.cpp

解法2：還是數數。

// Solution 2: Count already.

代碼2：https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-numbers-disappeared-in-an-array_2_AC.cpp

// Code 2: https://github.com/zhuli19901106/leetcode-2/blob/master/find-all-numbers-disappeared-in-an-array_2_AC.cpp

#449 Serialize and Deserialize BST

// #449 序列化反序列化一棵二叉搜索樹

描述：如題。

// Description: Serialize and Deserialize BST | LeetCode OJ

解法1：老實說，我沒想出「BST」有沒有值得深挖的地方。好像沒什麼可以特殊處理的地方啊？

// Solution 1: Honestly, I havent come up with a way to exploit the keyword "BST". Nothing seemed conspicuous to me.

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

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

#450 Delete Node in a BST

// #450 二叉搜索樹刪除節點

描述：如題。

// Description: Delete Node in a BST | LeetCode OJ

解法1：這題貌似是個經典面試題，而且挺難的。我就不解釋了，你自個兒琢磨去吧。反正我在草稿紙上花了半天，才把這破題給整明白，代碼也是倒騰了好一會兒。面試碰見這種題，你就自求多福吧。

// Solution 1: This one, AFAIK is a real classic one, very challenging too. Pray you dont run into it. Save your prayers if you do, just think it through really carefully and write your code slow and steady.

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

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

#451 Sort Characters By Frequency

// #451 按頻率將字母排序

描述：如題。

// Description: Sort Characters By Frequency | LeetCode OJ

解法1：水題。

// Solution 1: Piece of pancake.

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

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

#452 Minimum Number of Arrows to Burst Balloons

// #452 射穿氣球的最少箭數

描述：給定一些圓心在X軸上的氣球，告訴你每個氣球的左右邊界。現在允許你以平行Y軸的方向射箭穿過X軸，問至少幾支箭可以射破所有氣球？

// Description: Minimum Number of Arrows to Burst Balloons | LeetCode OJ

解法1：可以貪婪。

// Solution 1: Greed is good.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-number-of-arrows-to-burst-balloons_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-number-of-arrows-to-burst-balloons_1_AC.cpp

#453 Minimum Moves to Equal Array Elements

// #453 令所有元素相等的最小操作數

描述：給定N個元素的數組，每次操作允許你把N - 1各元素加1。問至少多少次能把所有元素變成一樣？

// Description: Minimum Moves to Equal Array Elements | LeetCode OJ

解法1：不就是把一個元素減1么？

// Solution 1: Aint no difference than decrementing one element by 1, right?

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-moves-to-equal-array-elements_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-moves-to-equal-array-elements_1_AC.cpp

#454 4Sum II

// #454 四數之和2

描述：給定四個數組，從中各選一個元素使得加起來等於0。求共有多少種選法？

// Description: 4Sum II | LeetCode OJ

解法1：暴力過。

// Solution 1: Brute-force.

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

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

#455 Assign Cookies

// #455 分餅乾

描述：有M塊餅乾，有大有小。有N個孩子，孩子對餅乾大小有要求，小了就發脾氣。每個孩子至多分一塊，問你最多能哄幾個孩子高興？

// Description: Assign Cookies | LeetCode OJ

解法1：貪婪。

// Solution 1: Be greedy.

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

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

#456 132 Pattern

// #456 132形式

描述：給定數組，問是否存在三個元素依次為ABC，使得A < C < B？

// Description: 132 Pattern | LeetCode OJ

解法1：謎之題目，謎之解法。

// Solution 1: I see it , but I dont get it.

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

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

#459 Repeated Substring Pattern

// #459 重複模式串

描述：給定字元串，問其是否存在循環節。

// Description: Repeated Substring Pattern | LeetCode OJ

解法1：KMP演算法知道吧？用next數組搞定。長度就算500萬也沒問題。

// Solution 1: You know KMP right? Use the "next" array on this. It can handle a string of 5 million charaters.

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

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

#460 LFU Cache

// #460 最低頻率緩存

描述：LRU知道吧？與LRU不同，LFU的替換依據是使用頻率。

// Description: LFU Cache | LeetCode OJ

解法1：懶得說，灰常麻煩。雙向鏈表、哈希表、LRU緩存都用上了，還有什麼好說的？趕緊寫吧。

// Solution 1: Too much trouble. Here you got doubly linked list, hash table, LRU cache, what else would I wanna say? Just start coding before you run out of time.

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

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

#461 Hamming Distance

// #461 漢明距離

描述：兩數異或二進位表示中1的個數。

// Description: Hamming Distance | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

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

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

#462 Minimum Moves to Equal Array Elements II

// #462 使所有元素相等的最少步數2

描述：給定數組，每次允許選一個元素加1或減1，問至少多少步，可以是所有元素相等？

// Description: Minimum Moves to Equal Array Elements II | LeetCode OJ

解法1：找中位數。

// Solution 1: Find the median.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-moves-to-equal-array-elements-ii_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/minimum-moves-to-equal-array-elements-ii_1_AC.cpp

#463 Island Perimeter

// #463 島嶼周長

描述：給定01矩陣，1表示陸地，求島嶼周長。

// Description: Island Perimeter | LeetCode OJ

解法1：只要考慮每個1四周有幾個1就行了。

// Solution 1: Just find out how many 1s there are around each 1.

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

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

#464 Can I Win

// #464 我能贏嗎

描述：給定1~N，以及一個整數S。開始和為0，兩人輪流從1~N選一個數，加到和里去。誰讓和達到或超過S就算贏。選出的數不能重複使用。

// Description: Can I Win | LeetCode OJ

解法1：記憶化搜索。

// Solution 1: DFS with memorization.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/can-i-win_1_AC.cpp

#465 Optimal Account Balancing

// #465 最佳賬戶平衡策略

描述：朋友之間可以相互借錢還錢。現在給定一些朋友間借錢的操作，請你設計用最少的還錢策略，使得大家互不相欠。

// Description: Optimal Account Balancing | LeetCode OJ

解法1：這是個難題，而且是NPC的難題。首先，難點在於你很容易把這題看成一個簡單的貪婪問題。其次，難點在於你要明白這其實是個關於集合劃分的問題。劃分什麼？對於一個和為0的集合S，劃分一個個的子集，使得每個子集的和都為0，而且都不進一步劃分。接著想吧。

// Solution 1: This is a tough one, an NPC one actually. The first challenge is to consider it a challenge, not a simple greedy one. Next, you have to see the partition problem out of it. What partition? Partition what? Given a multiset S which sums to 0, partition it into some sub-multisets, who sum to 0 as well and are not furtherly partitionable. Get on with it.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/optimal-account-balancing_1_AC.cpp

#466 Count The Repetitions

// #466 統計重複次數

描述：我們用[S, n]表示S字元串重複n遍。現在給定S1 = [s1, n1]和S2 = [s2, n2]，問使得[S2, M]是S1子序列的最大M是多少？

// Description: Count The Repetitions | LeetCode OJ

解法1：題目比較難懂，其實就是問S2能以子序列的形式在S1里重複多少遍。我的演算法基本是暴力的。有什麼更好的解法嗎？

// Solution 1: The problem description is a bit confusing. Its about counting how many S2 you can find in S1 as subsequences. My solution here is basically brute-force. Got anything better to suggest?

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

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

#467 Unique Substrings in Wraparound String

// #467 循環字元串中的唯一子串

描述：將a~z依次寫下去，構成一個無限長串S。現在給定一個字元串P，問P中有多少不同的子串出現在了S中。

// Description: Unique Substrings in Wraparound String | LeetCode OJ

解法1：想想，怎麼比較高效地表示abc、zabcd之類的字元串？

// Solution 1: Think about how to represent strings like "abc", "zabcd" efficiently?

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/unique-substrings-in-wraparound-string_1_AC.cpp

#468 Validate IP Address

// #468 驗證IP地址

描述：驗證IPv4或者IPv6地址。

// Description: Validate IP Address | LeetCode OJ

解法1：麻煩得很。

// Solution 1: I smell trouble.

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

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

#469 Convex Polygon

// #469 凸多邊形

描述：給定一對頂點，判斷是否為凸多邊形。

// Description: Convex Polygon | LeetCode OJ

解法1：叉乘可以求面積，面積是有方向的，方向相反就不好了。

// Solution 1: Cross product can be used to calculate area, area is directed, opposite direction is not politically correct.

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

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

#471 Encode String with Shortest Length

// #471 以最小長度編碼字元串

描述：對於字元串abcabcabc，你可以編碼成3[abc]，也可以不編碼。現在給你一個字元串S，允許你對其中的部分進行遞歸編碼，求出一種長度最短的編碼結果。

// Description: Encode String with Shortest Length | LeetCode OJ

解法1：難題。總體思路是記憶化搜索。另外，需要判斷字元串里的循環節，所以又要用到next數組了。

// Solution 1: A tough one. The idea is DFS with memorization. Besides, we need to calculate the length of every repetend in the string, so bring you "next" array.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/encode-string-with-shortest-length_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/encode-string-with-shortest-length_1_AC.cpp

#472 Concatenated Words

// #472 連接而成的詞

描述：給定一個詞典，從中找出能夠由其他至少兩個詞連接而成的詞。

// Description: Concatenated Words | LeetCode OJ

解法1：暴力DP，也不完全算是暴力，好歹還有個排序。

// Solution 1: Brute-force DP, if not totally brute-force. At least there is a sorting before that.

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

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

#473 Matchsticks to Square

// #473 火柴棍拼正方形

描述：給定一些長度不一的火柴棍，允許首尾相接。問能否拼成一個正方形？

// Description: Matchsticks to Square | LeetCode OJ

解法1：搜，但要注意姿勢。

// Solution 1: DFS, in the right stance.

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

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

#474 Ones and Zeroes

// #474 1和0

描述：給定一些01字元串，給你m個0和n個1，允許你做一些分配。問你最多能配出這些字元串中的幾個？

// Description: Ones and Zeroes | LeetCode OJ

解法1：半天沒看懂題目，懂了以後發現是個二維背包問題。

// Solution 1: Took me quite a while to tune in. Seemed like a 2-d Knapsack problem to me.

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

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

#475 Heaters

// #475 暖氣

描述：假設有一些房子，有一些暖氣，全都排在一條直線上。為了保證所有房子都被暖氣覆蓋到， 求最小的供暖半徑。

// Description: Heaters | LeetCode OJ

解法1：想想歸併排序。

// Solution 1: Think about Merge Sort.

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

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

#476 Number Complement

// #476 互補數

描述：給定一個數，按照二進位取反。

// Description: Number Complement | LeetCode OJ

解法1：位操作。

// Solution 1: Bit manipulations.

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

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

#477 Total Hamming Distance

// #477 總漢明距離

描述：給定一堆數，求兩輛漢明距離之和。

// Description: Total Hamming Distance | LeetCode OJ

解法1：按位考慮。

// Solution 1: Bit by bit.

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

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

#479 Largest Palindrome Product

// #479 最大迴文乘積

描述：給定一個數N，求兩個N位數相乘所能構成的最大迴文數，結果膜1337。據說N非常大，有8那麼大，怕不怕？

// Description: Largest Palindrome Product

解法1：你就說int64_t不就得了。另外，我跟大多數人一樣，實在不知道這題到底哪兒簡單了？暴力打表嗎？

// Solution 1: Why dont you say int64_t already. Besides, like the rest majority, I dont know where the hell did that "Easy" come from. Precalculation or what?

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

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

#480 Sliding Window Median

// #480 滑動窗口中位數

描述：給定一個數組，和一個固定大小的窗口。當窗口不斷向前滑動時，求出一系列中位數。

// Description: Sliding Window Median | LeetCode OJ

解法1：和Find Median from Data Stream一樣的解法。

// Solution 1: Same as Find Median from Data Stream.

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

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

#481 Magical String

// #481 神奇字元串

描述：我說我看不懂題目，你信嗎？

// Description: Magical String | LeetCode OJ

解法1：反正我信。

// Solution 1: The f* is that?

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

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

#482 License Key Formatting

// #482 序列號格式化

描述：太長不寫。

// Description: License Key Formatting | LeetCode OJ

解法1：水題。

// Solution 1: Dull.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/license-key-formatting_1_AC.cpp

#483 Smallest Good Base

// #483 最小的好基數

描述：給定一個整數N，如果對於整數K，使得N在K進位表示下每一位都是1，則認為K很好。求最小的好基數K。

// Description: Smallest Good Base | LeetCode OJ

解法1：顯然N - 1很好，所以這題首先是有解的。而N - 1就是上界。接下來怎麼辦呢？二分搜唄。

// Solution 1: Apparently N - 1 is a good base, so the problem is always solvable. As N - 1 is the upper bound for solutions, what we do next is to enumerate some parameters and solve some equations with binary search. Its numerical, so make sure you know things like error, truncation, overflow, etc..

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/smallest-good-base_1_AC.cpp

#484 Find Permutation

// #484 找出排列

描述：有一個1~N組成的排列，現在給你一個長度為N - 1的由DI組成的字元串，表示相鄰元素的關係是增還是減。根據這個串，請重建出字典序最小，而且滿足要求的排列。

// Description: https://leetcode.com/problems/find-permutation/#/description

解法1：想了半天，毫無頭緒。於是參考了網上的神解法。

// Solution 1: Not a single lead on this one. Here is a most brilliant solution from the Internet.

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

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

#485 Max Consecutive Ones

// #485 最長連續1子串

描述：如題。

// Description: Max Consecutive Ones | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/max-consecutive-ones_1_AC.cpp

#486 Predict the Winner

// #486 預測贏家

描述：給定一個數組，每個元素表示一個分數。倆人輪流，每次從左端或右端拿走一個分數，如此直到拿完。分高的人贏。問先手是否必勝？

// Description: Predict the Winner | LeetCode OJ

解法1：不要一看數據量很小，就暴力搜。暴力能解決問題嗎？不能啊。年輕人嘛，還是要DP，不要暴力。

// Solution 1: If it looks like DP, its DP.

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

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

#487 Max Consecutive Ones II

// #487 最長連續1子串2

描述：和之前一樣，不過這次允許你把一個0變成1。

// Description: Max Consecutive Ones II | LeetCode OJ

解法1：搞個狀態機試試？

// Solution 1: Try using a state machine?

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

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

#488 Zuma Game

// #488 祖瑪遊戲

描述：給定一串彩色球，再給你幾個球用來發射。每次發射你都可以隨便挑剩下的任一個，3個一消。問最少用多少個球可以消光。如果搞不定，返回-1。

// Description: Zuma Game | LeetCode OJ

解法1：基本算是暴力搜吧。

// Solution 1: Its basically a brute-force DFS.

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

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

#490 The Maze

// #490 迷宮

描述：給定一個01矩陣，1表示牆，0表示空地。現在球從起點出發，目標是到達終點。每次球可以朝一個方向滾，但滾動時必須撞牆才能換方向。問是否能到達終點。

// Description: https://leetcode.com/problems/the-maze/#/description

解法1：搜。

// Solution 1: DFS.

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

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

#491 Increasing Subsequences

// #491 遞增子序列

描述：給定一個數組，找出總共有多少不同的遞增子序列。

// Description: Increasing Subsequences | LeetCode OJ

解法1：暴力搜。我知道，這題的數據量非常小，而且數據範圍也很小，明擺著是要你DP。懶得寫了。

// Solution 1: Brute-force DFS. I know the size and range are both quite small. Clearly its indicating a DP solution. Just too lazy to try it out.

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

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

#492 Construct the Rectangle

// #492 構造矩形

描述：給定一個面積A，求出矩形長寬，使得矩形面積等於A，並且長寬儘可能接近。

// Description: Construct the Rectangle | LeetCode OJ

解法1：水題。

// Solution 1: Trivial.

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

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

#493 Reverse Pairs

// #493 逆序對

描述：給定一個數組，如果對於下標i < j，並且a[i] > 2 * a[j]，則稱為一個逆序對。求逆序對的個數。

// Description: Reverse Pairs | LeetCode OJ

解法1：又是比較 + 數數問題，樹狀數組搞定。

// Solution 1: Comparison and counting again, let BIT do the job.

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

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

#494 Target Sum

// #494 目標和

描述：給定一個數組，允許你對每個元素選擇加或減。問有多少種選法，能讓結果等於S。

// Description: Target Sum | LeetCode OJ

解法1：可以算是背包問題。

// Solution 1: Sort of like a Knapsack problem.

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

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

#495 Teemo Attacking

// #495 提莫進攻

描述：給定一些進攻的時間點，和進攻的中毒持續時間，求敵人總共的中毒時間。

// Description: Teemo Attacking | LeetCode OJ

解法1：這麼水的題，居然是medium？

// Solution 1: Too trivial to be rated "medium", I think.

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

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

#496 Next Greater Element I

// #496 下一個更大元素1

描述：給定無重複元素的數組a1和a2，其中a1是a2的子集。對於a1每個元素，找出其在a2中對應位置右邊的第一個大於它的元素。

// Description: Next Greater Element I | LeetCode OJ

解法1：破題目，真難讀懂。看樣子要用個棧，試了試，我看行。

// Solution 1: Hell of a problem to read. Looks like I need a stack, looks like my instinct is right.

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

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

#498 Diagonal Traverse

// #498 對角遍歷

描述：給定矩陣，按照「右上、左下」的方式輪換遍歷整個矩陣。

// Description: Diagonal Traverse | LeetCode OJ

解法1：讓幹嘛就幹嘛。

// Solution 1: Do as told.

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

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

#499 The Maze III

// #499 迷宮3

描述：和之前一樣，不過這次終點是個洞。除了掉進洞以外，球依然是撞牆才能轉向。現在請找出一條距離最短的路徑，使得球能滾進洞。要求輸出完整的路徑，並保證輸出的路徑是可行解里字典序最小的。

// Description: The Maze III | LeetCode OJ

解法1：輸出路徑也就算了，還尼瑪字典序最小，這題簡直把「麻煩」二字演繹到了極致。思路很簡單，實現很複雜。

// Solution 1: You dont worry when its not your problem. You dont suffer when its not your headache. Simple idea, lengthy implementation.

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

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

#500 Keyboard Row

// #500 鍵盤行

描述：給定一些單詞，問其中有多少可以在鍵盤的一行里打出來。

// Description: Keyboard Row | LeetCode OJ

解法1：水題。

// Solution 1: Easy.

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

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