ShannonChenCHN
commented
3 years ago 课程结构
- 入门篇（4讲）
- 时间、空间复杂度分析
- 基础篇（38讲）
- 是本课程学习的重点
- 共有 26 节内容，涵盖了最基础、最常用的数据结构和算法
- 高级篇（9讲）
- 不是那么常用的数据结构和算法
- 实战篇（5讲）
- 剖析一些开源项目、框架或者系统设计问题背后的数据结构和算法
Open ShannonChenCHN opened 3 years ago
ShannonChenCHN
commented
3 years ago
ShannonChenCHN
commented
3 years ago 从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。
从狭义上讲，也就是我们专栏要讲的，是指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。这些都是前人智慧的结晶，我们可以直接拿来用。
数据结构和算法有什么关系呢？ 数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。 因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。
数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。
想要学习数据结构与算法，首先要掌握一个数据结构与算法中最重要的概念——复杂度分析。 复杂度分析这个内容，一定要花大力气来啃，必须要拿下，并且要搞得非常熟练。否则，后面的数据结构和算法也很难学好。
然后就是数据结构与算法的正文内容了。
咱们学习要找重点，对于我们非算法工程师来讲，只需要掌握下面这 20 个最常用的、最基础数据结构与算法，不管是应付面试还是工作需要，只要集中精力逐一攻克这 20 个知识点就足够了。
在学习数据结构和算法的过程中，你也要注意，不要只是死记硬背，不要为了学习而学习，而是要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”。
学习数据结构和算法的过程，是非常好的思维训练的过程，所以，千万不要被动地记忆，要多辩证地思考，多问为什么。如果你一直这么坚持做，你会发现，等你学完之后，写代码的时候就会不由自主地考虑到很多性能方面的事情，时间复杂度、空间复杂度非常高的垃圾代码出现的次数就会越来越少。你的编程内功就真正得到了修炼。
建议你每周花 1～2 个小时的时间，集中把这周的三节内容涉及的数据结构和算法，全都自己写出来，用代码实现一遍。这样一定会比单纯地看或者听的效果要好很多！
有不懂的可以在评论里面问，评论里面有老师，也有其他高手。
当你努力打到一定级别之后，每天看着自己的经验值、战斗力在慢慢提高，那种每天都在一点一点成长的成就感就不由自主地产生了。
我们在枯燥的学习过程中，也可以给自己设立一个切实可行的目标。比如，每节课后都写一篇学习笔记或者学习心得。
在学习的过程中，一定会碰到“拦路虎”。如果哪个知识点没有怎么学懂，不要着急，这是正常的。因为，想听一遍、看一遍就把所有知识掌握，这肯定是不可能的。学习知识的过程是反复迭代、不断沉淀的过程。
书读百遍其义自见。
我自己的一点补充：先画图再写代码，画图有利于理解。
Q：学习了，也理解了，当时可以写出代码来，但是长时间就忘记了😣，这个难道真的如果日常不用的话，的确会忘记，那是不是就要先当公式一样记下来再说？ A：完全不需要死记硬背的，我也记不住快排，红黑树，但是只要你掌握分析的能力，等你真的需要的时候，花不到半个小时就弄懂了。你要记住的是，这些算法的特点，应用场景，用到了能想到他就好了。
Q: 本人学的Java，请问通过这个课程学习如何把数据结构和算法切实的用到编程中，提高程序性能呢？ A：学习的过程可以锻炼你的性能意识，写代码的时候会不自觉的考虑性能问题，所以写出低效代码的情况就少了。
Q: 个人的学习疑惑:以前报培训班学习时，最常见的问题是实操了，但是由于为了跟上课程进度，练习频率不够，导致当返回头去，前面的又忘了，陷入恶性循环中，只能再将以前的知识点反复练，但学习周期会很长，老师有好的学习安排计划吗 A: 对于初学者确实会有这个问题，我们也不能期望一遍就搞的很牢，这个也不现实，所以往返看两三遍还是要的。
Q: 这里有3个问题想请教老师：
Q：本人应届毕业生，大学期间就一直很喜欢算法。简单的参加了蓝桥杯，难的参加了ACM。算是一个比一般增删改查程序员厉害不少，但是比真正的算法工程师弱很多。本人喜欢算法，是因为算法能让自己感受到成就感。我想问问up大大，算法复杂度分析，是因为我高数的知识不够扎实吗，一直搞不懂。只会分析o1，O（n），O（n平方）。对于其他，特别是log2n，2n次方之类的，就理解不了，不知道怎么算出来的，只能通过死记硬背，记住了哪些算法，哪些数据结构，哪些代码结构是怎样的复杂度。。一脸懵逼 A: 还是缺少锻炼啊 多找几个代码分析分析 或者看看人家怎么分析的。久了就懂了
ShannonChenCHN
commented
3 years ago 关联笔记 https://github.com/ShannonChenCHN/algorithm-and-data-structure/issues/2
ShannonChenCHN
commented
3 years ago 关联笔记 #2
ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago 常见的缓存淘汰策略有三种：
从底层的存储结构上来看：
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。
而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。
三种最常见的链表结构，它们分别是：
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。
其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。
从图中我们可以看出，针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。
但是如果要想随机访问链表中的第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，所以对应的时间复杂度是 O(n) 。
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。
和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。
单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
从上面的图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。
从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：
对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过指针操作将其删除。尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，所以总时间复杂度为 O(n)。
对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，时间复杂度依然是 O(n)。
但是对于双向链表来说，第二种情况下比较有优势了，时间复杂度变成了 O(1)，因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样从头开始遍历去找前驱节点。
如果我们希望在链表的某个指定结点后面插入一个结点，双向链表和单链表一样，都是 O(1)。
但是如果我们希望在链表的某个指定结点前面插入一个结点，双向链表就比单链表更高效。双向链表的时间复杂度为 O(1) ，而单向链表则需要 O(n) 的时间复杂度。原因跟上面说的删除操作类似，差异就在于找前驱结点的操作效率。
除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
现在，你有没有觉得双向链表要比单链表更加高效呢？这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。如果你熟悉 Java 语言，你肯定用过 LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理，就会发现其中就用到了双向链表这种数据结构。（iOS 开源框架 YYCache 中也用到了双向链表）
缓存实际上就是利用了空间换时间的设计思想，当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。
相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
总结一下，对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。
如图所示，数组和链表的插入、删除、随机访问操作的时间复杂度正好相反。
不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
IYNG 的笔记：CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块(这个大小我不太确定。。)并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。 对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。
当然链表也有其缺点，因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。
所以，在我们实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。
大致思路：
我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
如果此数据没有在缓存链表中，又可以分为两种情况：
ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago 队列和栈恰好相反，队列的特点是"先进后出"。
队列最基本的操作也是两个：
enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用：
在用数组来实现队列的时候会有一个问题：在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。
我们可以用循环队列来解决这个问题，那么什么是循环队列呢？
循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。
循环队列(Swift)的实现见 https://github.com/ShannonChenCHN/algorithm-and-data-structure/issues/16#issuecomment-763688835 。
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？ 线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
问题：线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago ShannonChenCHN
commented
3 years ago 练习：动态数据结构支持动态的数据插入、删除、查找操作，除了红黑树，我们前面还学习过哪些呢？能对比一下各自的优势、劣势，以及应用场景吗？
ShannonChenCHN
commented
3 years ago 延伸阅读：
ShannonChenCHN
commented
3 years ago 全排列的实现思路：
假设数组中存储的是1，2， 3...n。
f(1,2,...n) = {最后一位是1, f(n-1)} + {最后一位是2, f(n-1)} +...+{最后一位是n, f(n-1)}。
1, 2, 3, 4 --> [4, 2, 3 | 1] --> [3, 2 | 4, 1] --> [2 | 3, 4, 1]
--> [3 | 2, 4, 1]
--> [4, 3 | 2, 1] --> [3 | 4, 2, 1]
--> [4 | 3, 2, 1)]
--> [4, 2 | 3, 1] --> [2 | 4, 3, 1]
--> [4 | 2, 3, 1]
--> [1, 4, 3 | 2] --> [3, 4 | 1, 2] --> [4 | 3, 1, 2]
--> [3 | 4, 1, 2]
--> [1, 3 | 4, 2] --> [3 | 1, 4, 2]
--> [1 | 3, 4, 2]
--> [1, 4 | 3, 2] --> [4 | 1, 3, 2]
--> [1 | 4, 3, 2]
--> [1, 2, 4 | 3] --> [4, 2 | 1, 3] --> [2 | 4, 1, 3]
--> ...
--> [1, 2, 3 | 4] --> [3, 2 | 1, 4] --> [2 | 3, 1, 4]
--> ...代码：
/// 打印所有的排列组合
/// - Parameters:
/// - data: 要排列的数据
/// - k: 要处理的子数组的数据个数
func printPermutations(data: inout [Int], k: Int) {
if (k == 1) {
var str = ""
for i in 0..<data.count {
str = str + "\(data[i])"
if i != data.count - 1 {
str = str + ", "
}
}
print(str)
}
for i in 0..<k {
var tmp = data[i]
data[i] = data[k-1]
data[k-1] = tmp
printPermutations(data: &data, k: k - 1);
tmp = data[i]
data[i] = data[k-1]
data[k-1] = tmp
}
}
var array = [1, 2, 3, 4]
printPermutations(data: &array, k: array.count)
用动态规划解决 0-1 背包问题：
func knapsack(array: [Int], maxWeightAllowed: Int) -> Int {
let a = Array.init(repeating: false, count: maxWeightAllowed+1)
var states = Array.init(repeating: a, count: array.count)
// 第一个不放
states[0][0] = true
// 把第一个放进去
if array[0] <= maxWeightAllowed {
states[0][array[0]] = true
}
for i in 1..<array.count {
// 不把第 i 个物品放入背包，直接照搬前 i-1 个的处理结果
for j in 0...maxWeightAllowed {
if states[i-1][j] == true {
states[i][j] = true
}
}
// 把第 i 个物品放入背包，在前 i-1 个的处理结果基础上加上第 i 个物品的重量
// 这里要保证 j + 第 i 个的重量小于 maxWeightAllowed，如果超过了，那就说明放不下了
for j in 0...maxWeightAllowed-array[i] {
if states[i-1][j] == true {
states[i][j+array[i]] = true
}
}
}
for i in (0...maxWeightAllowed).reversed() {
if states[array.count-1][i] == true {
return i
}
}
return 0
}
let array = [2, 2, 4, 6, 3]
let result = knapsack(array: array, maxWeightAllowed: 9)
print(result)
空间复杂度为 O(w)，也就是使用一维数组的解法：
func knapsack(array: [Int], maxWeightAllowed: Int) -> Int {
var states = Array.init(repeating: false, count: maxWeightAllowed+1)
// 第一个不放
states[0] = true
// 把第一个放进去
if array[0] <= maxWeightAllowed {
states[array[0]] = true
}
for i in 1..<array.count {
// 把第 i 个物品放入背包，在前 i-1 个的处理结果基础上加上第 i 个物品的重量
// 这里要保证 j + 第 i 个的重量小于 maxWeightAllowed，如果超过了，那就说明放不下了
for j in (0...maxWeightAllowed-array[i]).reversed() {
if states[j] == true {
states[j+array[i]] = true
}
}
}
for i in (0...maxWeightAllowed).reversed() {
if states[i] == true {
return i
}
}
return 0
}
let array = [2, 2, 4, 6, 3]
let result = knapsack(array: array, maxWeightAllowed: 9)
print(result)用回溯法解决 0-1 背包问题升级版：
struct Item: Equatable {
let weight: Int
let value: Int
}
// 结果放到 maxValue 中
var maxValue = Int.min
// 所有物品
let itemList = [Item(weight: 2, value: 3),
Item(weight: 2, value: 4),
Item(weight: 4, value: 8),
Item(weight: 6, value: 9),
Item(weight: 3, value: 6)]
// 背包承受的最大重量
let kMaxWeightAllowed = 9
func add(i: Int, weight: Int, value: Int) {
if weight == kMaxWeightAllowed || i == itemList.count {
if value > maxValue {
maxValue = value
}
return
}
// 选择不装第i个物品
add(i: i + 1, weight: weight, value: value)
// 选择装第i个物品
if weight + itemList[i].weight <= kMaxWeightAllowed {
add(i: i + 1, weight: weight + itemList[i].weight, value: value + itemList[i].value)
}
}
add(i: 0, weight: 0, value: 0)
print(maxValue)// 18
课程地址：https://time.geekbang.org/column/article/39922?code=qCVA2cDQgRT3zHOy%2FZk21JRtNkN7CjYC31L8M0omrqQ