数据结构与算法之美11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?

  |   0 评论   |   269 浏览

排序对于任何一个程序员来说,可能都不会陌生。你学的第一个算法,可能就是排序。大部分编程语言中,也都提供了排序函数。在平常的项目中,我们也经常会用到排序。排序非常重要,所以我会花多一点时间来详细讲一讲经典的排序算法。

排序算法太多了,有很多可能你连名字都没听说过,比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮,也是最经典的、最常用的:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。我按照时间复杂度把它们分成了三类,分三节课来讲解。

数据结构与算法之美10 | 递归:如何用三行代码找到“最终推荐人”?

  |   0 评论   |   311 浏览

推荐注册返佣金的这个功能我想你应该不陌生吧?现在很多App都有这个功能。这个功能中,用户A推荐用户B来注册,用户B又推荐了用户C来注册。我们可以说,用户C的“最终推荐人”为用户A,用户B的“最终推荐人”也为用户A,而用户A没有“最终推荐人”。

一般来说,我们会通过数据库来记录这种推荐关系。在数据库表中,我们可以记录两行数据,其中actor_id表示用户id,referrer_id表示推荐人id。

数据结构与算法之美09 | 队列:队列在线程池等有限资源池中的应用

  |   0 评论   |   310 浏览

我们知道,CPU资源是有限的,任务的处理速度与线程个数并不是线性正相关。相反,过多的线程反而会导致CPU频繁切换,处理性能下降。所以,线程池的大小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置的。

当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢?

实际上,这些问题并不复杂,其底层的数据结构就是我们今天要学的内容,队列(queue)。

数据结构与算法之美08 | 栈:如何实现浏览器的前进和后退功能?

  |   0 评论   |   319 浏览

浏览器的前进、后退功能,我想你肯定很熟悉吧?

当你依次访问完一串页面a-b-c之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面b和a。当你后退到页面a,点击前进按钮,就可以重新查看页面b和c。但是,如果你后退到页面b后,点击了新的页面d,那就无法再通过前进、后退功能查看页面c了。

数据结构与算法之美07 | 链表(下):如何轻松写出正确的链表代码?

  |   0 评论   |   268 浏览

上一节我讲了链表相关的基础知识。学完之后,我看到有人留言说,基础知识我都掌握了,但是写链表代码还是很费劲。哈哈,的确是这样的!

想要写好链表代码并不是容易的事儿,尤其是那些复杂的链表操作,比如链表反转、有序链表合并等,写的时候非常容易出错。从我上百场面试的经验来看,能把“链表反转”这几行代码写对的人不足10%。

为什么链表代码这么难写?究竟怎样才能比较轻松地写出正确的链表代码呢?

数据结构与算法之美06 | 链表(上):如何实现LRU缓存淘汰算法?

  |   0 评论   |   253 浏览

今天我们来聊聊“链表(Linked list)”这个数据结构。学习链表有什么用呢?为了回答这个问题,我们先来讨论一个经典的链表应用场景,那就是LRU缓存淘汰算法。

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。

数据结构与算法之美05 | 数组:为什么很多编程语言中数组都从0开始编号?

  |   0 评论   |   382 浏览

提到数组,我想你肯定不陌生,甚至还会自信地说,它很简单啊。

是的,在每一种编程语言中,基本都会有数组这种数据类型。不过,它不仅仅是一种编程语言中的数据类型,还是一种最基础的数据结构。尽管数组看起来非常基础、简单,但是我估计很多人都并没有理解这个基础数据结构的精髓。

在大部分编程语言中,数组都是从0开始编号的,但你是否下意识地想过,为什么数组要从0开始编号,而不是从1开始呢? 从1开始不是更符合人类的思维习惯吗?

你可以带着这个问题来学习接下来的内容。

数据结构与算法之美04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度

  |   0 评论   |   262 浏览

今天我会继续给你讲四个复杂度分析方面的知识点,最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)。如果这几个概念你都能掌握,那对你来说,复杂度分析这部分内容就没什么大问题了。

数据结构与算法之美03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?

  |   0 评论   |   244 浏览

我们都知道,数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢?这里就要用到我们今天要讲的内容:时间、空间复杂度分析。

其实,只要讲到数据结构与算法,就一定离不开时间、空间复杂度分析。而且,我个人认为,复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容基本上就掌握了一半

复杂度分析实在太重要了,因此我准备用两节内容来讲。希望你学完这个内容之后,无论在任何场景下,面对任何代码的复杂度分析,你都能做到“庖丁解牛”般游刃有余。

数据结构与算法之美02 | 如何抓住重点,系统高效地学习数据结构与算法?

  |   0 评论   |   230 浏览

你是否曾跟我一样,因为看不懂数据结构和算法,而一度怀疑是自己太笨?实际上,很多人在第一次接触这门课时,都会有这种感觉,觉得数据结构和算法很抽象,晦涩难懂,宛如天书。正是这个原因,让很多初学者对这门课望而却步。

我个人觉得,其实真正的原因是你没有找到好的学习方法没有抓住学习的重点。实际上,数据结构和算法的东西并不多,常用的、基础的知识点更是屈指可数。只要掌握了正确的学习方法,学起来并没有看上去那么难,更不需要什么高智商、厚底子。

还记得大学里每次考前老师都要划重点吗?今天,我就给你划划我们这门课的重点,再告诉你一些我总结的学习小窍门。相信有了这些之后,你学起来就会有的放矢、事半功倍了。

数据结构与算法之美01 | 为什么要学习数据结构和算法?

  |   0 评论   |   244 浏览

你是不是觉得数据结构和算法,跟操作系统、计算机网络一样,是脱离实际工作的知识?可能除了面试,这辈子也用不着?

尽管计算机相关专业的同学在大学都学过这门课程,甚至很多培训机构也会培训这方面的知识,但是据我了解,很多程序员对数据结构和算法依旧一窍不通。还有一些人也只听说过数组、链表、快排这些最最基本的数据结构和算法,稍微复杂一点的就完全没概念。

当然,也有很多人说,自己实际工作中根本用不到数据结构和算法。所以,就算不懂这块知识,只要Java API、开发框架用得熟练,照样可以把代码写得“飞”起来。事实真的是这样吗?

今天我们就来详细聊一聊,为什么要学习数据结构和算法。