前言

打算从0开始，用JavaScript刷题。
买了修言老师的小册子：前端算法与数据结构面试：底层逻辑解读与大厂真题训练
希望每天下班之后可以看一篇，争取早日上岸吧~

数据结构

我的想法：不同语言对于数据结构的实现有着不一样的特点。
之后的学习过程应该面向JavaScript的语言特性，针对前端的面试题来学习。

需要需要掌握的数据结构：

• 数组
• 栈
• 队列
• 链表
• 树

数组——重要的开箱即用数据类型

大多数的语言都天然地对数组有着原生的表达，JavaScript 亦然。这意味着我们可以对数组做到“开箱即用”，而不必自行模拟实现，非常方便。

初始化

在算法题中，推荐使用构造函数的方法初始化一个数组：

//推荐方法
const arr=new Array()
//该方法等价于
const arr = []
//使用构造函数创建数组的主要原因是，
//往往是因为我们有“创造指定长度的空数组”这样的需求。需要多长的数组，就给它传多大的参数.
const arr = new Array(7)

数组遍历

for方法

// 获取数组的长度
const len = arr.length
for(let i=0;i<len;i++) {
    // 输出数组的元素值，输出当前索引
    console.log(arr[i], i)
}

forEach方法

通过取 forEach 方法中传入函数的第一个入参和第二个入参，我们可以取到数组每个元素的值及其对应索引。
第一个入参：值
第二个入参：下标

arr.forEach((item, index)=> {
    // 输出数组的元素值，输出当前索引
    console.log(item, index)
})

map方法

map 方法在调用形式上与 forEach 无异。
区别在于 map 方法会根据你传入的函数逻辑对数组中每个元素进行处理、进而返回一个全新的数组
所以其实 map 做的事情不仅仅是遍历，而是在遍历的基础上“再加工”。
当我们需要对数组内容做批量修改、同时修改的逻辑又高度一致时，就可以调用 map 来达到我们的目的：

const newArr = arr.map((item, index)=> {
    // 输出数组的元素值，输出当前索引
    console.log(item, index)
    // 在当前元素值的基础上加1
    return item+1
})
//这段代码就通过 map 来返回了一个全新的数组,数组中每个元素的值都是在其现有元素值的基础上+1后的结果。

二维数组的初始化

不可用的fill方法及其局限性

	const arr =(new Array(7)).fill([])
	//生成了7行0列的一个空二维数组

缺陷在于，当你想修改某个坑里的数组的值时：

arr[0][0] = 1

原因：
当你给fill传递一个入参时，如果这个入参的类型是引用类型，那么 fill 在填充坑位时填充的其实就是入参的引用。
也就是说看似我们给7个坑位各初始化了一个数组。这7个数组对应了同一个引用、指向的是同一块内存空间，它们本质上是同一个数组。 因此当你修改第0行第0个元素的值时，第1-6行的第0个元素的值也都会跟着发生改变。

正确的初始化方法

const len = arr.length
for(let i=0;i<len;i++) {
    // 将数组的每一个坑位初始化为数组
    arr[i] = []
}

二维数组的遍历

for循环

// 缓存外部数组的长度
const outerLen = arr.length
for(let i=0;i<outerLen;i++) {
    // 缓存内部数组的长度
    const innerLen = arr[i].length
    for(let j=0;j<innerLen;j++) {
        // 输出数组的值，输出数组的索引
        console.log(arr[i][j],i,j)
    }
}

添加和删除元素的方法

添加方法

• unshift 方法-添加元素到数组的头部

const arr = [1,2]
arr.unshift(0) // [0,1,2]

• push 方法-添加元素到数组的尾部

const arr = [1,2]
arr.push(3) // [1,2,3]

• splice 方法-添加元素到数组的任何位置

const arr = [1,2] 
arr.splice(1,0,3) // [1,3,2]

splice方法详解

第一个入参是起始的索引值，
第二个入参表示从起始索引开始需要删除的元素个数
从第三个位置开始的入参，都代表着需要添加到数组里的元素的值

删除方法

• shift 方法-删除数组头部的元素

const arr = [1,2,3]
arr.shift() // [2,3]

• pop 方法-删除数组尾部的元素

const arr = [1,2,3]
arr.pop() // [1,2]

• splice 方法-删除数组任意位置的元素

const arr = [1,2,3]
arr.splice(1,1)//[1,3]
//删除从索引1位置的1个元素

总结

创造指定长度的空数组

const arr = new Array(7)

创建一个长度确定、同时每一个元素的值也都确定的数组

const arr = (new Array(7)).fill(1)
//[1,1,1,1,1,1,1]

当我们需要对数组内容做批量修改、同时修改的逻辑又高度一致时

const newArr = arr.map((item, index)=> {
    // 输出数组的元素值，输出当前索引
    console.log(item, index)
    // 在当前元素值的基础上加1
    return item+1
})

在 JavaScript 中，栈和队列的实现一般都要依赖于数组，大家完全可以把栈和队列都看作是“特别的数组”。

栈（Stack）——只用 pop 和 push 完成增删的“数组”

栈是一种后进先出的数据结构。
只允许从尾部添加或删除元素。

// 初始状态，栈空
const stack = []  
// 入栈过程
stack.push('东北大板')
stack.push('可爱多')
stack.push('巧乐兹')
stack.push('冰工厂')
stack.push('光明奶砖')

// 出栈过程，栈不为空时才执行
while(stack.length) {
    // 单纯访问栈顶元素（不出栈）
    const top = stack[stack.length-1]
    console.log('现在取出的冰淇淋是', top)  
    // 将栈顶元素出栈
    stack.pop()
}

// 栈空
stack // []

队列（Queue）——只用 push 和 shift 完成增删的“数组”

队列是先进先出的一种数据结构
队首出，队尾进。
（哈哈哈哈突然想到了星巴克补货都是先进先出呀。

const queue = []  
queue.push('小册一姐')
queue.push('小册二姐')
queue.push('小册三姐')  
  
while(queue.length) {
    // 单纯访问队头元素（不出队）
    const top = queue[0]
    console.log(top,'取餐')
    // 将队头元素出队
    queue.shift()
}

// 队空
queue // []

链表

链表结点的创建

function ListNode(val) {
    this.val = val;
    this.next = null;
}
const node = new ListNode(1)  
node.next = new ListNode(2)

JS 数组未必是真正的数组
JS比较特别。如果我们在一个数组中只定义了一种类型的元素const arr=[1,2,3]，那么他是连续内存的。
如果定义了不同的元素const arr=[1,''hahah',{a:1}]，则是一段非连续的内存。其底层使用哈希映射分配内存空间，是由对象链表来实现的。

树

二叉树的常用属性

二叉树第i层上最多有 $2^{i-1}$个节点
深度为h的二叉树中至多含有$2^h-1$个节点
若在任意一棵二叉树中，有$n_0$个叶子节点，有$n_2$个度为2的节点，则必有$n_0=n_2+1$
具有n个节点的完全二叉树深为$lo{g}_{2}x+1$（其中x表示不大于n的最大整数）

二叉树的节点

// 二叉树结点的构造函数
function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right=null;
}

二叉树遍历

• 先序遍历：根结点 -> 左子树 -> 右子树（先遍历根节点）
• 中序遍历：左子树 -> 根结点 -> 右子树 （根节点在中间遍历）
• 后序遍历：左子树 -> 右子树 -> 根结点（最后遍历根节点）
• 层序遍历：一层层遍历。

先序遍历

// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }
     
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历左子树 
    preorder(root.left)  
    // 递归遍历右子树  
    preorder(root.right)
}

中序遍历

// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }
     
    // 递归遍历左子树 
    inorder(root.left)  
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历右子树  
    inorder(root.right)
}

后序遍历

// 所有遍历函数的入参都是树的根结点对象
function postorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }
     
    // 递归遍历左子树 
    postorder(root.left)  
    // 递归遍历右子树  
    postorder(root.right)
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    
}

层序遍历