算法：动态规划、回溯算法、查找算法、搜索算法、贪心算法、分治算法、位运算、双指针、排序、模拟、数学、……
数据结构：数组、栈、队列、字符串、链表、树、图、堆、哈希表、……

大部分前端用 js，算法只知道查找、排序，数据结构只知道数组、字符串。

数据结构

简介

数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。

不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。

常见的数据结构可分为「线性数据结构」与「非线性数据结构」。

「线性数据结构」Linear Data Structure：「数组」Array、「链表」Linked List、「栈」Stack、「队列」Queue。

「非线性数据结构」Non-linear Data Structure：「树」Tree、「堆」Heap、「散列表」Hashing、「图」Graph。

数组

数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。

「可变数组」是经常使用的数据结构，其基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：访问元素、添加元素、删除元素。

内存地址连续

链表

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」。

建立此链表需要实例化每个节点，并构建各节点的引用指向。

function ListNode (val, next) {
  this.val = val || null
  this.next = next || null
}

// 实例化节点
const n1 = new ListNode(4) // head
const n2 = new ListNode(5)
const n3 = new ListNode(1)

// 构建引用指向
n1.next = n2
n2.next = n3

栈

栈是一种具有「先入后出」特点的抽象数据结构，可使用数组或链表实现。

通过常用操作「入栈 push()」,「出栈 pop()」，展示了栈的先入后出特性。

const arr = new Array()

arr.push(1) // 元素 1 入栈
arr.push(2) // 元素 2 入栈

arr.pop() // 元素 2 出栈
arr.pop() // 元素 1 出栈

Stack，ArrayDeque，LinkedList 的区别

Java 中 Stack，ArrayDeque，LinkedList 都可以作为栈使用，但在性能以及实现的细节上有些区别。

队列

队列是一种具有「先入先出」特点的抽象数据结构，可使用链表实现。

通过常用操作「入队 push()」,「出队 shift()」，展示了队列的先入先出特性。

const arr = new Array()

arr.push(1) // 元素 1 入栈
arr.push(2) // 元素 2 入栈

arr.shift() // 元素 1 出栈
arr.shift() // 元素 2 出栈

树

树是一种非线性数据结构，根据子节点数量可分为「二叉树」和「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」。

建立此二叉树需要实例化每个节点，并构建各节点的引用指向。

function TreeNode (val, left, right) {
  this.val = val || null
  this.left = left || null
  this.right = right || null
}

// 实例化节点
const n1 = new TreeNode(3) // 根节点 root
const n2 = new TreeNode(4)
const n3 = new TreeNode(5)
const n4 = new TreeNode(1)
const n5 = new TreeNode(2)

// 构建引用指向
n1.left = n2
n1.right = n3

n2.left = n4
n2.right = n5

图？？？

图是一种非线性数据结构，由「节点（顶点）vertex」和「边 edge」组成，每条边连接一对顶点。根据边的方向有无，图可分为「有向图」和「无向图」。

顶点集合 vertices、边集合 edges

表示图的方法通常有两种：

1、邻接矩阵：使用数组 vertices 存储顶点，邻接矩阵 edges 存储边； edges[i][j] 代表节点 i + 1 和节点 j + 1 之间是否有边。
2、邻接表：使用数组 vertices 存储顶点，邻接表 edges 存储边。edges 为一个二维容器，第一维 i 代表顶点索引，第二维 edges[i] 存储此顶点对应的边集和；例如 edges[0] = [1, 2, 3, 4] 代表 vertices[0] 的边集合为 [1, 2, 3, 4]。

邻接矩阵 VS 邻接表：
邻接矩阵的大小只与节点数量有关，即 N^2，其中 N 为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。
因此，邻接表适合存储稀疏图（顶点较多、边较少）；邻接矩阵适合存储稠密图（顶点较少、边较多）。

散列表

散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。

es6 之 Map

堆？？？

堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。

完全二叉树定义：设二叉树深度为 k，若二叉树除第 k 层外的其它各层（第 1 至 k-1 层）的节点达到最大个数，且处于第 k 层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

替换空格

正则表达式 \s 代表空格
遍历添加

大海 10
心心苒 9.9
烟花 9.7
琳晚晚 9.6
幽若影 9.5 养老
钏言 9.3
尉迟 9.3
一柠檬一 9.2
灰发化 9.2
冰川 9.2
三千烟雨知江南 9.0 愿意
兰芝伤 9.0
幸运蓝莓 8.9
树莓味可乐 8.9
S5第一唐门 8.9
辣条 8.9
芊浅浅 8.8 养老
冷眸 8.8

数据结构

简介

数组

链表

栈

队列

树

图 ？？？

散列表

堆 ？？？

替换空格

图？？？

堆？？？