前言
為什么要用 Swift 刷 leetcode？因?yàn)槲矣袃蓚€(gè)想法，一是學(xué) Swift 并且有機(jī)會練練，二是想把 leetcode 刷完。于是，這兩個(gè)想法就合二為一了，現(xiàn)在我以基本一天一道的速度在刷。
Swift 適合用來刷 leetcode 嗎？現(xiàn)在做了20多道題，我個(gè)人的意見是不適合。可能比純 C 好寫，但沒有主流的語言 java、python 好寫。
首先 Swift 這門語言效率不高，有些算法拿別的語言過得去，拿 Swift 就會超時(shí)（雖然是跟 case 有關(guān)系，不過 Swift 效率確實(shí)不高）。其次，Swift 有很多麻煩的地方，尤其是字符串處理上。它甚至都不能隨機(jī)訪問字符串里某個(gè)位置的字符……還得先轉(zhuǎn)成一個(gè)字符數(shù)組，也就意味著凡是有字符串的題的時(shí)間和空間復(fù)雜度都不會小于 O(n) 了。還有一些字符串相關(guān)的 API 會影響效率，如果想讓代碼簡潔就會超時(shí)…… 總之感覺如果是練習(xí)算法，不用考慮這些因素是最好的，從這個(gè)角度來說，Swift 并不是最適合刷 leet code 的語言。但當(dāng)然也是可行的，如果你有興趣，一起來刷吧。
我把我的解法放在了我的 Github上，逐漸更新。另外，Github 上還有一個(gè)非常全的題解，我也為它貢獻(xiàn)了一點(diǎn)點(diǎn)代碼。
每道題的筆記
以下是 1-20 題我寫的簡單題解，卡住的時(shí)候可以來看看：
Two Sum (Easy) 題解
很簡單的 hash。一個(gè)小技巧是，對于每個(gè)數(shù)先看和為 target 所需的數(shù)是否已經(jīng)在 dict 里，如果已經(jīng)在則直接返回，否則才把自身放進(jìn) dict 里。這樣只需循環(huán)一次，不用先構(gòu)建 hash、再遍歷，循環(huán)兩次。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)Add Two Numbers (Medium) 題解
簡單的單鏈表處理?？紤]幾種情況：1. 兩個(gè)數(shù)位數(shù)相等，且最高位不需進(jìn)位 2. 兩個(gè)數(shù)位數(shù)相等，且最高位需要進(jìn)位 3. 兩個(gè)數(shù)位數(shù)不相等。
有些人寫的時(shí)候會在結(jié)果的頭部先創(chuàng)建一個(gè)dummy，val任意，真正的頭結(jié)點(diǎn)直接往dummy后面插。最后返回dummy -> next。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(1)Longest Substring Without Repeating Characters (Medium) 題解
我用的方法是用一個(gè) hash 記錄每個(gè)字母出現(xiàn)的index，然后把字符串掃一遍。不出現(xiàn)重復(fù)時(shí)就往 hash 表里填。出現(xiàn)重復(fù)時(shí)，從 hash 取出字母出現(xiàn)的previousIndex，把從當(dāng)前串開頭至previousIndex的字母都從 hash 中清掉。
看到一個(gè)更好的方法，不需要存字母出現(xiàn)的index，出現(xiàn)重復(fù)時(shí)直接從當(dāng)前串開頭至出現(xiàn)重復(fù)字母的位置清掉 hash 即可。這種情況下也不需要用Dictionary存 hash，只需用Set即可。
本來 hash 需要的額外空間很小，但因?yàn)?swift 要遍歷字符串中的字符必須把字符數(shù)組存出來一份。所以空間復(fù)雜度為 O(n)。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)Median of Two Sorted Arrays (Hard) 題解
下面列出了兩個(gè)解法，其中 Solution2 是自己想出來的，也過了全部測試數(shù)據(jù)，但方法非常不簡潔。思路是從兩邊逼近中位數(shù)，取兩個(gè)數(shù)列的中點(diǎn)，可證明總有一個(gè)不能滿足第 k 大的條件。然后就調(diào)整這個(gè)數(shù)列。問題在于，有些情況可能會調(diào)整過頭。另外，還有這個(gè)數(shù)列已經(jīng)到頭、調(diào)整不了的情況，此時(shí)就需要去調(diào)另一個(gè)數(shù)列。總的來說仍然是 log(m + n) 的，但代碼非常長，原理也不夠清晰。
Solution1 參考了別人的題解，每次兩個(gè)數(shù)列各取 k/2 處，小者在這個(gè)位置之前全都截?cái)唷?br> 為啥 Solution1 就非常簡潔呢？最主要的問題在于，Solution1 是從一側(cè)逼近問題的，每次迭代都更靠近答案。Solution2 是從兩側(cè)往中間逼近，然而兩個(gè)數(shù)列并沒有二分查找那么好的特性，有可能兩個(gè)指針都在答案的同側(cè)，還要回頭找。
另外，Solution1 利用了一個(gè)技巧，保證每次迭代時(shí) nums1 都更短，不然交換。可以避免很多對稱的重復(fù)代碼。
在語言方面，可以看出 swift 里if(...) {return ...}這種基本都用guard代替。
時(shí)間復(fù)雜度：log(m+n) 空間復(fù)雜度：O(m+n)Longest palindromic Substring (Medium) 題解
這個(gè)解法是 O(n^2) 的。DP，先搜長度為 1、為 2…… 至 n。之所以寫法很不簡潔，多出了許多臨時(shí)變量，完全是 swift 的鍋。謹(jǐn)記 swift 字符串的特性，由于每一位字符長度不一定相等，它是不能隨機(jī)訪問的。也就是說，如果不存臨時(shí)變量，取某一位的字符、取字符串的長度、截取子串，全部都是 n 級別的…… 所以一再超時(shí)。
感覺很坑的是，我之前寫作isPalidromeMatrix[startIndex][endIndex] = ...這樣就會超時(shí)，而if (...) {isPalidromeMatrix[startIndex][endIndex] = true}這樣就不會。只不過多賦值了一些 false……
而且把if isPalidrome改成if isPalidromeMatrix[startIndex][endIndex]，時(shí)間會長一倍。感覺數(shù)據(jù)量稍微一大，swift 性能問題真的挺嚴(yán)重。
時(shí)間復(fù)雜度：O(n^2) 空間復(fù)雜度：O(n^2)
這個(gè)題是有一個(gè) O(n) 的算法的。首先有暴搜的思路，就是以任何一位為中心往外擴(kuò)展。O(n) 的算法是在這個(gè)基礎(chǔ)上，利用回文串的特性，存在一個(gè)子串那么中心點(diǎn)兩側(cè)對稱，在此基礎(chǔ)上再往外搜即可。具體可見這篇文章ZigZag Conversion (Easy) 題解
非常簡單的題，唯一的難點(diǎn)就是題目本身描述得不太清楚了。需要自己考慮 row = 1、2 的邊界情況。
swift 有個(gè)stride函數(shù)用來處理 for step 的情況。
**時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n) **Reverse Integer (Easy) 題解
這題本身很簡單，但感覺是道不錯(cuò)的面試題?？梢詼y試面試者是否考慮各種邊界情況，對溢出有沒有概念。
測試用例對 swift 給的不對，只能用Int32.max。我是把負(fù)數(shù)統(tǒng)一歸成正數(shù)來計(jì)算，這樣判斷溢出的語句可以簡單點(diǎn)。
時(shí)間復(fù)雜度：O(lgn) 空間復(fù)雜度：O(1)String to Integer (Easy) 題解
這道題與其說是寫代碼不如說是寫 case…… 一堆 case，真是一點(diǎn)懶都不能偷呀。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)Palindrome Number (Easy) 題解
很簡單的題，沒給出的條件是負(fù)數(shù)不算回文數(shù)。有個(gè) case 1000021 一開始做錯(cuò)了。另外一開始寫了個(gè)遞歸，后來發(fā)現(xiàn)沒必要……
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(1)-
Regular Expression Matching (Hard) 題解
評級為 hard，但感覺這題不難…… 就是遞歸一位一位往后讀，遇到 * 就分兩種情況，用盡這個(gè) token 或者下輪接著用這個(gè) token。
一個(gè)問題就是直接遞歸會超時(shí)。需要先把正則式處理一下：- aa 合并為 a*
- a.b* 合并為 .（就是 . 前后所有的 x* 全都去掉）。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)
Container With Most Water (Medium) 題解
本來想的是搜索加剪枝，搜以每個(gè)點(diǎn)做一端的。最壞情況 O(n^2)，結(jié)果最后有兩組數(shù)據(jù)（就是最壞情況）過不去，超時(shí)。
改成題解里這樣，從兩邊往中間搜，結(jié)果變成 O(n) 了。想改成記憶化搜索，發(fā)現(xiàn)很難。
搜索的順序果然還是非常重要！很多東西從后往前搜，從中間往兩邊搜，從兩邊往中間搜，就差得多了……
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(1)Integer to Roman (Medium) 題解
很簡單的遞歸，沒什么可說的。就是細(xì)心一點(diǎn)吧。
看到有的題解是把 1000、900、500 都存起來，這樣確實(shí)快很多，因?yàn)椴挥每紤]往左加的情況。另外非遞歸因?yàn)椴挥盟?10 次冪可能略快一點(diǎn)。
時(shí)間復(fù)雜度：O(lgn) 空間復(fù)雜度：O(1)Roman to Integer (Easy) 題解
很簡單的題，沒啥可說的。分情況討論，簡單遞歸即可（我怎么這么喜歡遞歸……）
看到一個(gè)題解的思路挺巧妙，倒著往前掃，比前一位大就往上加，沒前一位大就減掉。算是利用了羅馬數(shù)字一個(gè)很好的特性吧。
不過想了想好像沒啥倒過來的必要啊…… 直接從前往后掃也是一樣 O O
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)Longest Common Prefix (Easy) 題解
最簡單的字符串處理，沒什么可說的。
時(shí)間復(fù)雜度：O(nm) 空間復(fù)雜度：O(nm)3Sum (Medium) 題解
我用的還是 hash 方法，先找第一個(gè)數(shù)、再找第二個(gè)數(shù)…… 去重的方法就是要求三個(gè)數(shù)的序關(guān)系，這樣就不會重了。
看到一個(gè)題解用的是先排序，然后先定第一個(gè)數(shù)，第二個(gè)數(shù)左頭，第三個(gè)數(shù)右頭。然后大了挪小的、小了挪大的…… 這樣。算是另一種思路吧。
時(shí)間復(fù)雜度：O(n^2) 空間復(fù)雜度：O(n)3Sum Closest (Medium) 題解
這時(shí)候就用上上一題的排序思路了。先排好序，然后指定第一個(gè)數(shù)從左往右，第二個(gè)為第一個(gè)數(shù)右邊（剩下區(qū)間的最左端），第三個(gè)數(shù)為最右端。然后小了把左邊的往右挪、大了把右邊的往左挪……
時(shí)間復(fù)雜度：O(n^2) 空間復(fù)雜度：O(n)Letter Combinations of a Phone Number (Medium) 題解
懶癌犯了…… 明明一道廣搜的題，又寫成“遞歸”了，僅僅是因?yàn)閼械瞄_兩個(gè)數(shù)組…… 是不是已經(jīng)沒得救了 O O
好吧，后面老實(shí)補(bǔ)了一個(gè)正常版本。然后發(fā)現(xiàn)“遞歸”版本快得多…… 完全想不到任何原因呀，明明“遞歸”版本無謂地構(gòu)造了一些后綴字符串，難道是拷貝數(shù)組很慢？
時(shí)間復(fù)雜度：O(3^n) 空間復(fù)雜度：O(3^n)4Sum (Medium) 題解
在 3Sum 基礎(chǔ)上的延伸，先排序，再循環(huán)前兩位，后兩位左右夾逼。聽說這樣會超時(shí)？然而并沒有，時(shí)間還在中位數(shù)左右。500多ms
一些簡單的剪枝，比如夾逼時(shí)最小的兩個(gè)數(shù)都不夠小、最大的兩個(gè)數(shù)都不夠大，那也就沒必要繼續(xù)了。加了這些剪枝，雖然代碼長了很多很多，但是嗖快嗖快的，只要 52 ms。一下 beats 100% submissions，好有成就感呀。
時(shí)間復(fù)雜度：O(n^3) 空間復(fù)雜度：O(n)Remove Nth Node From End of List (Easy) 題解
挺簡單的題，沒什么可說的。只要兩個(gè)指針，第一個(gè)指向頭部，第二個(gè)指向第 n 個(gè)節(jié)點(diǎn)；然后把兩個(gè)指針同時(shí)往后挪，當(dāng)?shù)诙€(gè)指針到尾部時(shí)，第一個(gè)指針指向的就是就是倒數(shù)第 n 個(gè)節(jié)點(diǎn)，把它去了就行了。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)Valid Parentheses (Easy) 題解
大概是棧的最簡單的一道題了。如果是左括號，push；是右括號，pop，如果不匹配返回 false。結(jié)束后如果?？談t返回 true，否則返回 false。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)
