本文內(nèi)容為練習(xí)LeetCode題目時(shí)的解題思路和不同算法的記錄罗岖，實(shí)現(xiàn)語(yǔ)言為C++泻云，代碼保存在Github固该，均已在LeetCode提交AC且均含最優(yōu)解并盡多嘗試多解握础，單擊標(biāo)題以查看，持續(xù)更新扫尖，暫時(shí)只進(jìn)行Top Interview Questions列表下題目白对。

現(xiàn)在覺得全寫在一篇文章里面過于臃腫且不易查找，我又不想做個(gè)目錄出來换怖，那樣豈不是更臃腫甩恼？因此如果刷第二遍或者準(zhǔn)備停止刷LeetCode的話我會(huì)把這篇記錄按題目拆分出來，也許會(huì)根據(jù)專題整理一下多一級(jí)目錄狰域，也許不會(huì)媳拴，簡(jiǎn)書的文集內(nèi)不能再分級(jí)實(shí)在是一個(gè)很不好的缺點(diǎn)。[2018.05.09]

2018.05.11 update:
378. Kth Smallest Element in a Sorted Matrix
#56/145 solved#

1. Two Sum

除了雙重遍歷外兆览，可以用hash的方式空間換時(shí)間屈溉，遍歷過程中依次存放每個(gè)元素的值及其下標(biāo)，如果當(dāng)前元素的互補(bǔ)數(shù)(target-nums[i])在哈希表中存在則可得結(jié)果抬探。

7. Reverse Integer

反轉(zhuǎn)32位整數(shù)子巾，需要考慮溢出問題。
原本用了long long來判斷溢出小压，但后來發(fā)現(xiàn)有個(gè)家伙用溢出后的數(shù)做逆操作與上次結(jié)果比較不同來判斷线梗，十分有才，判斷方式：
if ((aux_ret - x % 10) / 10 != ret) return 0;

13. Roman to Integer

羅馬數(shù)字的規(guī)則對(duì)左減數(shù)字有限制（僅限于I/X/C且不能跨位相減）怠益，但右加數(shù)字沒有仪搔，因此逆序做轉(zhuǎn)換是AC的但順序轉(zhuǎn)換會(huì)WA(eg:MCMXCVI-1996)。

14. Longest Common Prefix

求一組字符串的最長(zhǎng)相同前綴（LCP）蜻牢，個(gè)人給出兩種解決方案烤咧，一種是橫向地順序遍歷每個(gè)字符串與之前得到的LCP計(jì)算新的LCP，這種思想可以劃分到動(dòng)態(tài)規(guī)劃中抢呆；另外一種方法是考慮整體類似于一個(gè)不完全的字符矩陣煮嫌，那么我們可以縱向地從第一列開始逐列對(duì)比，全部相同就把該字符加到LCP中抱虐，不同就可以返回LCP了昌阿。
此外LeetCode還給出了分治法和二分查找法的解決方案，思想也很簡(jiǎn)單恳邀，但是不如前面兩種方法簡(jiǎn)潔也沒有明顯優(yōu)勢(shì)懦冰，因此了解即可。

20. Valid Parentheses

學(xué)過編譯原理的應(yīng)該都知道怎么做谣沸，可以利用棧來進(jìn)行括號(hào)匹配儿奶，有無法匹配的括號(hào)那么說明語(yǔ)法錯(cuò)誤。

21. Merge Two Sorted Lists

第一種迭代方案是在需要合并時(shí)交換當(dāng)前節(jié)點(diǎn)和比較節(jié)點(diǎn)鳄抒，也是自己第一時(shí)間想到的做法云石；
第二種迭代方案是按大小順序依次合并兩個(gè)鏈表的每個(gè)節(jié)點(diǎn)到新鏈表；
第三種是遞歸的做法棒口，從第一個(gè)節(jié)點(diǎn)開始依次合并每個(gè)最小節(jié)點(diǎn)，注意此方法不是尾遞歸秉版，不適用于過長(zhǎng)鏈表合并，可能會(huì)導(dǎo)致棧溢出茬祷，但該題目目前的測(cè)試用例規(guī)模還沒有到臨界點(diǎn)清焕，可以AC。

22. Generate Parentheses

窮舉n對(duì)圓括號(hào)可以構(gòu)成的所有合法字符序列祭犯。
第一個(gè)想到的方法是把每個(gè)合法字符串作為一行形成一個(gè)矩陣縱向遍歷秸妥，每次添加一個(gè)括號(hào)，對(duì)于每行的字符串沃粗，如果下一個(gè)可能添加的括號(hào)有兩種選擇粥惧，則拷貝其一到矩陣最后一行；
第二個(gè)方法是遞歸回溯最盅，可以把回溯過程看做一棵二叉樹突雪，每次遞歸調(diào)用會(huì)拷貝一次當(dāng)前字符串然后判斷下次添加的括號(hào)可能性（分支），直到n對(duì)括號(hào)全部添加完成后（葉子節(jié)點(diǎn)）把當(dāng)前字符串加入結(jié)果集涡贱；
第三個(gè)方法LeetCode上稱之為Closure number但我覺得像是分治法（還是DP咏删？），這個(gè)方法比較trickier问词，LeetCode上的解釋也沒太明白督函，這里就說一下個(gè)人理解，我們可以把一個(gè)合法的括號(hào)字符串看做一個(gè)閉包激挪，它必然起于左括號(hào)止于右括號(hào)侨核，且每個(gè)合法括號(hào)串都可以從某個(gè)位置分為兩個(gè)同樣合法的括號(hào)串（包括空串），因此對(duì)于給定的n所可能構(gòu)造的所有括號(hào)串都可以一步步劃分為兩個(gè)子閉包并解構(gòu)（去掉頭尾的一對(duì)左右括號(hào)）直到最小閉包——空串為止灌灾。基于以上分析悲柱，我們就可以從空串開始逆向一步步對(duì)兩個(gè)子閉包之一構(gòu)造新的閉包（在頭尾各添加一個(gè)左/右括號(hào)）然后合并锋喜，至于構(gòu)造對(duì)象是誰都是可以的，也就是代碼中的核心部分：

ret.push_back(left + '(' + right + ')');// 以right閉包為構(gòu)造對(duì)象
//ret.push_back('(' + left + ')' + right);// 或以left閉包為構(gòu)造對(duì)象

26. Remove Duplicates from Sorted Array

一開始題意理解錯(cuò)誤了..題目要求是在O(1)復(fù)雜度的前提下得到輸入排序數(shù)組去重后的結(jié)果豌鸡，注意要用輸入數(shù)組保存去重后的數(shù)組嘿般，輸出的長(zhǎng)度是去重后數(shù)組的長(zhǎng)度。順便一提in-place算法一般多采用替代或者交換的方式來實(shí)現(xiàn)涯冠，我的解法是遍歷整個(gè)數(shù)組依次把第n個(gè)不重復(fù)的元素替換數(shù)組下標(biāo)為n-1的元素得到最終結(jié)果炉奴。

28. Implement strStr()

字符串匹配函數(shù)的實(shí)現(xiàn)，逐字匹配過于低效蛇更，用hash方式空間換時(shí)間瞻赶。
也可以用KMP算法來實(shí)現(xiàn)赛糟，其本質(zhì)是對(duì)于模式串中前后綴相同的子串減少匹配次數(shù)，回頭實(shí)現(xiàn)了之后補(bǔ)充源碼再梳理一下KMP的原理砸逊。

38. Count and Say

根據(jù)上一次的字符串計(jì)算下次的結(jié)果璧南，迭代法，維持一個(gè)相同數(shù)字計(jì)數(shù)器师逸，當(dāng)遇到不同數(shù)字或者字符串結(jié)尾時(shí)把這個(gè)數(shù)字和計(jì)數(shù)器的值附加到新字符串后面司倚。

46. Permutations

給定一個(gè)無重復(fù)整數(shù)數(shù)組，窮舉其所有排列篓像。

1. 遞歸回溯
   思路比較清晰动知，每次定位一個(gè)數(shù)字，鎖上這個(gè)數(shù)字在的位置（剩余數(shù)字不可以排在這里）员辩，每次上鎖后記錄偏移量（這個(gè)數(shù)字的位置）盒粮，然后排列剩下的數(shù)字，完成后根據(jù)偏移量插入之前定位的數(shù)字屈暗。當(dāng)只剩一個(gè)數(shù)字未確定時(shí)（只有一種排列）開始層層回溯直到最終結(jié)果拆讯。
   關(guān)鍵之處在于鎖和偏移量的更改要想清楚才能保證回溯不會(huì)出錯(cuò)。
2. 動(dòng)態(tài)規(guī)劃
   與方法1異途同歸养叛，對(duì)于上一次獲取到的所有排列种呐，插入新的元素，新形成的排列數(shù)量為原排列數(shù)量乘以i（即階乘i!）弃甥，其狀態(tài)轉(zhuǎn)移方程如下：

dp[i][j] = dp[i - 1][j / (i + 1)].insert(dp[i - 1][j / (i + 1)].begin() + j % (i + 1), nums[count - i - 1]);

• 其中dp[i]表示新的排列集合爽室，dp[i-1]表示上一次的排列集合，代碼實(shí)現(xiàn)時(shí)分別用dp_next和dp_prev表示淆攻，j/(i+1)是選擇插入對(duì)象阔墩，因?yàn)閷?duì)一個(gè)排列插入新元素共有i+1種可能性，j%(i+1)是插入新元素的偏移量瓶珊。

3. 做完之后看了下discuss啸箫，發(fā)現(xiàn)自己沒有很好地利用"distinct"這個(gè)條件，貌似還有個(gè)Permutations II是允許包含重復(fù)元素的輸入來著伞芹，emmm忘苛，但是不覺得利用distinct的解法更好因此沒有再寫一個(gè)針對(duì)它的實(shí)現(xiàn)。

53. Maximum Subarray

從左到右遍歷數(shù)組求和：
1.如果第i個(gè)元素前的和小于0唱较，那么從該元素重新開始求和（否則不是加上前面的和反倒又變小了么扎唾，以防越過最大子數(shù)組左界）；
2.如果本次求和的結(jié)果大于上次保存的最大子數(shù)組和南缓，則更新后者為當(dāng)前求和結(jié)果（防止越過最大子數(shù)組右界的情況）胸遇。
這是O(n)的解決方案，不過我一開始并沒有意識(shí)到這個(gè)方法本質(zhì)上其實(shí)是動(dòng)態(tài)規(guī)劃汉形，根據(jù)動(dòng)態(tài)規(guī)劃的思想重新解釋的話纸镊，步驟(1.)就是其狀態(tài)轉(zhuǎn)移方程

sum(vec,i) = vec[i] + (sum(vec,i-1) > 0 ? sum(vec,i-1) : 0)

而這只能不斷更新確定子數(shù)組左界倍阐，有可能會(huì)越過右界，這時(shí)結(jié)果是不可靠的薄腻，例如[1,1,-3,0]這種情況收捣，其最大子數(shù)組為[1,1]，但當(dāng)遍歷到-3時(shí)庵楷，sum[i-1]=2而vec[i]=-3罢艾，導(dǎo)致sum[i]=-1，越過右界vec[1]=1尽纽，因此需要步驟(2.)來防止這種情況的發(fā)生咐蚯，即對(duì)比上次求和結(jié)果與本次求和結(jié)果，如果變小了弄贿，那么有可能越過右界春锋，不取其值。
and WHY using divide and conquer approach 差凹？我并不認(rèn)為分治法更subtle期奔，不但麻煩且效率低。

66. Plus One

比較簡(jiǎn)單危尿，模擬加法進(jìn)位而且是特化的只+1版本呐萌，需要注意處理最高位進(jìn)位的情況。

69. Sqrt(x)

求平方根谊娇，可以用二分法求也可以用牛頓法求肺孤。二分法不提，牛頓迭代法注意退出條件和整形溢出济欢，另外整形相除的精度損失在計(jì)算順序不同的情況下可能導(dǎo)致WA：

牛頓迭代法公式：x_n+1=x_n+f'(x_n)/f(x_n);

ret = (ret + x / ret) / 2;// AC 減少除法造成的精度損失
ret = ret / 2 + x / (ret * 2);// WA

70. Climbing Stairs

到達(dá)第n級(jí)臺(tái)階的方式有兩種：從n-1階跨1階或從n-2階跨2階赠堵，因此dp[n]=dp[n-1]+dp[n-2]》ㄈ欤可以用動(dòng)態(tài)規(guī)劃做也可以作為斐波那契數(shù)列做茫叭，但是暴力遞歸會(huì)導(dǎo)致TLE。

88. Merge Sorted Array

給定兩個(gè)有序數(shù)組nums1和nums2半等，合并nums1的前m個(gè)和nums2的前n個(gè)元素到nums1中揍愁，nums1的長(zhǎng)度不小于m+n（注意此處：需要抹除合并后多于m+n的部分，因?yàn)檩敵龅慕Y(jié)果是nums1）酱鸭。
個(gè)人有兩種解法，第一種直接把nums2插入到nums1的第m個(gè)元素后面垛吗，擦除多余部分然后對(duì)nums1排序可得結(jié)果凹髓；第二種遍歷nums1的前m個(gè)和nums2的前n個(gè)元素，對(duì)比大小按順序插入到nums1中然后擦除多余部分怯屉，需要注意的是nums1的合法長(zhǎng)度會(huì)隨插入新元素?cái)?shù)量增長(zhǎng)（即循環(huán)條件之一應(yīng)為i1<m+i2）蔚舀，若nums2有剩下的元素（說明m=0或剩下元素都大于nums1[m-1]）則直接插入到nums1中饵沧。
討論區(qū)有另外一種解法倒序遍歷，是第二種的逆向思維赌躺，不用考慮i1<m+i2這個(gè)細(xì)節(jié)狼牺，只要nums2中的n個(gè)合法元素均已按正確的順序替換到nums1中即可得到正確結(jié)果（剩余的nums1合法元素本來就是有序的）。核心代碼：

while (i2 > -1) nums1[i--] = i1 > -1 && nums1[i1] > nums2[i2] ? nums1[i1--] : nums2[i2--];

94. Binary Tree Inorder Traversal

二叉樹中序遍歷礼患，遞歸方法自然是第一選擇是钥，但是要求使用迭代且空間復(fù)雜度為O(1)，那么可以選擇莫里斯遍歷(Morris Traversal)：
二叉樹遍歷的主要問題在于當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)時(shí)如何返回對(duì)應(yīng)的父節(jié)點(diǎn)缅叠，而該方法的解決方法是通過額外的時(shí)間消耗和一個(gè)輔助指針悄泥，來將父節(jié)點(diǎn)對(duì)應(yīng)的需要返回到它的葉子節(jié)點(diǎn)的空右子節(jié)點(diǎn)指針指向它（相當(dāng)于構(gòu)造了一個(gè)環(huán)），這樣肤粱，當(dāng)遍歷到葉子節(jié)點(diǎn)需要返回時(shí)便可以通過該指針回到父節(jié)點(diǎn)繼續(xù)下一步操作弹囚。
核心步驟如下：

• 判斷當(dāng)前節(jié)點(diǎn)是否有左子樹，如果沒有领曼，那么獲取當(dāng)前節(jié)點(diǎn)值（中序遍歷）鸥鹉；
• 如果有左子樹，那么把輔助指針指向左子樹庶骄，并循環(huán)右移直到葉子節(jié)點(diǎn)毁渗；
  • 如果葉子節(jié)點(diǎn)為空（開始構(gòu)造環(huán)），那么把葉子節(jié)點(diǎn)的右節(jié)點(diǎn)指針指向當(dāng)前節(jié)點(diǎn)（需要返回的父節(jié)點(diǎn)）瓢姻，構(gòu)造一個(gè)環(huán)祝蝠，然后當(dāng)前節(jié)點(diǎn)左移到左子樹根節(jié)點(diǎn)（開始遍歷左子樹）；
  • 如果葉子節(jié)點(diǎn)右節(jié)點(diǎn)指針指向當(dāng)前節(jié)點(diǎn)（已構(gòu)造環(huán)→左子樹已遍歷完畢）幻碱，那么重新把其右節(jié)點(diǎn)指針置空（恢復(fù)原樹結(jié)構(gòu)）绎狭，獲取當(dāng)前節(jié)點(diǎn)值，然后把當(dāng)前節(jié)點(diǎn)移到右子樹（開始遍歷右子樹）褥傍。

101. Symmetric Tree

判斷一個(gè)二叉樹是否左右對(duì)稱儡嘶，問題可以轉(zhuǎn)換為判斷根節(jié)點(diǎn)的兩個(gè)子樹是否鏡像對(duì)稱，其特點(diǎn)是結(jié)點(diǎn)值相同恍风，且左子樹的左子樹與右子樹的右子樹鏡像對(duì)稱蹦狂、左子樹的右子樹與右子樹的左子樹鏡像對(duì)稱。
據(jù)此思想朋贬，遞歸的實(shí)現(xiàn)容易想到凯楔，迭代的做法我直接模擬了函數(shù)調(diào)用棧的方式來實(shí)現(xiàn)。

104. Maximum Depth of Binary Tree

二叉樹深度優(yōu)先遍歷锦募。

108. Convert Sorted Array to Binary Search Tree

對(duì)已排序數(shù)組建立平衡二叉樹摆屯，遞歸思想，數(shù)據(jù)結(jié)構(gòu)了解一下糠亩。

118. Pascal's Triangle

楊輝三角虐骑，就算沒有了解的人也很容易發(fā)現(xiàn)其規(guī)律准验，每層左右邊界均為1，其他數(shù)字為上一層對(duì)應(yīng)兩個(gè)數(shù)字之和廷没。其實(shí)也是個(gè)動(dòng)態(tài)規(guī)劃問題糊饱，作為數(shù)組來歸納其狀態(tài)轉(zhuǎn)移方程就是

triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]

121. Best Time to Buy and Sell Stock

維持一個(gè)最小買入價(jià)格和當(dāng)前賣出利潤(rùn)來計(jì)算最大利潤(rùn)。注意此題不可以用雙層循環(huán)颠黎，會(huì)導(dǎo)致TLE另锋。

122. Best Time to Buy and Sell Stock II

只有一股股票，在知曉給定天數(shù)每天價(jià)格的前提下獲取最大利潤(rùn)盏缤，可以將其買賣多次但因?yàn)橹挥幸还伤圆豢梢再I入復(fù)數(shù)股再賣掉砰蠢。說實(shí)話感覺這題沒什么意思，還不如13題的羅馬數(shù)字轉(zhuǎn)換唉铜。

125. Valid Palindrome

判斷回文字符串台舱，但是要求大小寫不敏感并且只關(guān)心字母和數(shù)字，邏輯比較清晰潭流，只判斷在a_z|AZ|0~9間的字符并把小寫字符轉(zhuǎn)換為大寫字符即可竞惋。實(shí)現(xiàn)沒有用庫(kù)函數(shù)，用庫(kù)函數(shù)判斷是否阿爾法字符和進(jìn)行大小寫轉(zhuǎn)換比較簡(jiǎn)單清晰一些灰嫉。

136. Single Number

異或的用法很亮眼拆宛，坦白地說我沒想起來，很慚愧讼撒，位運(yùn)算用到的比較少浑厚。
對(duì)本題來說，因?yàn)?strong>異或運(yùn)算是滿足交換律的根盒，因此所有出現(xiàn)兩次的數(shù)字最終異或結(jié)果為0钳幅，可以得出唯一一個(gè)僅出現(xiàn)一次的single number。

141. Linked List Cycle

判斷一個(gè)鏈表是否有環(huán)：
如果有環(huán)炎滞，那么必然有一個(gè)節(jié)點(diǎn)指向前面的某個(gè)節(jié)點(diǎn)敢艰，基于此想法可以用hash解決，但空間復(fù)雜度是O(n)册赛；
另外一種很妙的方案钠导，是類比兩個(gè)人在閉環(huán)跑道跑步，如果兩人速度不同則必然會(huì)相遇森瘪，相似地牡属，維持兩個(gè)指針，一個(gè)每次“跑兩步”(fast=fast->next->next)扼睬，另一個(gè)每次“跑一步”(slow=slow->next)逮栅。如此當(dāng)有環(huán)時(shí)兩個(gè)指針必然會(huì)有重疊的情況，無環(huán)時(shí)指針最終會(huì)到達(dá)“終點(diǎn)”(null)，退出循環(huán)证芭。

149. Max Points on a Line

這道題還是比較麻煩的（在LeetCode上AC率15.2%倒數(shù)第三），一開始的基本思路是先獲取所有構(gòu)成的不重復(fù)直線担映，然后對(duì)每條直線遍歷所有的點(diǎn)計(jì)算線上點(diǎn)數(shù)废士，但這樣有三個(gè)問題，一是“不重復(fù)”的處理是很笨重蝇完，二是要處理大數(shù)相乘可能導(dǎo)致的int溢出官硝，三是要處理int除法的精度損失。
后來選擇了另一種處理方式短蜕，忽略問題一避免問題二氢架，著重處理問題三，核心思想是對(duì)于一個(gè)已確定的點(diǎn)朋魔，只要其他的點(diǎn)與該點(diǎn)構(gòu)成直線的斜率相同岖研，那么便都在同一直線上（直線的點(diǎn)斜式思想）。步驟如下：

1. 先選擇一個(gè)錨點(diǎn)警检，建立一個(gè)std::map孙援，鍵為斜率，值為以該斜率和錨點(diǎn)確定的直線上點(diǎn)的數(shù)量扇雕；
2. 然后遍歷其他的點(diǎn)計(jì)算與錨點(diǎn)的斜率拓售，斜率要用到除法，為了防止精度損失镶奉，這里采用先約分然后std::pair<int,int>存儲(chǔ)約分后除數(shù)和被除數(shù)的方式來轉(zhuǎn)換础淤，但需要注意兩種特殊情況：
   sp1. 對(duì)于重復(fù)點(diǎn)（錨點(diǎn)本身也算是一個(gè)重復(fù)的點(diǎn)）的數(shù)量進(jìn)行累加，暫稱重復(fù)數(shù)量哨苛；
   sp2. 對(duì)于斜率不存在的情況鸽凶，通過std::pair的一對(duì)int均置為0來區(qū)分為單獨(dú)一組（除數(shù)不可能為0）；
3. 遍歷完畢后獲取該錨點(diǎn)的map value最大值移国，并加上重復(fù)數(shù)量吱瘩，得到本輪的同一直線上最多點(diǎn)的數(shù)量，然后與上一輪的值比較取大者迹缀，回步驟1重復(fù)直到錨點(diǎn)遍歷完畢即可得到結(jié)果使碾。

155. Min Stack

實(shí)現(xiàn)一個(gè)可以獲取最小值的棧，要求壓出棧祝懂、獲取棧頂和最小元素的操作時(shí)間復(fù)雜度都是O(1)票摇。
因?yàn)槭菞＃猿鰲Ｔ氐捻樞蚴枪潭ǖ模ㄏ热牒蟪觯┭馀睿敲纯梢跃S持一個(gè)容器保存棧中最小值更新的記錄矢门，我這里用了一個(gè)數(shù)組，如果壓/出棧時(shí)最小值更新了，那么把更新的最小值放入/取出數(shù)組祟剔，這樣無論何時(shí)該數(shù)組的最后一個(gè)元素都是當(dāng)前最小值隔躲。關(guān)鍵代碼：

if (mins_.empty() || x <= mins_.back()) mins_.push_back(x);// 壓棧時(shí)的判斷
if (values_.back() == mins_.back()) mins_.pop_back();// 出棧時(shí)的判斷

160. Intersection of Two Linked Lists

emmm這道題...我想到了雙指針“跑步”但是跑偏了→_→
要求找出兩個(gè)無環(huán)單鏈表的交叉點(diǎn)，時(shí)間復(fù)雜度O(n)物延，空間復(fù)雜度O(1)宣旱，不能改變?cè)湵斫Y(jié)構(gòu)。假如把兩個(gè)鏈表拼接起來叛薯，那么如果有交叉點(diǎn)則必然在同一時(shí)間達(dá)到這個(gè)交叉點(diǎn)浑吟，如下圖所示：

two pointers

169. Majority Element

主要元素的數(shù)量多于一半的情況下意味著最多數(shù)量者即為解，且不同元素的數(shù)量必然少于相同元素?cái)?shù)量耗溜。

171. Excel Sheet Column Number

可能是我英文水平不夠组力，讀了好幾遍才理解這題意思，事實(shí)上就是完成26進(jìn)制到10進(jìn)制的轉(zhuǎn)換抖拴。

172. Factorial Trailing Zeroes

這道題有點(diǎn)像腦筋急轉(zhuǎn)彎...燎字？好吧是我數(shù)字敏感性不夠#_#
題目是求出n!結(jié)果中數(shù)位0的個(gè)數(shù)，但要求時(shí)間復(fù)雜度為對(duì)數(shù)階阿宅。其中原理是結(jié)果中的每個(gè)0都必然來自于x10轩触，而10可以分解為2x5，由于因數(shù)2的數(shù)量多于因數(shù)5家夺，因此我們只需要統(tǒng)計(jì)出n脱柱！的因數(shù)中5的數(shù)量即為結(jié)果中數(shù)位0的數(shù)量，至于求因數(shù)5的數(shù)量可以使n對(duì)5輾轉(zhuǎn)相除拉馋，累加每次相除的結(jié)果（e.g. 26/5=5,5/5=1,5+1=6榨为，26的階乘可以分解出6個(gè)因數(shù)5，則其階乘結(jié)果中含6個(gè)0數(shù)位）：while ((n /= 5) > 0) sum += n;

189. Rotate Array

獲取數(shù)組循環(huán)右移n步的結(jié)果煌茴。
根據(jù)右移步數(shù)和數(shù)組長(zhǎng)度可以知道每個(gè)數(shù)組元素的最終位置随闺，通過右移步數(shù)對(duì)數(shù)組長(zhǎng)度求余，得到原本數(shù)組尾部移動(dòng)到數(shù)組頭部的元素?cái)?shù)量蔓腐，然后把這些元素插入頭部再清除尾部多余元素矩乐。

190. Reverse Bits

位運(yùn)算題，每次完成1bit的位置反轉(zhuǎn)共32bit回论，要先想清楚運(yùn)算邏輯散罕。

191. Number of 1 Bits

位運(yùn)算題，因?yàn)槭乔蠖M(jìn)制位為1的數(shù)量傀蓉，因此把n循環(huán)右移并與1做與(&)運(yùn)算直到n為0即可（右移高位補(bǔ)0欧漱，為0時(shí)說明剩下的二進(jìn)制位中已經(jīng)沒有1了）。

198. House Robber

最先想到的還是遞歸葬燎，不過提交之后會(huì)TLE误甚，沒辦法還是寫迭代吧缚甩，為了不超時(shí)，又是一個(gè)動(dòng)態(tài)規(guī)劃的做法窑邦。
因?yàn)椴荒軗尳賰蓷澫噜彿课萆猛虼藫尳俚降趎棟房屋時(shí)的最大收獲要么是前面n-1棟的最大收獲，要么是前面n-2棟的最大收獲加上第n棟的收獲冈钦，狀態(tài)轉(zhuǎn)移方程：

dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2])

202. Happy Number

對(duì)各數(shù)位的平方循環(huán)求和裕寨，如果結(jié)果為1返回true，結(jié)果發(fā)生了循環(huán)返回false(哈希確認(rèn))派继，否則繼續(xù)下一次數(shù)位平方求和。

204. Count Primes

求小于n的素?cái)?shù)數(shù)量捻艳，篩法實(shí)現(xiàn)驾窟，假設(shè)所有(1,n)內(nèi)的所有自然數(shù)都是素?cái)?shù)，從2開始认轨，如果是素?cái)?shù)那么它的所有倍數(shù)都是非素?cái)?shù)绅络，遍歷完成后可以篩出所有素?cái)?shù)。

206. Reverse Linked List

單鏈表反轉(zhuǎn)的迭代和遞歸實(shí)現(xiàn)嘁字。

217. Contains Duplicate

哈隙骷保或者set集合。

234. Palindrome Linked List

判斷單鏈表是否回文纪蜒≈怨В考慮O(n)時(shí)間復(fù)雜度和O(1)空間復(fù)雜度，因?yàn)榛匚逆湵淼暮蟀氩糠直厝皇乔鞍氩糠值姆崔D(zhuǎn)纯续，有以下解決方案：

1. 先通過雙指針方式取得鏈表的后半部分([1,2,3,2,1]->[2,1],[1,2,2,1]->[2,1]);
2. 反轉(zhuǎn)后半部分随珠，然后同時(shí)遍歷鏈表前半部分和反轉(zhuǎn)的后半部分，如果全部匹配那么就是回文鏈表猬错。

237. Delete Node in a Linked List

這道題很容易窗看，把指向當(dāng)前節(jié)點(diǎn)的指針指向下一節(jié)點(diǎn)即可，但是需要注意不要忘記內(nèi)存管理倦炒，記得釋放显沈。

238. Product of Array Except Self

給定數(shù)組nums，對(duì)于其中的每一個(gè)元素nums[i]逢唤，求出除nums[i]之外所有元素的乘積拉讯。
簡(jiǎn)單來說，返回?cái)?shù)組ret中:

ret[i] = nums[0]*nums[1]*...*nums[i-1]*nums[i+1]*...*nums[n-1];
ret[i] = (nums[0]*nums[1]*...*nums[i-1])  *  (nums[i+1]*...*nums[n-1]);
ret[i] = 1 * (nums[0]*nums[1]*...*nums[i-1])  *  (nums[i+1]*...*nums[n-1]);// 1*front*back

可以把前面和后面的部分分別視為兩個(gè)因子front和back鳖藕，遍歷nums[i]遂唧，分別從頭/尾部迭代計(jì)算front/back，并分別在頭/尾部與對(duì)應(yīng)的ret[i]/ret[n-1-i]相乘吊奢，遍歷完成后即得結(jié)果盖彭。

242. Valid Anagram

兩種方法：排序后比較或哈希思想纹烹。

268. Missing Number

要滿足時(shí)間復(fù)雜度O(n)和空間復(fù)雜度O(1)，第一時(shí)間想起來的是求n個(gè)數(shù)的和然后減去實(shí)際和的方式（高斯公式）召边，另外LeetCode上還有一種解法是用異或也很棒铺呵，再次用到了異或的交換律。

283. Move Zeroes

可以順序遍歷隧熙，把第n個(gè)發(fā)現(xiàn)的非零數(shù)與第n個(gè)數(shù)(0)交換片挂，也可以逆序遍歷，把第n個(gè)發(fā)現(xiàn)的0與第n個(gè)非零數(shù)交換贞盯，為了減少交換次數(shù)音念，可以在遍歷次數(shù)等于n時(shí)不做交換。

326. Power of Three

一種迭代求解躏敢，一種換底公式闷愤，注意要以10為底，否則會(huì)有精度問題件余。LeetCode給出還有另外兩種解法讥脐，進(jìn)制轉(zhuǎn)換和用滿足條件的最大int對(duì)n求余。
這道題沒什么意義啼器，踩旬渠。

344.Reverse String

回字的四種寫法。

347. Top K Frequent Elements

獲取給定集合中出現(xiàn)頻率最高的k個(gè)元素端壳，要求時(shí)間復(fù)雜度低于O(nlogn)告丢，很經(jīng)典的題目。

• 首先要統(tǒng)計(jì)集合中所有元素的出現(xiàn)頻率损谦，哈希表是第一選擇芋齿；
• 其次要根據(jù)頻率進(jìn)行排序，且不能丟掉與頻率關(guān)聯(lián)的元素值成翩，看到O(nlogn)的時(shí)間復(fù)雜度限制觅捆，可以知道普通的比較排序必然是不滿足要求的，因此可以選擇時(shí)間復(fù)雜度為O(n)的桶排序麻敌，也可以使用優(yōu)化過的原本為O(nlogn)時(shí)間復(fù)雜度的比較排序比如堆排序和快速排序栅炒，本題目我實(shí)現(xiàn)了包含桶排序、堆排序（最大堆术羔、最小堆）和快速排序的四種方案赢赊，堆排序的優(yōu)化在于減少堆元素?cái)?shù)量（O(nlogk)或O(nlog(n-k)），快速排序直接調(diào)用了C++ functional庫(kù)的nth_element级历，屬于部分快速排序释移。
  皆滿足題目要求，受益匪淺寥殖，之前還不曉得有個(gè)nth_element來著玩讳。
• 關(guān)于桶排序：由于桶本身是有序的涩蜘，因此桶排序不需要進(jìn)行比較，用可能大量冗余的空間換取了時(shí)間熏纯，這是它突破比較排序時(shí)間復(fù)雜度下線O(nlogn)的原因同诫。
• 關(guān)于堆排序：堆的本質(zhì)是一棵完全二叉樹，且具有每個(gè)節(jié)點(diǎn)必定大于（最大堆）/小于（最小堆）其子節(jié)點(diǎn)的性質(zhì)樟澜。std::priority_queue默認(rèn)是最大堆误窖，容器采用vector<T>，比較方法為less<T>秩贰，可以自定義比較方法（std提供的greater<T>可以用于最小堆）霹俺，堆排序建堆的時(shí)間復(fù)雜度為O(n)，而調(diào)堆的時(shí)間復(fù)雜度為O(logn)毒费，原因在于建堆是自底向上而調(diào)堆是自頂向下丙唧。
• 關(guān)于快速排序：快速排序的時(shí)間復(fù)雜度是不穩(wěn)定的，受到原元素順序的限制蝗罗，在隨機(jī)度較高的情況下它優(yōu)于堆排序，因?yàn)槎雅判虻膎是堆元素?cái)?shù)量遠(yuǎn)大于快速排序的n蝌戒，但惡化的快排（O(n²)）不如堆排串塑。

350. Intersection of Two Arrays II

寫了三種，哈希北苟、遍歷和排序桩匪，其中排序不適用于不改變交集元素出現(xiàn)順序的要求（For follow up）。
關(guān)于Follow up第三條友鼻，如果兩個(gè)數(shù)據(jù)量都是海量的傻昙，可以采取外排序方式然后對(duì)排序后的數(shù)組求交集（方法三）。

371. Sum of Two Integers

每次相加分為兩步彩扔，先計(jì)算無進(jìn)位再計(jì)算進(jìn)位妆档，用了遞歸思想，邏輯比較清晰虫碉，因?yàn)閎an掉了+-運(yùn)算符贾惦，所以很容易想起來如何用位運(yùn)算做。

378. Kth Smallest Element in a Sorted Matrix

給定一個(gè)橫向和縱向都遞增的n*n矩陣敦捧，找出其中第k小的元素须板。
實(shí)現(xiàn)了兩種方法，堆排和快排兢卵，其中快排沒有用std的算法權(quán)當(dāng)練手了习瑰，可以參照347題，那道題比這個(gè)復(fù)雜一些秽荤，我給出了較為詳細(xì)的解釋甜奄。
另外還有一種據(jù)說時(shí)間復(fù)雜度是O(n)的特化算法但是我沒仔細(xì)看柠横，后續(xù)有時(shí)間了再學(xué)習(xí)一下。

384. Shuffle an Array

這道題的意義在于去了解Fisher-Yates洗牌算法贺嫂。

Fisher-Yates原理：
對(duì)于給定的一個(gè)長(zhǎng)度為n原始序列滓鸠，每次（第i次，i>=0）隨機(jī)選擇原始序列前n-i個(gè)元素中的一個(gè)與第n-i個(gè)元素交換位置第喳，即從后往前每次確定一個(gè)元素糜俗，直到全部確定完成shuffle。
只要隨機(jī)選擇元素的時(shí)候是真隨機(jī)曲饱，那么shuffle結(jié)果也是真隨機(jī)的悠抹。

387. First Unique Character in a String

可以想到兩種方案，一是哈希表保存字符計(jì)數(shù)信息扩淀，然后獲得單字符index楔敌，二是兩次遍歷查找是否重復(fù)。

412. Fizz Buzz

vector初始化以便使用下標(biāo)驻谆。

454. 4Sum II

暴力求解的時(shí)間復(fù)雜度過高O(n⁴)卵凑，可以二分法解決，4個(gè)數(shù)組兩兩一組求和然后判斷是否互補(bǔ)即可胜臊，復(fù)雜度為O(n²)勺卢。