愉快的leetcode

写这篇分享的时候,回忆起上大学那会儿的算法课,现在想起来都瑟瑟发抖。课本是三大圣经之一的《算法导论》,我们一群刚从从新手村里出来的弱鸡,看着前面这座大山,内心十分抗拒。那会儿的想法是,学这个有用吗?其实不光是算法,西电在本科期间设置的课程大多不涉及工程领域,四年时间,三年半都在学数据结构、算法、计算机导论、编译原理、计算机网络这些CS专业基础课,而且由于在当时看来这些课程本身没有太大联系,学的时候内心是充满困惑的。但现在看来,还是那时太年轻啊,工作之后面临的新技术,其实一点儿都不“新”。那些所谓的新技术,核心和本质的东西其实就是当初学的那些基础知识。掌握了这些基础之后,学任何东西都很快。现在我的理解是,基础知识就是大楼的地基,它决定我们的技术高度。

是什么

当你准备开始学习、回炉算法的时候,你已经意识到它是什么了。

为什么

当然是为了用。

1、最直接的就是能够写出高性能的代码。

对于iOSer来说,尤其我们平时做业务为主,感觉平时用到算法的地方不多,但只不过是苹果爸爸给我们封装好了而已,我们用的很多API,底层的东西都涉及到了数据结构和算法,只不过我们不用动手去实现。相较于后端来说可能自己用算法实现一些东西的机会会多一些。我就以我个人的经验举几个栗子🌰说明一下:

先说一个前两天碰到的,就咱们孕管的代码。帖子详情页的实现有四个地方存在内存问题,其中这个比较严重的直接导致在某些机型上内存撑爆gg。

ok,那么问题来了,也是一个经典的关于OC内存管理的iOS面试题:ARC下的 autoreleasepool 是什么,怎么用,它是怎么实现的?这里只说它的实现。

autoreleasepool的本质,或者说实现是一个与线程绑定的、以栈为节点的双向链表,很明显,它利用了链表的两个特性或者说优点才能达到帮我们释放内存的工作,即采用动态存储分配,不会造成内存浪费和溢出执行插入和删除操作十分方便,是修改指针的操作,不需要移动大量元素

通常情况下,我们是不需要手动添加 autoreleasepool 的,使用线程自动维护的 autoreleasepool 就好了。根据苹果官方文档中对 Using Autorelease Pool Blocks 的描述,我们知道在下面三种情况下是需要我们手动添加 autoreleasepool 的:

回到孕管代码里这个问题,属于第二种情况,PHForumDetialItemAnalysis 的set方法中,有大量的计算,而且创建了大量的占用内存的临时变量并且没有及时释放,导致了这个问题。

再说一个后端的栗子🌰吧,这个其实更具有代表性。场景是去年在上家公司”不务正业“去重写了公司的新的搜索后端服务。先简单列一下战果吧:

资源占用(服务器配置) 搜索效率 & 搜索质量
老搜索 8核16G内存 一般
新搜索 双核4G内存 巨幅提升

搜索服务是高内存需求的,重写后的新搜索在资源占用和搜索质量上都有了明显的提高。原因在哪呢,还是因为具体的实现有本质区别。
老的搜索是纯代码实现,没有借助任何的开源搜索引擎,大部分搜索相关功能是 数据库(MySQL)redis 来实现的,索引丢在redies的cache里面,在公司业务初期数据量不大的情况下也还ok,能撑得住,但是到后面公司的数据积累越来越大,老的搜索执行效率就开始出现问题了。所以才有了要重写新搜索的需求。

经过初期技术调研后,考虑到公司实际的业务和数据规模,新搜索决定基于 Elasticsearch 来做,关于 Elasticsearch 这里就不多说了,其实运维用的比较多,属于比较常见的ELK架构的一部分,很多用来搞日志分析的。新搜索之所以较老搜索有速度上的巨幅提升,根本原因还是在于 MySQL 和 Elasticsearch 索引方式的不同——Elasticsearch 使用的 倒排索引 比 MySQL 的 B-Tree索引 快。

呐,那么这两种索引算法的使用就是至关重要的了。关于倒排索引,它又包含了很多的数据结构和算法在里面。。。

所以说,掌握了数据结构与算法,看待问题的深度,解决问题的角度和方式就会完全不一样

2、大厂面试必备。

我觉得,这两个理由,足够了。当然作为程序员的”内功“,还有更多理由去学习数据结构和算法,就不多提了。高手闯荡江湖,哪怕一招儿鲜,那也得是内功深厚的一招儿鲜。

怎么做

第一步注册leetcode账号:
英文版 or 中文版

其实区别不大,之前中文版的题目稍微少些,现在同步的差不多了。而且现在英文版账号已经可以同步到中文版了。
简单的了解一下这个网站的使用: leetcode入门指南

基础知识准备

其实从前面也可以看出来,数据结构和算法是不分家的。它们都是前人从很多实际操作场景中抽象出来的,都是些比较经典的东西。之前说基础就是地基,下面介绍一下打地基所用的材料们:

复杂度分析

为什么要进行代码的复杂度分析?其实把代码跑过一遍以后通过一些比如IDE的监控啊什么的我们就能知道这段代码的执行效率了,包括用时啊、内存占用啊、CPU占用啊之类的,但这都属于事后诸葛。。。而且有很大的局限性:

  1. 受测试环境(比如硬件配置)影响大。同一段代码,不同机器运行,我配置牛逼就是跑的快,充钱的自然是爸爸,这在哪都是同样的道理,简单粗暴。
  2. 受测试数据不同而影响大。就拿排序来讲,比如对同一个排序算法而言,测试用例的有序度不一样,在相同环境下执行时间肯定是不同的;再比如不同的排序算法,由于数据规模不一样,很可能执行时间的结果也有较大差异,就几个数据排排序,可能插入排序就比快排快,但是你能说插入排序就是比快排快吗?数据量上万、上千万的时候呢?

综上,我们必须要做马前卒而不是马后炮,需要一个不依赖测试环境不依赖测试数据不需要代码执行就能衡量代码执行效率的标准或者方法,就是时间复杂度空间复杂度分析。

时间复杂度——大O表示法

时间复杂度可以简单地理解为执行这段代码所需要的时间

举个栗子🌰先:

一个非常简单的求0~n的和的代码:

1
2
3
4
5
6
7
8
int add(int n) {
int sum = 0;
int i = 1;
for (; i <= n; i++) {
sum = sum + i;
}
return sum;
}

根据计算机组成原理里的相关知识,从 CPU 的角度来看,这段代码的每一行,CPU 都要进行以下操作:读数据-运算-写数据。当然了,每行代码对应的 CPU 执行次数、执行的时间都不一样,但是这里只是粗略估计,所以可以假设每行代码执行的时间都一样,为一个单位时间常数 t。在这个假设的基础之上,来看下这段代码的总执行时间是多少。

第 2、3 行代码分别需要 1 个 t 的执行时间,第 4、5 行都运行了 n 遍,所以需要 2n*t 的执行时间,所以这段代码总的执行时间就是 T(n) = (2n+2) *t 。可以看出来, T(n) 与每行代码的执行次数 n 成正比。

再来个循环嵌套的代码瞅瞅:

1
2
3
4
5
6
7
8
9
10
11
int add(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; i++) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}

第 2、3、4 行代码,每行都需要 1 个 t 的执行时间,第 5、6 行代码循环执行了 n 遍,需要 2n*t 的执行时间,第 7、8 行代码循环执行了 n^2 遍,所以需要 2n^2 *t 的执行时间。所以,整段代码总的执行时间 T(n) = (2n^2 + 2n+3) *t。同样,T(n) 与每行代码的执行次数 n 也成正比 。

尽管我们不知道单位时间 t 的具体时长,但我们能看出来:一段代码的执行时间 = 代码总执行次数*单位时间 ,总结成一个公式就是大O表示法了:

T(n) = O(f(n))

具体解释一下这个公式。其中,T(n) 表示代码执行的时间;n 表示数据规模的大小;f(n) 表示每行代码执行的次数总和。因为这是一个公式,所以用 f(n) 来表示,就是上面的红色部分。公式中的 O,表示代码的执行时间 T(n) 与 f(n) 表达式成正比,就是单位时间的 t 倍。

所以,替换一下就可以知道:第一个栗子🌰中的 T(n) = O(2n+2),第二个栗子🌰中的 T(n) = O(2n^2+2n+3)。这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

其实很简单,当 n 很大时,决定多项式规模的是多项式中最高阶单项式。所以我们可以忽略多项式中低阶、常量、系数三部分,只需要记录一个最大量级就可以了,如果用大 O 表示法表示刚讲的那两段代码的时间复杂度,就可以简记为:

T(n) = O(n)
T(n) = O(n^2 )

到这里剩下的事儿其实很简单了,上面是讲原理所以看上去很复杂,其实上面那两段代码打眼一看就知道复杂度是多少:

  • 只关注循环次数对多的那段代码

  • 加法法则——总复杂度等于量级最大的那段代码的复杂度

    • 比如上面那两段代码放在一个方法里面,那这个新的方法的复杂度就是由后面那段代码决定的,也是 O(n^2 )
  • 乘法法则——嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    • 还是上面那哥儿俩,比如在第一个方法的循环中调用了第二个方法,则 T(n) = T1(n) * T2(n^2 ) = O(n*n^2 ) = O(n^3 )

关于这个 大O 有很多图和文章总结比较各种数据结构、算法的复杂度以及不同复杂度的对比,google一下 big o cheat sheet 巨多,可以去看下。这张来自 bigocheatsheet.com 的比较著名的一张图po一下:

几种常见的时间复杂度

这里主要列几种常见的多项式类型的时间复杂度,非多项式类型的 O(2^n ) 和 O(n!) ,当数据规模 n 越来越大时,这哥儿俩执行时间会急剧增加,无限增长,效率十分低下,就不多提了。

  • O(1)

O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码,它与输入数据的规模无关。比如这段代码:

1
2
3
4
5
6
int sum() {
int i = 8;
int j = 6;
int sum = i + j;
return sum;
}

一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。

  • O(logn)、O(nlogn)

对数阶的这种其实很常见,但又贼难看,很恶心。举个栗子🌰看下:

1
2
3
4
5
6
void func(int n) {
i = 1;
while (i <= n) {
i = i * 2;
}
}

还是看循环次数先,第 4 行这个语句决定什么时候跳出循环。i 每次循环的值变化为:2、4、8、16…即 k 次循环后值为 2^k 。跳出循环的条件为 i <= n 则求执行了多少次 k 为:2^k = n , k = log2n 。所以这段代码的时间复杂度就是 O(log2n) 。

同理,下面这段代码的时间复杂度就是 O(log3n) 。

1
2
3
4
5
6
void func(int n) {
i = 1;
while (i <= n) {
i = i * 3;
}
}

这里就有个说法了,根据换底公式,对数是可以互相转化的,因为 log3n = log32 * log2n ,所以 O(log3n) = O(常数*log2n) ,又因为我们可以忽略系数,所以这种对数的时间复杂度统一表示为O(logn) 。

O(nlogn) 就是根据前面乘法法则来的,O(logn) 中嵌套了个循环就变 O(nlogn) 。

  • O(n)、O(n^k )

这个不说了。。。就是几层循环的问题。。。

空间复杂度

这个就比较好理解了,就是某段代码运行所占用的空间。还是举个栗子🌰:

1
2
3
4
5
6
7
8
9
10
11
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}

for (i = n-1; i >= 0; --i) {
print out a[i]
}
}

上面这个,第 2 行,申请了一个空间储存 i ,算是额外空间,但是跟我们的数据规模 n 没有关系,所以直接忽略。第 3 行申请了大小为 n 的空间,这个算 O(n) ,除此之外没有占用额外的空间了,所以时候这段代码的空间复杂度为 O(n) 。

需要注意的是,在刷leetcode的时候,我们其实关注的更多的空间复杂度在于某段代码执行时所需要的额外空间,比如给个简单的数组排序,题目中给出的目标数组本身所占用的空间我们可以忽略,比如冒泡排序这种不需要开辟额外的辅助空间的算法空间复杂度就是 O(1) ,快排这种需要额外的辅助空间的,就需要 O(nlogn) 了。

数据结构与算法的概念&基础实现(随时补充)

概念和特性还是要比较熟练的掌握的,要不然下面的流程走不下去了。。当然,一些基础结构的基础实现也是应该熟记于心的,要不然真到了写代码的时候要用某个结构,发现这个结构怎么实现都写半天写不出来。。。那就基本gg了,有再好的算法思路都没用。

数据结构:

  • 数组

    • 数组的索引为什么从0开始?

      挺有意思的一个小东西:

      数组在实现随机访问的时候,比如a[i]是怎么访问的。“索引”或者“下标”的本质其实应该是“偏移量”

      数组的访问下标从0开始与从1开始的区别,其实本质上是 a[i]_address = base_address + i * type_sizea[i]_address = base_address + (i-1)*type_size 的区别。如果 a 是数组在内存中的首地址,那么访问 a[i] 时,计算其地址的公式分别为上面那俩。可以看到,后者多了一次减法运算。

      深入到CPU的层面,这里就多了一次减法指令,其实好像也没什么问题。。。对于现在的CPU来说差别好像不是很大,但要知道数组作为最基础的数据结构之一,其随机访问又是很基础的操作之一,效率的优化是要尽可能做到极致的,越往底层越是这样。上面提到了减法指令,为什么说多一个减法指令就会影响效率的问题,原因呢涉及到一部分《计组》的知识,关于CPU是怎么通过ALU完成最基本的加减操作的,这个不多展开。写到这里突然想起两个事儿,一个是当年被《计组》支配的恐惧,二是后来发现的网易公开课上一套关于CS的科普类型的专辑视频,挺好玩的,覆盖面比较全,虽然没那么系统、细致,但是我看前面讲计算机底层的一些底层概念的部分还是相当相当不错的,通俗易懂还有动画,比尼玛啃大部头的《计组》舒服多了,后悔当年刚学《计组》的时候咋没发现呢。。。大学一个学期整明白都费劲的东西,十几分钟就给你安排的明明白白。。。po张图感受下,墙裂推荐给大伙儿~

  • 链表

    • 单链表、双向链表、循环链表实现以及基本的CURD操作

      这里要特别注意边界条件的处理,特别是对头节点、尾节点、空链表的处理。建议引入哨兵节点简化部分判空操作。

      很多情况下,需要处理当前节点的前驱节点,如果是没有哨兵节点的链表,对第一个节点,即头节点,没有前驱节点。如果不作特殊处理,就可能出错;如果对它特别对待,就会增加代码复杂性,还会降低程序效率。而如果有哨兵节点的话, 线性表的每个位置的节点都有前驱节点,因此可以统一处理。这时候在考虑边界条件的时候往往只需要关注尾节点就好,省去了一些麻烦。

      ”哨兵“的应用除了在这里还有几个比较常见的情况,比如快排我们选取的基点就是一个哨兵,上面提到的 autoreleasepool 的实现原理中,OC也是通过”哨兵“来解决autoreleasepool的嵌套问题的,回头看完栈结构的时候可以再多聊一下。

    • 应用场景较多,往往链表会结合其他数据结构一起使用,比如拿散列表作链表的节点来实现高效的LRU算法等。

  • 队列

  • 散列表

  • 二叉树

  • Trie树

  • 。。。

算法

  • 递归
  • 排序
  • 二分查找
  • 搜索
  • 哈希
  • 贪心
  • 分治
  • 回溯
  • 动态规划
  • 字符串匹配
  • 。。。

leetcode题目(随时补充)

初次刷题或者对于我们而言,按照数据结构和算法分成多个小的模块,选取部分模块进行刷题就足够了,很多难度偏大和用得比较少的也不用去浪费时间在上面。

数据结构:

算法

  • 递归
  • 排序
  • 二分查找
  • 搜索
  • 哈希
  • 贪心
  • 分治
  • 回溯
  • 动态规划
  • 字符串匹配
  • 。。。

刷题

理想很丰满:看题——有思路——设计算法——写代码——通过

显示很骨感:看题——这啥啊——不会啊——想不出来啊——算了算了

为了避免被题恶心晕的情况,给大家推荐一个刷题思路吧:

  1. 读题
  2. 。。。直接看答案,没错,直接看答案
  3. 背答案手书默写
  4. leetcode作答,搞定一个解法
  5. 多思路、多解法
  6. 复杂度优化
  7. 二刷、三刷、四刷、五刷。。。。

需要注意的一点是,leetcode的测试用例会有考虑边界与极端情况,所以我们在写代码的时候也要考虑到,健壮性还是很重要的~

最后,祝各位刷的愉快 ^.^

文章作者: ゴウサク
文章链接: http://dapaner.top/2019/06/23/愉快的leetcode/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Corner&Coder
微信赞赏码
支付宝赞赏码