推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > iOS大全 > 用 Swift 来刷 leet code 吧

用 Swift 来刷 leet code 吧

iOS大全 2018-10-18

来源:伯乐在线 - 戴仓薯 

如需转载,发送「转载」二字查看说明


前言


为什么要用 Swift 刷 leetcode?因为我有两个想法,一是学 Swift 并且有机会练练,二是想把 leetcode 刷完。于是,这两个想法就合二为一了,现在我以基本一天一道的速度在刷。


Swift 适合用来刷 leetcode 吗?现在做了20多道题,我个人的意见是不适合。可能比纯 C 好写,但没有主流的语言 java、python 好写。


首先 Swift 这门语言效率不高,有些算法拿别的语言过得去,拿 Swift 就会超时(虽然是跟 case 有关系,不过 Swift 效率确实不高)。其次,Swift 有很多麻烦的地方,尤其是字符串处理上。它甚至都不能随机访问字符串里某个位置的字符……还得先转成一个字符数组,也就意味着凡是有字符串的题的时间和空间复杂度都不会小于 O(n) 了。还有一些字符串相关的 API 会影响效率,如果想让代码简洁就会超时…… 总之感觉如果是练习算法,不用考虑这些因素是最好的,从这个角度来说,Swift 并不是最适合刷 leet code 的语言。但当然也是可行的,如果你有兴趣,一起来刷吧。


我把我的解法放在了我的 Github上,逐渐更新。另外,Github 上还有一个非常全的题解,我也为它贡献了一点点代码。


每道题的笔记


以下是 1-20 题我写的简单题解,卡住的时候可以来看看:


  1. Two Sum (Easy) 题解

    很简单的 hash。一个小技巧是,对于每个数先看和为 target 所需的数是否已经在 dict 里,如果已经在则直接返回,否则才把自身放进 dict 里。这样只需循环一次,不用先构建 hash、再遍历,循环两次。

    时间复杂度:O(n) 空间复杂度:O(n)


  2. Add Two Numbers (Medium) 题解

    简单的单链表处理。考虑几种情况:1. 两个数位数相等,且最高位不需进位 2. 两个数位数相等,且最高位需要进位 3. 两个数位数不相等。

    有些人写的时候会在结果的头部先创建一个dummy,val任意,真正的头结点直接往dummy后面插。最后返回dummy -> next。

    时间复杂度:O(n) 空间复杂度:O(1)


  3. Longest Substring Without Repeating Characters (Medium) 题解

    我用的方法是用一个 hash 记录每个字母出现的index,然后把字符串扫一遍。不出现重复时就往 hash 表里填。出现重复时,从 hash 取出字母出现的 previousIndex,把从当前串开头至previousIndex的字母都从 hash 中清掉。


    看到一个更好的方法,不需要存字母出现的index,出现重复时直接从当前串开头至出现重复字母的位置清掉 hash 即可。这种情况下也不需要用Dictionary存 hash,只需用Set即可。


    本来 hash 需要的额外空间很小,但因为 swift 要遍历字符串中的字符必须把字符数组存出来一份。所以空间复杂度为 O(n)。

    时间复杂度:O(n) 空间复杂度:O(n)


  4. Median of Two Sorted Arrays (Hard) 题解

    下面列出了两个解法,其中 Solution2 是自己想出来的,也过了全部测试数据,但方法非常不简洁。思路是从两边逼近中位数,取两个数列的中点,可证明总有一个不能满足第 k 大的条件。然后就调整这个数列。问题在于,有些情况可能会调整过头。另外,还有这个数列已经到头、调整不了的情况,此时就需要去调另一个数列。总的来说仍然是 log(m + n) 的,但代码非常长,原理也不够清晰。


    Solution1 参考了别人的题解,每次两个数列各取 k/2 处,小者在这个位置之前全都截断。


    为啥 Solution1 就非常简洁呢?最主要的问题在于,Solution1 是从一侧逼近问题的,每次迭代都更靠近答案。Solution2 是从两侧往中间逼近,然而两个数列并没有二分查找那么好的特性,有可能两个指针都在答案的同侧,还要回头找。


    另外,Solution1 利用了一个技巧,保证每次迭代时 nums1 都更短,不然交换。可以避免很多对称的重复代码。

    在语言方面,可以看出 swift 里if(...) {return ...}这种基本都用guard代替。

    时间复杂度:log(m+n) 空间复杂度:O(m+n)


  5. Longest palindromic Substring (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) 的算法是在这个基础上,利用回文串的特性,存在一个子串那么中心点两侧对称,在此基础上再往外搜即可。具体可见这篇文章


  6. ZigZag Conversion (Easy) 题解

    非常简单的题,唯一的难点就是题目本身描述得不太清楚了。需要自己考虑 row = 1、2 的边界情况。

    swift 有个stride函数用来处理 for step 的情况。

    时间复杂度:O(n) 空间复杂度:O(n)


  7. Reverse Integer (Easy) 题解

    这题本身很简单,但感觉是道不错的面试题。可以测试面试者是否考虑各种边界情况,对溢出有没有概念。

    测试用例对 swift 给的不对,只能用Int32.max。我是把负数统一归成正数来计算,这样判断溢出的语句可以简单点。

    时间复杂度:O(lgn) 空间复杂度:O(1)


  8. String to Integer (Easy) 题解

    这道题与其说是写代码不如说是写 case…… 一堆 case,真是一点懒都不能偷呀。

    时间复杂度:O(n) 空间复杂度:O(n)


  9. Palindrome Number (Easy) 题解

    很简单的题,没给出的条件是负数不算回文数。有个 case 1000021 一开始做错了。另外一开始写了个递归,后来发现没必要……

    时间复杂度:O(n) 空间复杂度:O(1)


  10. Regular Expression Matching (Hard) 题解

    评级为 hard,但感觉这题不难…… 就是递归一位一位往后读,遇到 * 就分两种情况,用尽这个 token 或者下轮接着用这个 token。

    一个问题就是直接递归会超时。需要先把正则式处理一下:

    aa 合并为 a*

    a.b 合并为 .(就是 . 前后所有的 x 全都去掉)。

    时间复杂度:O(n) 空间复杂度:O(n)


  11. Container With Most Water (Medium) 题解

    本来想的是搜索加剪枝,搜以每个点做一端的。最坏情况 O(n^2),结果最后有两组数据(就是最坏情况)过不去,超时。

    改成题解里这样,从两边往中间搜,结果变成 O(n) 了。想改成记忆化搜索,发现很难。

    搜索的顺序果然还是非常重要!很多东西从后往前搜,从中间往两边搜,从两边往中间搜,就差得多了……

    时间复杂度:O(n) 空间复杂度:O(1)


  12. Integer to Roman (Medium) 题解

    很简单的递归,没什么可说的。就是细心一点吧。

    看到有的题解是把 1000、900、500 都存起来,这样确实快很多,因为不用考虑往左加的情况。另外非递归因为不用算 10 次幂可能略快一点。

    时间复杂度:O(lgn) 空间复杂度:O(1)


  13. Roman to Integer (Easy) 题解

    很简单的题,没啥可说的。分情况讨论,简单递归即可(我怎么这么喜欢递归……)

    看到一个题解的思路挺巧妙,倒着往前扫,比前一位大就往上加,没前一位大就减掉。算是利用了罗马数字一个很好的特性吧。

    不过想了想好像没啥倒过来的必要啊…… 直接从前往后扫也是一样 O O

    时间复杂度:O(n) 空间复杂度:O(n)


  14. Longest Common Prefix (Easy) 题解

    最简单的字符串处理,没什么可说的。

    时间复杂度:O(nm) 空间复杂度:O(nm)


  15. 3Sum (Medium) 题解

    我用的还是 hash 方法,先找第一个数、再找第二个数…… 去重的方法就是要求三个数的序关系,这样就不会重了。

    看到一个题解用的是先排序,然后先定第一个数,第二个数左头,第三个数右头。然后大了挪小的、小了挪大的…… 这样。算是另一种思路吧。

    时间复杂度:O(n^2) 空间复杂度:O(n)


  16. 3Sum Closest (Medium) 题解

    这时候就用上上一题的排序思路了。先排好序,然后指定第一个数从左往右,第二个为第一个数右边(剩下区间的最左端),第三个数为最右端。然后小了把左边的往右挪、大了把右边的往左挪……

    时间复杂度:O(n^2) 空间复杂度:O(n)


  17. Letter Combinations of a Phone Number (Medium) 题解

    懒癌犯了…… 明明一道广搜的题,又写成“递归”了,仅仅是因为懒得开两个数组…… 是不是已经没得救了 O O

    好吧,后面老实补了一个正常版本。然后发现“递归”版本快得多…… 完全想不到任何原因呀,明明“递归”版本无谓地构造了一些后缀字符串,难道是拷贝数组很慢?

    时间复杂度:O(3^n) 空间复杂度:O(3^n)


  18. 4Sum (Medium) 题解

    在 3Sum 基础上的延伸,先排序,再循环前两位,后两位左右夹逼。听说这样会超时?然而并没有,时间还在中位数左右。500多ms

    一些简单的剪枝,比如夹逼时最小的两个数都不够小、最大的两个数都不够大,那也就没必要继续了。加了这些剪枝,虽然代码长了很多很多,但是嗖快嗖快的,只要 52 ms。一下 beats 100% submissions,好有成就感呀。

    时间复杂度:O(n^3) 空间复杂度:O(n)


  19. Remove Nth Node From End of List (Easy) 题解

    挺简单的题,没什么可说的。只要两个指针,第一个指向头部,第二个指向第 n 个节点;然后把两个指针同时往后挪,当第二个指针到尾部时,第一个指针指向的就是就是倒数第 n 个节点,把它去了就行了。

    时间复杂度:O(n) 空间复杂度:O(n)


  20. Valid Parentheses (Easy) 题解

    大概是栈的最简单的一道题了。如果是左括号,push;是右括号,pop,如果不匹配返回 false。结束后如果栈空则返回 true,否则返回 false。

    时间复杂度:O(n) 空间复杂度:O(n)


觉得本文对你有帮助?请分享给更多人

关注「 iOS大全 」

看更多精选 iOS 技术文章


专栏作者简介 (  



戴仓薯:iOS开发,同时也是世界上最大的仓鼠。

打赏支持作者写出更多好文章,谢谢!

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《用 Swift 来刷 leet code 吧》的版权归原作者「iOS大全」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注iOS大全微信公众号

iOS大全微信公众号:iOShub

iOS大全

手机扫描上方二维码即可关注iOS大全微信公众号

iOS大全最新文章

精品公众号随机推荐