LeetCode 簡略題解 - 601~700

02-08

#605 Can Place Flowers

// #605 能放花嗎

描述：給定一個01數組，問能否將其中N個0變成1，使得數組中不存在相鄰的1。

// Description: Can Place Flowers

解法1：水題。

// Solution 1: Easy.

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

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

#606 Construct String from Binary Tree

// #606 二叉樹序列化

描述：給定一棵二叉樹，按照規則將其序列化，要求在無二義性的情況下，省去尾部多餘的空括弧。

// Description: Construct String from Binary Tree

解法1：水題。

// Solution 1: Trivial.

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

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

#609 Find Duplicate File in System

// #609 文件系統查重

描述：給定文件列表，和每個文件的內容，找出內容重複的文件。

// Description: Find Duplicate File in System

解法1：這題不是演算法題，而是系統設計題。題目本身沒什麼挑戰性，值得仔細思考的是follow-up部分的要求。系統設計的關鍵，通常是代碼復用、介面擴展以及計算並行化。

// Solution 1: This is not an algorithmic, but a system design problem. The problem itself is no challenge, but the follow-up section down below. The key criteria of system design problems are usually code reusability, interface scalability and computation parallelizability.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/find-duplicate-file-in-system_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/find-duplicate-file-in-system_1_AC.cpp

#611 Valid Triangle Number

// #611 有效三角數

描述：給定一個非負數組，從中選取3個數（不同順序算一樣）作為三角形的三邊。問有多少個這樣的三元組？

// Description: Valid Triangle Number

解法1：a + b > c

// Solution 1: a + b > c

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

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

#617 Merge Two Binary Trees

// #617 合併二叉樹

描述：給定兩個二叉樹，按照對應位置值相加，空節點作0處理的方法，合併兩個二叉樹。

// Description: Merge Two Binary Trees

解法1：遍歷即可，不過每個節點都應該額外分配，不能用舊節點。

// Solution 1: Just traverse them, only in that every merged node should be newly allocated, instead of tearing old ones from the two.

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

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

#621 Task Scheduler

// #621 任務調度

描述：有一些任務若干個，用A-Z表示，相同任務可能有多個。每個單位時間運行一個任務，要求兩個相同任務之間間隔不小於N，問運行完全部任務的最小時間。

// Description: Task Scheduler

解法1：數據規模不大，直接模擬。

// Solution 1: Run a simulation, considering the data scala is reasonable.

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

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

#623 Add One Row to Tree

// #623 給二叉樹加一行

描述：給定一個二叉樹，要求在深度為d的地方加一層節點，值統一設為v。

// Description: Add One Row to Tree

解法1：隨便怎麼遍歷，記錄深度即可。

// Solution 1: Traverse it all you want, just keep track of the depth.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/add-one-row-to-tree_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/add-one-row-to-tree_1_AC.cpp

#624 Maximum Distance in Arrays

// #624 最大數組距離

描述：給定m個有序數組，允許你從兩數組中各選一數，問最大差值是多少？

// Description: Maximum Distance in Arrays

解法1：其實問題不難，不過為了達到O(N)複雜度，並且使代碼簡潔些，在寫法上有點技巧。首先我么只關心每個數組中的最大值和最小值。其次，要在O(N)時間內求出對於每個數組而言，除它以外其他數組中的最大值和最小值。（看懂了嗎？）至於代碼寫法，我為了避免複製粘貼代碼，選擇將比較符作為一個函子，這點如果有函數式編程的思維，是很容易想到的。高階函數的使用可以優化代碼結構，宜善用之。

// Solution 1: The problem itself is easy, except no really if you wish to attain O(N) time. The writing is a bit tricky if you wish to make it clean. First, we care only the max and min for each array. Then, we calculate the max and min for each array except itself. (Capisch?) As for the matter of writing, I chose a functor to do the comparison, so as to reuse one piece of code to do two similar jobs. With some sense in functional programming, higher-order functions can be useful for better code organization, use it wisely.

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

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

#625 Minimum Factorization

// #625 最小因數分解

描述：給定正整數a，找出最小的的int32_t整數b，使得b的十進位位數相乘正好等於a。如果不存在就返回0。

// Description: Minimum Factorization

解法1：思路其實挺簡單，按照2、3、5、7進行因式分解，然後按9~2的順序從大到小地從a中除去，直到不能分解為止。如果不能除到1，則無解。求得的字元串排成升序就是最小結果了。代碼實現比較難看，不優雅。

// Solution 1: The idea is simple. Factorize by 2, 3, 5, 7 and divide by 9~2 all the way down from a. If it doesnt end up as 1, no solution. Otherwise, sort the resulting string in ascending order to get the final result. The implementation is a bit ugly though, uncool.

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

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

#628 Maximum Product of Three Numbers

// #628 三數最大乘積

描述：給定一個整數數組，求任取三元素所得乘積的最大值。

// Description: Maximum Product of Three Numbers

解法1：只要不是0，乘積的絕對值就會越變越大。但是負號使得乘積在最大和最小之間交替，所以要同時記錄最大值和最小值。

// Solution 1: As long as no zero is encountered, the absolute value of the product will keep growing. The presence of minus sign, however, will make the product switching between max and min. Thus we need to keep track of both.

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

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

#629 K Inverse Pairs Array

// #629 K逆序對數組

描述：給定1~N的排列，問逆序數為K的排列共有多少種？

// Description: K Inverse Pairs Array

解法1：dp[i][j]表示1~(i+1)排列中逆序數為j的種類數，動規搞起。

// Solution 1: Let dp[i][j] be the number of permutations with inverse number j, you know what to do.

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

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

#630 Course Schedule III

// #630 課表3

描述：有N門課，每門都有固定的時長和最晚完成時間。允許你自由選擇開始上課的時間以及上課順序，時間不能重疊。問最多能完成多少門課？

// Description: Course Schedule III

解法1：這是個貪婪的問題，請思考代碼中的now的意義。

// Solution 1: This is a greedy one, please think about the meaning of "now" in the code.

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

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

#632 Smallest Range

// #632 最小範圍

描述：給定k個有序數組，求一個最小的區間，使得該區間包含了每個數組中至少一個元素。

// Description: Smallest Range

解法1：Minimum Window Substring這題里的解法可以用到本題，只要稍動腦筋就知道如何轉化了。

// Solution 1: Minimum Window Substring The solution of that problem can be applied here, with just a little trick to convert the problem, were good.

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

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

#633 Sum of Square Numbers

// #633 平方數之和

描述：給定非負整數c，問是否存在整數a、b，使得a^2+b^2=c？

// Description: Sum of Square Numbers

解法1：水題。

// Solution 1: Trivial.

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

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

#635 Design Log Storage System

// #635 設計日誌文件系統

描述：比較無聊，懶得說。

// Description: Design Log Storage System

解法1：總體思路還是哈希。

// Solution 1: Hashing works just fine.

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

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

#636 Exclusive Time of Functions

// #636 函數獨佔時間

描述：給定函數調用站以及對應時間，求各個函數所佔用的CPU時間。

// Description: Exclusive Time of Functions

解法1：棧。

// Solution 1: Stack.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/exclusive-time-of-functions_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/exclusive-time-of-functions_1_AC.cpp

#637 Average of Levels in Binary Tree

// #637 二叉樹各層均值

描述：如題。

// Description: Average of Levels in Binary Tree

解法1：水。

// Solution 1: Boring.

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

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/average-of-levels-in-binary-tree_1_AC.cpp

#638 Shopping Offers

// #638 購物促銷

描述：商場有一些物品，各有價格。你有份購物清單，各有數目。現在給你一些能夠省錢的組合搭配。問你利用這些組合，最少花多少錢能完成購物任務？

// Description: Shopping Offers

解法1：多維背包。問題不難，但是理論上計算複雜度非常高。正因為如此，數據量小的一筆。數據量這麼小，就給了我們利用編碼來壓縮空間的可能。通過把多維坐標展開成一維，數據結構的設計就簡單多了。請看代碼。

// Solution 1: Its multi-dimensional knapsack problem. Not difficult, but extremely computationally intensive in theory. Thats exactly why the data scala is limited so tight. With such small data scale, we might utilitize some encoding scheme to compress space usage. Through flattening the n-dim coordinates to 1-dim, the data structure is reduced to simple arrays, making things a lot easier. Please read the code for more details.

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

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

#639 Decode Ways II

// #639 解碼方式2

描述：按照A~Z對應1~26的規則，把一串字母進行編碼。現在給你一個編碼後的字元串，但其中可能含有通配符「*」，表示0~9的任意一個。問總共有多少種不同解碼方式？結果膜1e9+7。

// Description: Decode Ways II

解法1：思路依然是DP，分析線性遞推關係。不過這題我的代碼寫得亂七八糟，思路也不甚清晰。很不清真。

// Solution 1: Still a DP problem, solved by linear recurrence relation. Yet my version of code is totally f**ked up. So lame.

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

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

#640 Solve the Equation

// #640 解方程

描述：給定一元一次只含加減法的方程，求解。

// Description: Solve the Equation

解法1：水題。

// Solution 1: Easy.

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

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

#643 Maximum Average Subarray I

// #643 最大子數組均值1

描述：給定長度為N的數組，求長度為K的子數組的最大均值。

// Description: Maximum Average Subarray I

解法1：水題。

// Solution 1: Trivial.

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

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

#644 Maximum Average Subarray II

// #644 最大子數組均值2

描述：給定長度為N的數組，求長度不小於K的子數組的最大均值。

// Description: Maximum Average Subarray II

解法1：這題不簡單，我愣想了半小時也沒個好思路，最後參考了討論區。兩點提示，0*n=0，前綴和。

// Solution 1: Quite a problem, took me half an hour for nothing, ended up seeking for help from discussion board. Two hints, 0*n=0, prefix sum.

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

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

#645 Set Mismatch

// #645 集合不匹配

描述：給定1~N，其中某個數x變成了另一個數y，且x和y都在1~N之間，求出x和y。

// Description:

解法1：數據範圍1~N，數組長度為N。不用哈希對得起觀眾？

// Solution 1: Exact data range, exact data scale. Whatcha waitin fer? Hash it.

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

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

#646 Maximum Length of Pair Chain

// #646 最大數對鏈長度

描述：對於數對(a,b)和(c,d)，已知a<b，c<d，如果b<c，則稱兩數對成鏈。給定一些數對，問能夠組成的鏈的最大長度。

// Description: Maximum Length of Pair Chain

解法1：貪婪，不過得動點腦筋。

// Solution 1: Greedy, but takes a little reckoning.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-length-of-pair-chain_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/maximum-length-of-pair-chain_1_AC.cpp

#647 Palindromic Substrings

// #647 迴文子串

描述：給定一個字元串，求所有迴文子串的個數。

// Description: Palindromic Substrings

解法1：根據Manacher演算法可以求出每個位置的迴文半徑，於是可以在O(N)時間內求出所有迴文子串的個數。不過，實在太麻煩了，於是暴力水過。

// Solution 1: With Manachers algorithm we can deduce the palindromic radius of each position, thus getting the result in O(N) time. Considering the complication, Id rather not tangle.

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

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

#648 Replace Words

// #648 替換單詞

描述：給定一個含有一堆詞根的詞典，和一句話。要求在存在詞根的情況下，把句中單詞都替換為對應詞根，要求越短越好。

// Description: Replace Words

解法1：對前綴取哈希，沿路查找是否有匹配即可。原理上和字典樹類似，但是實現簡單多了。

// Solution 1: Hash every prefixes andn search for a match along the path. Its similar to a trie, but much more efficient and simpler.

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

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

#649 Dota2 Senate

// #649 Dota2議會

描述：給定正反兩派順序排成一條隊。從第一個開始，每個人有機會消滅任何一個敵人，如果自己已被消滅，則跳過。問誰贏？

// Description: Dota2 Senate

解法1：本以為是博弈論問題，結果貪婪就夠了。

// Solution 1: I thought it was game theory, turned out greedy was good enough.

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

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

#650 2 Keys Keyboard

// #650 兩鍵鍵盤

描述：給定一個字母A，每次操作允許你複製全部文本，或者把複製好的文本粘貼一份。問得到N個A至少需要多少次操作。

// Description: 2 Keys Keyboard

解法1：DP。

// Solution 1: DP.

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

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

#652 Find Duplicate Subtrees

// #652 二叉樹查重

描述：給定一個二叉樹，找出所有存在重複的子樹。重複的定義是從根節點往下完全一樣。

// Description: Find Duplicate Subtrees

解法1：序列化，哈希。

// Solution 1: Serialization and hashing.

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

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

#653 Two Sum IV - Input is a BST

// #653 兩數之和——輸入是二叉搜索樹

描述：如題，求是否存在兩數加起來等於某和。

// Description: Two Sum IV - Input is a BST

解法1：看到不少手動遞歸、用迭代器遍歷的解法。我覺得這種題（在Leetcode上並不少見）無聊的地方就在於，明明不能提供更優的時空複雜度，卻硬要人想出一些奇奇怪怪的解法（茴），寫代碼搞得跟雜耍似的，花式裝逼很吊？骨骼這麼清奇你得練如來神掌，還寫啥代碼。我能想到的最簡單粗暴的辦法，中序遍歷+哈希。

// Solution 1: I dont know whats the point about those fancy solutions when they offer neither a better time or space complexity, nor a clean and easy solution. Were programmer, not jugglers. So what? Am I supposed to be impressed? For me, its plain and simple, an inorder traversal with hashing.

代碼1：https://github.com/zhuli19901106/leetcode-2/blob/master/two-sum-iv-input-is-a-bst_1_AC.cpp

// Code 1: https://github.com/zhuli19901106/leetcode-2/blob/master/two-sum-iv-input-is-a-bst_1_AC.cpp

#654 Maximum Binary Tree

// #654 最大二叉樹

描述：給定一個不含重複元素的數組，每次取最大元素作為二叉樹的根節點，然後按照左右子數組、左右子樹遞歸劃分，構造出整個二叉樹。

// Description: Maximum Binary Tree

解法1：直接線性查找最大，然後遞歸劃分。

// Solution 1: Linear search and recursive partition.

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

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

解法2：「查找最大」這部分是可以優化的，請搜索「RMQ問題」。

// Solution 2: "Searching for max" is eligible for optimization. Google "RMQ problem" for more info.

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

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

#655 Print Binary Tree

// #655 列印二叉樹

描述：比較無聊，懶得說。

// Description: Print Binary Tree

解法1：水題。

// Solution 1: Chores.

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

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