《学习JavaScript数据结构与算法（第2版）》精读笔记
写在前面
- 书籍介绍：本书讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构，之后探讨了各种排序和搜索算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序、顺序搜索、二分搜索，然后介绍了动态规划和贪心算法等常用的高级算法以及函数式编程，最后还介绍了如何计算算法的复杂度。
- 我的简评：数据结构和算法知识可以说是编程的通识，不管学习哪门编程语言，理解好数据结构，会一些基本的算法，才算入门。并且深入数据结构和算法，才能在编程的路上走得更高、更远。
- ！！福利：文末有pdf书籍、笔记思维导图、随书代码打包下载地址哦
数据结构
- 列表 List：斐波那契数列
- 队列 Queue：对数据进行排序；优先队列
- 栈 Stack：括号闭合； 进制转换；回文判断；递归演示；汉诺塔
- 字典 Dictionary
- 集合 Set：并集、交集、差集、子集
- 散列表 HashTable：散列函数；处理冲突有几种方法：分离链接、线性探查和双散列法
- 链表 LinkedList：双向链表；循环链表
- 二叉树 Bst：访问树的所有节点有三种方式：中序、先序和后序；难点：移除一个节点；自平衡二叉查找树、AVL树、红黑树
- 图 Graph：邻接矩阵；图遍历： 广度优先搜索（Breadth-First Search， BFS）和深度优先搜索（Depth-First Search， DFS）
- 最短路径算法
- 最小生成树
算法基础
基本算法：
- 阶乘：
return n * factorial(n - 1);
- 斐波那契数列：
return fibonacci2(n - 1) + fibonacci2(n - 2);；尾递归优化
- 素数检测：遍历i < Math.sqrt(n); 判断n % i == 0；
- 最大公约数：遍历i=Math.min(a, b);判断a % i == 0 && b % i == 0；
- 最小公倍数：遍历从i=Math.max(a, b);到i <= a * b;判断i % a == 0 && i % b == 0；
- 杨辉三角
- 最长公共子串
排序算法：
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 堆排序
- 快速排序
搜索算法：
- 线性查找
- 二分查找
- 跳转查找
- 插值查找
- 深度优先搜索
- 广度优先搜索
算法通识：
- 算法模式：1、递归：递归是一种解决问题的方法，它解决问题的各个小部分，直到解决最初的大问题。递归通常涉及函数调用自身。ECMAScript 6有尾调用优化；2、动态规划（Dynamic Programming， DP）是一种将复杂问题分解成更小的子问题来解决的优化技术。能解决的一些著名的问题如下：背包问题、最长公共子序列、矩阵链相乘、硬币找零、图的全源最短路径；3、贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。
- 算法复杂度：1、大 O 表示法：一般考虑的是CPU（时间）占用。排序算法的时间复杂度；搜索算法的时间复杂度；2、NP 完全理论：多项式算法。
设计原则
- 单一职责原则：SRP 原则体现为：一个对象（方法）只做一件事情；SRP 原则是所有原则中最简单也是最难正确运用的原则之一。
- 最少知识原则：最少知识原则（LKP）说的是一个软件实体应当尽可能少地与其他实体发生相互作用。
- 开放封闭原则：定义如下：软件实体（类、模块、函数）等应该是可以扩展的，但是不可修改；几乎所有的设计模式都是遵守开放-封闭原则的，我们见到的好设计，通常都经得起开放-封闭原则的考验。
- 接口与面向接口原则：接口是对象能响应的请求的集合；接口在 JavaScript 中的最大作用就退化到了检查代码的规范性。
写在后面
