概述
算法复杂度 / Big-O / 渐进分析法 ✅
- 这里没有什么需要实施的,你只是在观看视频并记笔记!耶!
- 这里有很多视频,只要看到你理解为止就好了,你随时可以回来复习。
- 如果你不理解背后的所有数学,不要担心。
- 你只需要理解如何用大O表示法来表达算法的复杂度。
- 哈佛大学CS50 - 渐进符号(视频)
- 大O符号(通用快速教程)(视频)
- 大O符号(以及Ω和Θ)- 最佳数学解释(视频)
- Skiena(视频)
- 加州大学伯克利分校关于大O符号(视频)
- 摊还分析(视频)
- TopCoder(包括递归关系和主定理):
- 速查表
- [回顾] 在 18 分钟内分析算法(播放列表)(视频)
好吧,差不多就到这里了。
当你阅读《破解编程面试》时,有一个章节专门讲述此事,并在最后进行了一次测验,以测试你是否能够确定不同算法的运行时间复杂度。这是一个非常全面的复习和测试。
数据结构
-
数组(Arrays) ✅
- 介绍:
- 实现一个动态数组(可自动调整大小的可变数组):
- 练习使用数组和指针去编码,并且指针是通过计算去跳转而不是使用索引
- 通过分配内存来新建一个原生数据型数组
- 可以使用 int 类型的数组,但不能使用其语法特性
- 从大小为16或更大的数(使用2的倍数 —— 16、32、64、128)开始编写
- size() —— 数组元素的个数
- capacity() —— 可容纳元素的个数
- is_empty()
- at(index) —— 返回对应索引的元素,且若索引越界则愤然报错
- push(item)
- insert(index, item) —— 在指定索引中插入元素,并把后面的元素依次后移
- prepend(item) —— 可以使用上面的 insert 函数,传参 index 为 0
- pop() —— 删除在数组末端的元素,并返回其值
- delete(index) —— 删除指定索引的元素,并把后面的元素依次前移
- remove(item) —— 删除指定值的元素,并返回其索引(即使有多个元素)
- find(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引,若未找到则返回 -1
- resize(new_capacity) // 私有函数
- 若数组的大小到达其容积,则变大一倍
- 获取元素后,若数组大小为其容积的1/4,则缩小一半
- 时间复杂度
- 在数组末端增加/删除、定位、更新元素,只允许占 O(1) 的时间复杂度(平摊(amortized)去分配内存以获取更多空间)
- 在数组任何地方插入/移除元素,只允许 O(n) 的时间复杂度
- 空间复杂度
- 因为在内存中分配的空间邻近,所以有助于提高性能
- 空间需求 = (大于或等于 n 的数组容积)* 元素的大小。即便空间需求为 2n,其空间复杂度仍然是 O(n)
-
链表(Linked Lists)
- 介绍:
- C代码(视频)
- 不是整个视频,只是关于Node结构和内存分配的部分。
- 链表 vs 数组:
- 为什么你需要避免使用链表(视频)
- 的确:你需要关于“指向指针的指针”的相关知识:(因为当你传递一个指针到一个函数时,
该函数可能会改变指针所指向的地址)该页只是为了让你了解“指向指针的指针”这一概念。
但我并不推荐这种链式遍历的风格。因为,这种风格的代码,其可读性和可维护性太低。 - 实现(我实现了使用尾指针以及没有使用尾指针这两种情况):
- size() —— 返回链表中数据元素的个数
- empty() —— 若链表为空则返回一个布尔值 true
- value_at(index) —— 返回第 n 个元素的值(从0开始计算)
- push_front(value) —— 添加元素到链表的首部
- pop_front() —— 删除首部元素并返回其值
- push_back(value) —— 添加元素到链表的尾部
- pop_back() —— 删除尾部元素并返回其值
- front() —— 返回首部元素的值
- back() —— 返回尾部元素的值
- insert(index, value) —— 插入值到指定的索引,并把当前索引的元素指向到新的元素
- erase(index) —— 删除指定索引的节点
- value_n_from_end(n) —— 返回倒数第 n 个节点的值
- reverse() —— 逆序链表
- remove_value(value) —— 删除链表中指定值的第一个元素
- 双向链表
- 介绍(视频)
- 并不需要实现
-
堆栈(Stack)
- 堆栈(视频)
- [Review] Stacks in 3 minutes (video)
- 可以不实现,因为使用数组来实现是微不足道的事
-
队列(Queue)
- 队列(视频)
- 原型队列/先进先出(FIFO)
- [Review] Queues in 3 minutes (video)
- 使用含有尾部指针的链表来实现:
- enqueue(value) —— 在尾部添加值
- dequeue() —— 删除最早添加的元素并返回其值(首部元素)
- empty()
- 使用固定大小的数组实现:
- enqueue(value) —— 在可容的情况下添加元素到尾部
- dequeue() —— 删除最早添加的元素并返回其值
- empty()
- full()
- 花销:
- 在糟糕的实现情况下,使用链表所实现的队列,其入列和出列的时间复杂度将会是 O(n)。
因为,你需要找到下一个元素,以致循环整个队列 - enqueue:O(1)(平摊(amortized)、链表和数组 [探测(probing)])
- dequeue:O(1)(链表和数组)
- empty:O(1)(链表和数组)
- 在糟糕的实现情况下,使用链表所实现的队列,其入列和出列的时间复杂度将会是 O(n)。
-
哈希表(Hash table)
-
视频:
-
在线课程:
-
使用线性探测法的数组实现
- hash(k, m) - m是哈希表的大小
- add(key, value) - 如果键已存在,则更新值
- exists(key) - 检查键是否存在
- get(key) - 获取给定键的值
- remove(key) - 删除给定键的值
-
更多的知识
-
二分查找(Binary search)
- 二分查找(视频)
- 二分查找(视频)
- 详情
- 蓝图
- 【复习】四分钟二分查找(视频)
- 实现:
- 二分查找(在一个已排序好的整型数组中查找)
- 迭代式二分查找
-
按位运算(Bitwise operations)
- Bits 速查表 ── 你需要知道大量2的幂数值(从2^1 到 2^16 及 2^32)
- 好好理解位操作符的含义:
&、|、^、~、>>、<<
- 一补数和补码
- 计算置位(Set Bits)
- 交换值:
- 绝对值:
树(Trees)
-
树-介绍
- 树的介绍(视频)
- 树遍历(视频)
- BFS(广度优先搜索)和DFS(深度优先搜索)(视频)
- BFS 笔记
- 层次遍历(BFS,使用队列)
- 时间复杂度: O(n)
- 空间复杂度:最佳情况:O(1),最坏情况:O(n/2)=O(n)
- DFS 笔记:
- 时间复杂度:O(n)
- 空间复杂度:
- 最好情况:O(log n) - 树的平均高度
- 最坏情况:O(n)
- 中序遍历(DFS:左、节点本身、右)
- 后序遍历(DFS:左、右、节点本身)
- 先序遍历(DFS:节点本身、左、右)
- BFS 笔记
- [复习]4分钟内的广度优先搜索(视频)
- [复习] 4分钟内的深度优先搜索(视频)
- [复习]11分钟内的树遍历(播放列表)(视频)
-
二叉查找树(Binary search trees):BSTs
- 二叉搜索树复习(视频)
- 介绍(视频)
- MIT(视频)
- C/C++:
- 实现:
- insert // 将值插入树中
- get_node_count // 查找树上的节点数
- print_values // 从小到大打印树中节点的值
- delete_tree
- is_in_tree // 如果值存在于树中则返回 true
- get_height // 以节点为单位返回高度(单个节点的高度为1)
- get_min // 返回树上的最小值
- get_max // 返回树上的最大值
- is_binary_search_tree
- delete_value
- get_successor // 返回给定值的后继者,若没有则返回-1
-
堆(Heap) / 优先级队列(Priority Queue) / 二叉堆(Binary Heap)
- 以树形结构可视化,但通常在存储上是线性的(数组、链表)
- 堆(Heap)
- 堆简介(视频)
- 二叉树(视频)
- 树高度备注(视频)
- 基本操作(视频)
- 完全二叉树(视频)
- 伪代码(视频)
- 堆排序 - 跳转到开始部分(视频)
- 堆排序(视频)
- 构建堆(视频)
- MIT:堆和堆排序(视频)
- CS 61B Lecture 24:优先队列(视频)
- 线性时间构建堆(大顶堆)
- [复习] 13分钟了解堆(视频)
- 实现一个大顶堆:
- insert
- sift_up —— 用于插入元素
- get_max —— 返回最大值但不移除元素
- get_size() —— 返回存储的元素数量
- is_empty() —— 若堆为空则返回 true
- extract_max —— 返回最大值并移除
- sift_down —— 用于获取最大值元素
- remove(i) —— 删除指定索引的元素
- heapify —— 构建堆,用于堆排序
- heap_sort() —— 拿到一个未排序的数组,然后使用大顶堆或者小顶堆进行就地排序
排序(Sorting)
- 笔记:
- 实现各种排序,知道每种排序的最坏、最好和平均的复杂度分别是什么场景:
- 不要用冒泡排序 - 效率太差 - 时间复杂度 , 除非
- 排序算法的稳定性 ("快排是稳定的么?")
- 哪种排序算法可以用链表?哪种用数组?哪种两者都可?
- 并不推荐对一个链表排序,但归并排序是可行的.
- 链表的归并排序
- 实现各种排序,知道每种排序的最坏、最好和平均的复杂度分别是什么场景:
关于堆排序,请查看前文堆的数据结构部分。堆排序很强大,不过是非稳定排序。
- Sedgewick ── 归并排序(5个视频)
- Sedgewick ── 快速排序(4个视频)
- 加州大学伯克利分校:
- 冒泡排序(视频)
- 冒泡排序分析(视频)
- 插入排序 & 归并排序(视频)
- 插入排序(视频)
- 归并排序(视频)
- 快排(视频)
- 选择排序(视频)
- 归并排序代码:
- 快速排序代码:
- [Review] Sorting (playlist) in 18 minutes
- 实现:
- 归并:平均和最差情况的时间复杂度为 。
- 快排:平均时间复杂度为 。
- 选择排序和插入排序的最坏、平均时间复杂度都是 。
- 关于堆排序,请查看前文堆的数据结构部分。
- 有兴趣的话,还有一些补充,但并不是必须的:
总结一下,这是15种排序算法的可视化表示。
如果你需要有关此主题的更多详细信息,请参阅“一些主题的额外内容”中的“排序”部分。
图(Graphs)
图表可以用来表示计算机科学中的许多问题,所以这一部分很长,就像树和排序一样。
-
笔记:
- 有4种基本方式在内存里表示一个图:
- 对象和指针
- 邻接矩阵
- 邻接表
- 邻接图
- 熟悉以上每一种图的表示法,并了解各自的优缺点
- 广度优先搜索和深度优先搜索:知道它们的计算复杂度和设计上的权衡以及如何用代码实现它们
- 遇到一个问题时,首先尝试基于图的解决方案,如果没有再去尝试其他的。
- 有4种基本方式在内存里表示一个图:
-
MIT(视频):
-
Skiena 教授的课程 - 很不错的介绍:
-
图 (复习和其他):
- 6.006 单源最短路径问题(视频)
- 6.006 Dijkstra算法(视频)
- 6.006 Bellman-Ford算法(视频)
- 6.006 加速Dijkstra算法(视频)
- Aduni:图算法 I - 拓扑排序,最小生成树,Prim算法 - 讲座6(视频)
- Aduni:图算法 II - DFS,BFS,Kruskal算法,Union Find数据结构 - 讲座7(视频)
- Aduni:图算法 III:最短路径 - 讲座8(视频)
- Aduni:图算法 IV:几何算法入门 - 讲座9(视频)
- CS 61B 2014:加权图(视频)
- 贪婪算法:最小生成树(视频)
- 强连通分量Kosaraju算法图算法(视频)
- [复习] 最短路径算法(播放列表)16分钟(视频)
- [复习] 最小生成树(播放列表)4分钟(视频)
-
完整的 Coursera 课程:
-
我会实现:
- DFS 邻接表 (递归)
- DFS 邻接表 (栈迭代)
- DFS 邻接矩阵 (递归)
- DFS 邻接矩阵 (栈迭代)
- BFS 邻接表
- BFS 邻接矩阵
- 单源最短路径问题 (Dijkstra)
- 最小生成树
- 基于 DFS 的算法 (根据上文 Aduni 的视频):
- 检查环 (我们会先检查是否有环存在以便做拓扑排序)
- 拓扑排序
- 计算图中的连通分支
- 列出强连通分量
- 检查双向图
更多知识
-
递归(Recursion)
- Stanford 大学关于递归 & 回溯的课程:
- 什么时候适合使用
- 尾递归会更好么?
- 解决任何递归问题的5个简单步骤(视频)
-
动态规划(Dynamic Programming)
- 在你的面试中或许没有任何动态规划的问题,
但能够知道一个题目可以使用动态规划来解决是很重要的。 - 这一部分会有点困难,每个可以用动态规划解决的问题都必须先定义出递推关系,要推导出来可能会有点棘手。
- 我建议先阅读和学习足够多的动态规划的例子,以便对解决 DP 问题的一般模式有个扎实的理解。
- 视频:
- Skiena:CSE373 2020 - 讲座19 - 动态规划简介(视频)
- Skiena:CSE373 2020 - 讲座20 - 编辑距离(视频)
- Skiena:CSE373 2020 - 讲座20 - 编辑距离(续)(视频)
- Skiena:CSE373 2020 - 讲座21 - 动态规划(视频)
- Skiena:CSE373 2020 - 讲座22 - 动态规划和复习(视频)
- Simonson:动态规划 0(从59:18开始)(视频)
- Simonson:动态规划 I - 第11讲(视频)
- Simonson:动态规划 II - 第12讲(视频)
- 单独的动态规划问题列表(每个都很短):
动态规划(视频)
- 耶鲁课程笔记:
- Coursera 课程:
- 在你的面试中或许没有任何动态规划的问题,
-
组合(Combinatorics) (n 中选 k 个) & 概率(Probability)
-
NP, NP-Completeness和近似算法
- 知道最经典的一些 NP-Completeness 问题,比如旅行商问题和背包问题,
而且能在面试官试图忽悠你的时候识别出他们。 - 知道 NP-Completeness 是什么意思.
- 计算复杂度(视频)
- Simonson:
- Skiena:
- 复杂度: P, NP, NP-完全性, 规约(视频)
- 复杂度: 近视算法 Algorithms(视频)
- 复杂度: 固定参数算法(视频)
- Peter Norvik 讨论旅行商问题的近似最优解:
- 《算法导论》(CLRS)的第 1048 - 1140 页。
- 知道最经典的一些 NP-Completeness 问题,比如旅行商问题和背包问题,
其他
链表加数组实现自动扩容