![]()
内容推荐 本书结合实际应用场景讲解数据结构和算法,涵盖常用、常考的数据结构和算法的原理讲解、代码实现和应用场景等。 本书分为11章。第1章介绍复杂度分析方法。第2章介绍数组、链表、栈和队列这些基础的线性表数据结构。第3章介绍递归编程技巧、8种经典排序、二分查找及二分查找的变体问题。第4章介绍哈希表、位图、哈希算法和布隆过滤器。第5章介绍树相关的数据结构,包括二叉树、二叉查找树、平衡二叉查找树、递归树和B+树。第6章介绍堆,以及堆的各种应用,包括堆排序、优先级队列、求Top K、求中位数和求百分位数。第7章介绍跳表、并查集、线段树和树状数组这些比较高级的数据结构。第8章介绍字符串匹配算法,包括BF算法、RK算法、BM算法、KMP算法、Trie树和AC自动机。第9章介绍图及相关算法,包括深度优先搜索、广度优先搜索、拓扑排序、Dijkstra算法、Floyd算法、A*算法、最小生成树算法、最大流算法和最大二分匹配等。第10章介绍4种算法思想,包括贪心、分治、回溯和动态规划。第11章介绍4个经典项目中的数据结构和算法的应用,包括Redis、搜索引擎、鉴权限流和短网址服务。另外,附录A为书中的思考题的解答。 尽管本书的大部分代码采用Java语言编写,但本书讲解的知识与具体编程语言无关,因此,本书不但适合各种类型的研发工程师,而且可以作为高校计算机相关专业师生的学习用书和培训学校的教材。 作者简介 王争,前Google工程师,微信公众号【小争哥】作者,GitHub上算法教程Star数排名前列。热衷分享,致力于通俗易懂地讲解数据结构和算法,帮助广大程序员攻克算法学习、算法刷题、算法面试三项难关。 目录 第1章 复杂度分析 1.1 复杂度分析(上):如何分析代码的执行效率和资源消耗 1.1.1 复杂度分析的意义 1.1.2 大O复杂度表示法 1.1.3 时间复杂度分析方法 1.1.4 几种常见的时间复杂度量级 1.1.5 空间复杂度分析方法 1.1.6 内容小结 1.1.7 思考题 1.2 复杂度分析(下):详解最好、最坏、平均、均摊这4种时间复杂度 1.2.1 最好时间复杂度和最坏时间复杂度 1.2.2 平均时间复杂度 1.2.3 均摊时间复杂度 1.2.4 内容小结 1.2.5 思考题 第2章 数组、链表、栈和队列 2.1 数组(上):为什么数组的下标一般从0开始编号 2.1.1 数组的定义 2.1.2 寻址公式和随机访问特性 2.1.3 低效的插入和删除操作 2.1.4 警惕数组访问越界问题 2.1.5 容器能否完全替代数组 2.1.6 解答本节开篇问题 2.1.7 内容小结 2.1.8 思考题 2.2 数组(下):数据结构中的数组和编程语言中的数组的区别 2.2.1 C/C++中数组的实现方式 2.2.2 Java中数组的实现方式 2.2.3 JavaScript中数组的实现方式 2.2.4 内容小结 2.2.5 思考题 2.3 链表(上):如何基于链表实现LRU缓存淘汰算法 2.3.1 链表的底层存储结构 2.3.2 链表的定义和操作 2.3.3 链表的变形结构 2.3.4 链表与数组的性能对比 2.3.5 解答本节开篇问题 2.3.6 内容小结 2.3.7 思考题 2.4 链表(下):借助哪些技巧可以轻松地编写链表相关的复杂代码 2.4.1 技巧1:理解指针或引用的含义 2.4.2 技巧2:警惕指针丢失和内存泄露 2.4.3 技巧3:利用“哨兵”简化代码 2.4.4 技巧4:留意边界条件和特殊情况 2.4.5 技巧5:举例画图,辅助思考 2.4.6 技巧6:多写多练,没有捷径 2.4.7 内容小结 2.4.8 思考题 2.5 栈:如何实现浏览器的前进和后退功能 2.5.1 栈的定义 2.5.2 顺序栈和链式栈 2.5.3 支持动态扩容的顺序栈 2.5.4 栈在函数调用中的应用 2.5.5 栈在表达式求值中的应用 2.5.6 栈在括号匹配中的应用 2.5.7 解答本节开篇问题 2.5.8 内容小结 2.5.9 思考题 2.6 队列:如何实现线程池等有限资源池的请求排队功能 2.6.1 队列的定义 2.6.2 顺序队列和链式队列 …… 第3章 递归、排序、二分查找 第4章 哈希表、位图和哈希算法 第5章 树 第6章 堆 第7章 跳表、并查集、线段树和树状数组 第8章 字符串匹配算法 第9章 图 第10章 贪心、分治、回溯和动态规划 第11章 数据结构和算法实战 附录A 思考题答案 |