前言
数据结构和算法是计算机科学的基石,是计算机的灵魂。要想成为计算机专业人员,学习和掌握算法是十分必要的。不懂数据结构和算法的人很难写出效率更高的代码。计算机科学的很多新行业都离不开数据结构和算法作为基石,比如大数据、人工智能等。底层开发中也需要使用非常多的数据结构和算法知识,以保证底层系统的稳定性和高效性。
一、对算法的理解
计算机科学家尼古拉斯·沃斯在计算机领域有一句人尽皆知的名言:
'算法 + 数据结构 = 程序'(Algorithms+Data Structures=Programs)
所以数据结构和算法是程序员必须掌握的技能。尤其是到一些大公司面试的时候,算法更是一个少不了的环节。熟练掌握数据结构和算法,可以开拓视野,提高逻辑思维能力,在写代码和分析官方源码的时候也非常有帮助。
学习数据结构和算法的一个好处就是:学完之后知识基本不会过时,可以永远为我们所用。大家都知道程序员需要不停地学习,因为知识更新太快。框架经常会被淘汰或大幅更新,但基础算法如 KMP 算法自 1977 年联合发表后,至今依然没有被淘汰。如果是一个框架,基本上很难保证那么多年还能存在,就算存在也会有大量的更新,还是需要不停地学习。
二、核心知识点概览
本书的知识覆盖范围全面,总共分为 13 个章节,先是详细介绍了常见的八大数据结构。后面都是我们比较常见的算法题,其中包括了二叉树的 Morris 遍历,KMP 算法,马拉车算法等经典题型。
关于数据结构,大家普遍认为难度较大的可能就是图了,本书对图的分类,图的表示方式,图的遍历,以及图的各种经典算法比如迪杰斯特拉算法,普里姆算法,拓扑排序等都有大量介绍。
主要涵盖内容如下:
- 数据结构:数组,链表,队列,栈,散列表,AVL 树,二叉搜索树,红黑树,字典树,哈夫曼树,线段树,笛卡尔树,堆,图的分类与表示,图的遍历
- 图算法:迪杰斯特拉算法,贝尔曼福特算法,弗洛伊德算法,普里姆算法,SPFA,克鲁斯卡尔算法,博鲁夫卡算法,拓扑排序
- 排序算法:冒泡排序,选择排序,插入排序,快速排序,归并排序,堆排序,桶排序,基数排序,希尔排序,计数排序
- 其他算法:牛顿迭代法,位运算,有限状态机,二叉树的遍历方式,Morris 遍历,递归,回溯算法,回溯剪枝,贪心算法,双指针,滑动窗口,Base64 编码,深度优先搜索 (DFS),广度优先搜索(BFS),前缀和,动态规划,国王与金矿,01 背包,完全背包,多重背包,组合与排列,并查集,KMP 算法,马拉车算法,算术表达式转换
三、章节内容详解
本书以 Java 为描述语言,介绍了计算机编程中常用的数据结构和算法,主要内容如下。
第 1 章:主要介绍了 8 种数据结构,包括数组、链表、队列、栈、散列表、树、堆、图。每种数据结构又有细分,比如介绍树的时候有完全二叉树、满二叉树、二叉搜索树、AVL 树、红黑树、字典树、哈夫曼树、线段树、笛卡儿树等。图的介绍中也包含经典的算法,比如迪杰斯特拉算法、弗洛伊德算法、普里姆算法和克鲁斯卡尔算法等。
第 2 章:介绍了几种经典排序算法,以及它们的稳定性分析。
第 3 章:主要介绍了一些位运算和常见操作符,还有一些简单的操作和使用技巧,如有限状态机和相关示例讲解。
第 4 章:介绍了和树有关的知识,比如树的遍历方式,包括 DFS 遍历、Morris 遍历,以及 BFS 遍历等。
第 5 章:分析了递归的原理和示例练习,可以把它看作是对一棵树的 DFS 遍历。
第 6 章:主要介绍了回溯算法的使用,然后得出回溯算法的使用模板,以及一些经典示例,还有一些重复问题和不符合条件的修剪分支。
第 7 章:主要介绍贪心算法的使用和存在的不足。
第 8 章:分别介绍了相向双指针、同向双指针和快慢双指针的使用技巧,还有滑动窗口的介绍和使用模板,以及大小可变窗口、固定窗口、只增不减窗口等。
第 9 章:主要介绍了 BFS 和 DFS 的使用模板和示例练习。
第 10 章:主要介绍了一维前缀和与二维前缀和的使用。
第 11 章:介绍动态规划和一些经典问题的讲解,如背包问题、组合与排列问题等。
第 12 章:通过生动形象的故事,介绍了并查集的使用、并查集优化、并查集路径压缩以及合并优化等。
第 13 章:介绍了其他一些经典算法,比如 KMP 算法、马拉车算法、算术表达式的运算、牛顿迭代法求平方根、Base64 编码等。
这是一本关于数据结构和算法的书,以 Java 为描述语言,介绍了计算机编程中常用的数据结构和算法。全书共 13 章,讲述了常见的数据结构、排序算法、位运算、树、递归、回溯算法、贪心算法、双指针和滑动窗口、BFS 和 DFS、前缀和、动态规划、并查集、其他经典算法等知识。本书内容丰富,实用性强,通过示例练习和问题分析等方式,详细讲解了与算法有关的知识点。


