小磊哥er的大前端学习笔记

Appearance

《学习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 中的最大作用就退化到了检查代码的规范性。

写在后面 ​