Hello算法笔记
数据结构
可以根据逻辑结构和物理结构来区分
按照逻辑结构
1. 线性数据结构： 数组、链表、栈、队列、哈希表<br /> 2.非线形数据结构：树、图、堆、哈希表按照物理结构（在计算机内存中的存储方式）
- 连续空间存储
- 离散空间存储
数组
将相同类型元素存储在连续内存空间的数据结构，为什么数组的索引从0开始？因为索引本质上表示的是内存地址的偏移量，首个地址的偏移量是0，所以索引自然为0
优点
- 快速查找，直接访问对应索引元素
缺点
- 插入和删除的效率比较低（插入的时候需要后挪，删除的时候需要前移，时间复杂度O(N））
链表
一种线形数据结构，由一个个节点连接。节点中包含包含：当前节点的值value和指向下一个节点的地址next
优点
- 插入和删除的效率高，只需要改变原来一个节点的指针
缺点
- 访问节点的效率低，不能直接访问想要的节点，只能通过前置节点才能知道下一个节点
- 内存占用多，因为一个节点的内容除了包含值还有下个节点的饮用地址
尾节点的next字段值为null
链表类型
- 单向链表
- 环形链表
- 双向链表
栈
先进后出，叠在一起的盘子，要拿最低下的盘子，需要把上面的盘子一个个拿走
javascript可以使用数组模拟栈操作，也可以使用链表
队列
先进先出
javascript可以使用数组模拟栈操作，也可以使用链表
队列类型
- 双向队列，两端都可以添加和删除元素
哈希表(HashMap)
哈希表通过键值之前的映射，实现高效的元素查找。时间复杂度0(1),在
js中可以使用Map类型来实现
避免hash冲突可以是用Symbol来指定唯一key
二叉树
二叉树是一种非线性数据结构，表示祖先与后代之间的派生关系，体现一分为二的分治逻辑。类似于链表，二叉树也是节点关联。节点包含一个值，两个指针，左指针和右指针
/* 初始化二叉树 */
// 初始化结点
let n1 = new TreeNode(1),
n2 = new TreeNode(2),
n3 = new TreeNode(3),
n4 = new TreeNode(4),
n5 = new TreeNode(5);
// 构建引用指向（即指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
完美二叉树
所有的节点都被填满，所有节点的度为2
完全二叉树
只有最底层的节点没有被填满，且最底层节点尽量靠左填充
完满二叉树
除了叶结点之外，其余所有的节点都有两个子节点
平衡二叉树
任意节点的左子树和右子树的高度之差绝对值 
层序遍历（广度优先）
从上到下，从左到右
前序/中序/后序（深度优先）
其体现着一种：先走到头，再回头继续的遍历方式
- 前序访问： // 访问优先级：根结点 -> 左子树 -> 右子树
- 中序访问： // 访问优先级：左子树 -> 根结点 -> 右子树
- 后序访问： // 访问优先级：左子树 -> 右子树 -> 根结点
二叉搜索树
二叉搜索树需要满足：
- 对于根节点，左子树中所有的节点的值 < 根节点的值 < 右子树所有的节点值
- 任意节点的左子树和右子树也是满足条件1，即也是二叉搜索树
对于以上，可以想到先排序，然后二分
AVL树
AVL 树的独特之处在于「旋转 Rotation」的操作，其可 在不影响二叉树中序遍历序列的前提下，使失衡结点重新恢复平衡。换言之，旋转操作既可以使树保持为「二叉搜索树」，也可以使树重新恢复为「平衡二叉树」。
堆
一颗限定条件下的「完全二叉树」。
根据成立条件：
- Max Heap 大顶堆： 任意节点的值 ≥ 其子节点的值
- Min Heap 小顶堆： 任意节点的值 ≤ 其子节点的值
查找算法
线形查找
遍历数据结构+判断是否命中
时间复杂度： O(n)
空间复杂度： O(1)
优点
缺点
二分查找
利用数据的有序性，通过每轮缩小一半的搜索区间来查找
使用二分法的两个前置条件：
- 数据必须有序性
- 仅适用于数组，因为在循环的过程中需要跳跃
如果为了满足数据有序性，去做数据的排序，是得不偿失。排序算法的时间复杂度一般为O(nlogn)
优点
缺点
hash查找
借助一个哈希数据结构，根据键值对的映射，实现O(1)的查找，以空间换时间
在js中使用Map类型
优点
缺点
排序算法
冒泡排序
function bubbleSort(arrs) {
for (let i = nums.length; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j+1]) {
const tmp = nums[j];
nums[j] = nums[j+1]
nums[j+1] = tmp
}
}
}
}
插入排序
function insertSort(nums) {
for (let i = 1; i < nums.length; i++) {
let tmp = nums[i]
let j = i - 1
while(j >= 0 && nums[i] < nums[j]) {
nums[i] = nums[j]
j--
}
nums[j+1] = tmp
}
}
快速排序
// 先计算一次分割点，然后递归
function partition(nums, left, right) {
// 取第一个元素为基准值
// i 从左往右找到一个 大于基准值的
// j 从右往左找到一个 小于基准值的
let i = left
let j = right
const base = nums[i]
while(i < j) {
while(i < j && nums[j] > nums[left]) {
j--
}
while(i < j && nums[i] <= nums[left]) {
i++
}
swap(nums, i, j)
}
// i,j重叠
swap(nums, i, left)
return i
}
function swap(nums, i, j) {
const tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
}
//
function quickSort(nums, left, right) {
if (left >= right) {
return
}
const pivot = partition(nums, left, right)
quickSort(nums, left, pivot - 1)
quickSort(nums, pivot + 1, right)
}