前言
为什么要用 Swift 刷 leetcode？因为我有两个想法，一是学 Swift 并且有机会练练，二是想把 leetcode 刷完。于是，这两个想法就合二为一了，现在我以基本一天一道的速度在刷。
Swift 适合用来刷 leetcode 吗？现在做了20多道题，我个人的意见是不适合。可能比纯 C 好写，但没有主流的语言 java、python 好写。
首先 Swift 这门语言效率不高，有些算法拿别的语言过得去，拿 Swift 就会超时（虽然是跟 case 有关系，不过 Swift 效率确实不高）。其次，Swift 有很多麻烦的地方，尤其是字符串处理上。它甚至都不能随机访问字符串里某个位置的字符……还得先转成一个字符数组，也就意味着凡是有字符串的题的时间和空间复杂度都不会小于 O(n) 了。还有一些字符串相关的 API 会影响效率，如果想让代码简洁就会超时…… 总之感觉如果是练习算法，不用考虑这些因素是最好的，从这个角度来说，Swift 并不是最适合刷 leet code 的语言。但当然也是可行的，如果你有兴趣，一起来刷吧。
我把我的解法放在了上，逐渐更新。另外，Github 上还有一个，我也为它贡献了一点点代码。
每道题的笔记
以下是 1-20 题我写的简单题解，卡住的时候可以来看看：
(Easy)
很简单的 hash。一个小技巧是，对于每个数先看和为 target 所需的数是否已经在 dict 里，如果已经在则直接返回，否则才把自身放进 dict 里。这样只需循环一次，不用先构建 hash、再遍历，循环两次。时间复杂度：O(n) 空间复杂度：O(n)(Medium)
简单的单链表处理。考虑几种情况：1. 两个数位数相等，且最高位不需进位 2. 两个数位数相等，且最高位需要进位 3. 两个数位数不相等。有些人写的时候会在结果的头部先创建一个dummy，val任意，真正的头结点直接往dummy后面插。最后返回dummy -> next。时间复杂度：O(n) 空间复杂度：O(1)(Medium)
我用的方法是用一个 hash 记录每个字母出现的index，然后把字符串扫一遍。不出现重复时就往 hash 表里填。出现重复时，从 hash 取出字母出现的previousIndex，把从当前串开头至previousIndex的字母都从 hash 中清掉。看到一个更好的方法，不需要存字母出现的index，出现重复时直接从当前串开头至出现重复字母的位置清掉 hash 即可。这种情况下也不需要用Dictionary存 hash，只需用Set即可。本来 hash 需要的额外空间很小，但因为 swift 要遍历字符串中的字符必须把字符数组存出来一份。所以空间复杂度为 O(n)。时间复杂度：O(n) 空间复杂度：O(n)(Hard)
下面列出了两个解法，其中 Solution2 是自己想出来的，也过了全部测试数据，但方法非常不简洁。思路是从两边逼近中位数，取两个数列的中点，可证明总有一个不能满足第 k 大的条件。然后就调整这个数列。问题在于，有些情况可能会调整过头。另外，还有这个数列已经到头、调整不了的情况，此时就需要去调另一个数列。总的来说仍然是 log(m + n) 的，但代码非常长，原理也不够清晰。Solution1 参考了别人的题解，每次两个数列各取 k/2 处，小者在这个位置之前全都截断。为啥 Solution1 就非常简洁呢？最主要的问题在于，Solution1 是从一侧逼近问题的，每次迭代都更靠近答案。Solution2 是从两侧往中间逼近，然而两个数列并没有二分查找那么好的特性，有可能两个指针都在答案的同侧，还要回头找。另外，Solution1 利用了一个技巧，保证每次迭代时 nums1 都更短，不然交换。可以避免很多对称的重复代码。在语言方面，可以看出 swift 里if(...) {return ...}这种基本都用guard代替。时间复杂度：log(m+n) 空间复杂度：O(m+n)(Medium)
这个解法是 O(n^2) 的。DP，先搜长度为 1、为 2…… 至 n。之所以写法很不简洁，多出了许多临时变量，完全是 swift 的锅。谨记 swift 字符串的特性，由于每一位字符长度不一定相等，它是不能随机访问的。也就是说，如果不存临时变量，取某一位的字符、取字符串的长度、截取子串，全部都是 n 级别的…… 所以一再超时。感觉很坑的是，我之前写作isPalidromeMatrix[startIndex][endIndex] = ...这样就会超时，而if (...) {isPalidromeMatrix[startIndex][endIndex] = true}这样就不会。只不过多赋值了一些 false……而且把if isPalidrome改成if isPalidromeMatrix[startIndex][endIndex]，时间会长一倍。感觉数据量稍微一大，swift 性能问题真的挺严重。时间复杂度：O(n^2) 空间复杂度：O(n^2)这个题是有一个 O(n) 的算法的。首先有暴搜的思路，就是以任何一位为中心往外扩展。O(n) 的算法是在这个基础上，利用回文串的特性，存在一个子串那么中心点两侧对称，在此基础上再往外搜即可。具体可见(Easy)
非常简单的题，唯一的难点就是题目本身描述得不太清楚了。需要自己考虑 row = 1、2 的边界情况。swift 有个stride函数用来处理 for step 的情况。时间复杂度：O(n) 空间复杂度：O(n)(Easy)
这题本身很简单，但感觉是道不错的面试题。可以测试面试者是否考虑各种边界情况，对溢出有没有概念。测试用例对 swift 给的不对，只能用Int32.max。我是把负数统一归成正数来计算，这样判断溢出的语句可以简单点。时间复杂度：O(lgn) 空间复杂度：O(1)(Easy)
这道题与其说是写代码不如说是写 case…… 一堆 case，真是一点懒都不能偷呀。时间复杂度：O(n) 空间复杂度：O(n)(Easy)
很简单的题，没给出的条件是负数不算回文数。有个 case 1000021 一开始做错了。另外一开始写了个递归，后来发现没必要……时间复杂度：O(n) 空间复杂度：O(1)(Hard)
评级为 hard，但感觉这题不难…… 就是递归一位一位往后读，遇到 * 就分两种情况，用尽这个 token 或者下轮接着用这个 token。一个问题就是直接递归会超时。需要先把正则式处理一下：- aa 合并为 a*
- a.b 合并为 .（就是 . 前后所有的 x 全都去掉）。时间复杂度：O(n) 空间复杂度：O(n)
(Medium)
本来想的是搜索加剪枝，搜以每个点做一端的。最坏情况 O(n^2)，结果最后有两组数据（就是最坏情况）过不去，超时。改成题解里这样，从两边往中间搜，结果变成 O(n) 了。想改成记忆化搜索，发现很难。搜索的顺序果然还是非常重要！很多东西从后往前搜，从中间往两边搜，从两边往中间搜，就差得多了……时间复杂度：O(n) 空间复杂度：O(1)(Medium)
很简单的递归，没什么可说的。就是细心一点吧。看到有的题解是把 1000、900、500 都存起来，这样确实快很多，因为不用考虑往左加的情况。另外非递归因为不用算 10 次幂可能略快一点。时间复杂度：O(lgn) 空间复杂度：O(1)(Easy)
很简单的题，没啥可说的。分情况讨论，简单递归即可（我怎么这么喜欢递归……）看到一个题解的思路挺巧妙，倒着往前扫，比前一位大就往上加，没前一位大就减掉。算是利用了罗马数字一个很好的特性吧。不过想了想好像没啥倒过来的必要啊…… 直接从前往后扫也是一样 O O时间复杂度：O(n) 空间复杂度：O(n)(Easy)
最简单的字符串处理，没什么可说的。时间复杂度：O(nm) 空间复杂度：O(nm)(Medium)
我用的还是 hash 方法，先找第一个数、再找第二个数…… 去重的方法就是要求三个数的序关系，这样就不会重了。看到一个题解用的是先排序，然后先定第一个数，第二个数左头，第三个数右头。然后大了挪小的、小了挪大的…… 这样。算是另一种思路吧。时间复杂度：O(n^2) 空间复杂度：O(n)(Medium)
这时候就用上上一题的排序思路了。先排好序，然后指定第一个数从左往右，第二个为第一个数右边（剩下区间的最左端），第三个数为最右端。然后小了把左边的往右挪、大了把右边的往左挪……时间复杂度：O(n^2) 空间复杂度：O(n)(Medium)
懒癌犯了…… 明明一道广搜的题，又写成“递归”了，仅仅是因为懒得开两个数组…… 是不是已经没得救了 O O好吧，后面老实补了一个正常版本。然后发现“递归”版本快得多…… 完全想不到任何原因呀，明明“递归”版本无谓地构造了一些后缀字符串，难道是拷贝数组很慢？时间复杂度：O(3^n) 空间复杂度：O(3^n)(Medium)
在 3Sum 基础上的延伸，先排序，再循环前两位，后两位左右夹逼。听说这样会超时？然而并没有，时间还在中位数左右。500多ms一些简单的剪枝，比如夹逼时最小的两个数都不够小、最大的两个数都不够大，那也就没必要继续了。加了这些剪枝，虽然代码长了很多很多，但是嗖快嗖快的，只要 52 ms。一下 beats 100% submissions，好有成就感呀。时间复杂度：O(n^3) 空间复杂度：O(n)(Easy)
挺简单的题，没什么可说的。只要两个指针，第一个指向头部，第二个指向第 n 个节点；然后把两个指针同时往后挪，当第二个指针到尾部时，第一个指针指向的就是就是倒数第 n 个节点，把它去了就行了。时间复杂度：O(n) 空间复杂度：O(n)(Easy)
大概是栈的最简单的一道题了。如果是左括号，push；是右括号，pop，如果不匹配返回 false。结束后如果栈空则返回 true，否则返回 false。时间复杂度：O(n) 空间复杂度：O(n)