/Algorithms

算法和数据结构项目

Primary LanguageJavaMIT LicenseMIT

License: MIT

Algorithms

数据结构和算法是良好的程序设计和高效代码的基础。如果你想要成为一个牛逼的程序员,那么掌握高效的数据结构和算法,是必须的技能。本课程的目标,是帮助广大程序员夯实数据结构和算法基础,提升抽象思维和编程能力。

本课程涉及的数据结构包括(但不限于):数组、链表、栈、队列和优先队列,并查集,二分搜索树,哈希表,AVL 树等。

本仓库包括课程的 PPT(包括文案讲稿),还有部分源代码。

本项目主要参考谷歌工程师 Wlliam Fiset 开源的算法项目

课程大纲

章节 标题(+视频链接) 内容
01 数据结构介绍 介绍什么是数据结构,为什么要学数据结构,还有什么是抽象数据类型。
02 算法复杂度 介绍算法复杂度和 Big-O 标记,并分析相关案例。
03 静态和动态数组 介绍数组概念,应用场景,支持的操作和复杂度,还有使用样例等。
04 实现动态数组 通过现场编程,演示如何基于静态数组实现动态数组。
05 单向和双向链表 介绍单向和双向链表,应用场景,术语,复杂度。演示如何插入和删除节点
06 实现双向链表 通过现场编程,演示如何实现双向链表。
07 栈 Stack 介绍什么是栈,栈有哪些使用场景,演示栈的操作,分析栈操作的复杂度。演示如何通过栈来解决括号匹配问题。演示汉诺塔游戏。
08 栈操作演示 通过 PPT 演示如何基于单向链表来实现栈。
09 实现栈(现场编程) 通过代码演示如何基于双向链表来实现栈。
10 队列 Queue 介绍什么是队列,队列的术语,队列有哪些使用场景,队列的操作演示,还有分析队列的操作复杂度。
11 队列操作演示(基于单向链表) 演示如何基于队列实现宽度优先搜索 BFS 算法,如何基于单向链表实现队列。
12 实现队列(现场编程) 现场编程演示如何基于双向链表来实现队列。
13 优先队列 PriorityQueue(穿插讲解堆 Heap) 介绍什么是优先队列 PQ,有哪些应用场景,演示 PQ 的主要操作,然后分析操作复杂度。中间穿插讲解堆 Heap。
14 将最小堆转换成最大堆 演示如何将最小堆(Min Heap)转换成最大堆(Max Heap),包括数值和字符串场景。
15 向二叉堆中添加元素 介绍二叉堆和完全二叉树,解释如何基于数组来实现二叉堆,演示如何向二叉堆中添加元素。
16 从二叉堆中移除元素 演示如何从二叉堆中移除元素,然后演示如何通过哈希表优化移除操作的复杂度。
17 实现二叉堆(现场编程)(上) 现场编程演示如何基于 ArrayList 实现二叉堆,并且采用 HashMap 对移除 Removal 操作进行优化。这是上半部分。
18 实现二叉堆(现场编程)(下) 现场编程演示如何基于 ArrayList 实现二叉堆,并且采用 HashMap 对移除 Removal 操作进行优化。这是下半部分。
19 并查集(Union Find) 介绍什么是并差集,应用场景,还有操作复杂度。
20 并查集应用~克努斯卡尔算法 演示并查集的应用~克努斯卡尔最小生成树算法。
21 查找和合并操作演示 演示并查集的查找和合并操作是如何工作的
22 并查集路径压缩 演示并查集的路径压缩是如何工作的
23 实现并查集(现场编程) 通过现场编程演示如何基于数据实现并查集
24 二叉搜索树(BST) 介绍什么是树,二叉树,和二叉搜索树。包括树的使用场景,二叉搜索树的操作复杂度。
25 向二叉搜索树中添加元素 演示如何向二叉搜索树中添加元素,评估添加操作的复杂度。
26 从二叉搜索树中移除元素 演示如何从二叉搜索树中移除元素,分四种情况。
27 从二叉搜索树中移除元素 演示树的先序、中序、后序和按层次遍历的工作方式。
28 实现二叉搜索树(现场编程)(上) 通过现场编程演示如何实现二叉搜索树,上半部分实现add/remove等方法
29 实现二叉搜索树(现场编程)(下) 通过现场编程演示如何实现二叉搜索树,下半部分演示如何实现四种遍历算法(先序/中序/后序和按层次遍历)。