数据结构

栈

一个后进先出的数据结构。在JS中，使用数组实现栈结构。

javascript

const stack = [];
stack.push(1);
const items = stack.pop();

使用场景：需要后进先出的场景，如十进制转二进制、判断字符括号是否有效和函数调用堆栈等

相关题目：力扣第20题

JS中的函数调用堆栈

多个函数的互相调用就是入栈和出栈的操作。

队列

一个先进先出的数据结构，使用数组可以实现队列的结构。

javascript

const queue = [];
queue.push(1);
const item1 = queue.shift();

应用场景：需要先进先出的场景，例如食堂排队打饭、js异步中的任务队列、计算最近请求次数

题目：力扣第933题

js异步中的任务队列

异步任务会被放到webAPIs执行，然后代码会继续执行。

javascript

// 先打印2再打印1
setTimeout(() => console.log(1), 0);
console.log(2)

链表

多个元素组成的列表，元素存储不连续，使用next指针连在一起。我们可以使用对象模拟一个链表。

javascript

const a = {val: 'a'};
const b = {val: 'b'};
a.next = b;
// 遍历链表
let p = a;
while(p) {
    console.log(p);
    p = p.next;
}
// 插入 a c b
const c = {val: 'c'};
c.next = b;
a.next = c;
// 删除 a b
a.next = b

推荐题目：力扣第237、206、2、83、141题

JS中的原型链

本质是链表，原型链上的节点是各种原型对象，如Object.prototype、Function.prototype，原型链通过__proto__属性连接各种原型对象。

如果A沿着原型链能找到B.prototype，那么A instanceof B为true。所有的对象的原型对象都是Object。如果在A对象上没有找到x属性，那么会沿着原型链找x属性。

javascript

func instanceof Object;  // true

面试题1

instanceof的原理，并用代码实现。

javascript

const instanceOf = (A, B) => {
    let p = A;
    while(p) {
        if(p === B.prototype) return true;
        p = p.__proto__;
    }
    return false;
};

面试题2

输出什么？

javascript

var foo = {}, F = function(){};
Object.prototype.a = 'a';
Function.prototype.b = 'b';

console.log(foo.a);  // a
console.log(foo.b);  // undifind
console.log(F.a); // a
console.log(F.b); // b

获取JSON的节点值

javascript

const json = {
    a: {
        b: {
            c: 2
        }
    },
    d: 3   
}
const path = ['a', 'b', 'c'];
let p = json;
path.forEach(k => {
    p = p[k];
})

集合

一种无序且唯一的数据结构，ES6中有集合(Set)这一数据结构。集合常用操作有去重、判断某元素是否在集合中、求交集......

javascript

// 去重
const arr = [1, 1, 1, 2];
const arr2 = [...new Set(arr)];
// 判断元素是否在集合中
const set = new Set(arr)
console.log(set.has(1)); // true
// 求交集
const set2 = new Set([2, 3]);
const set3 = new Set([...set].filter(item => set2.has(item)))

推荐题目：力扣第349题

Set操作

使用Set对象：new、add、delete、has、size
迭代Set：多种迭代方法、Set和Array互转、求交集/差集

javascript

const mySet = new Set();
mySet.add(1);
mySet.add('hello');
mySet.add({a: 1});
console.log(mySet.has(3));
mySet.delete(1);
// 迭代set 三种效果一样
for (let item of mySet) {
    console.log(item);
}
for (let item of mySet.keys()) {
    console.log(item);
}
for (let item of mySet.values()) {
    console.log(item);
}
// set转array
const arr1 = [...mySet];
const arr2 = Array.from(mySet);
// array转Set
const mySet2 = new Set([1, 2, 3, 4])
// 求交集
const mySet3 = new Set([...mySet].filter(x => mySet2.has(x)));
// 求差集
const mySet4 = new Set([...mySet].filter(x => !mySet2.has(x)));

字典

与集合类似，字典也是一种存储唯一值的数据结构，它是以键值对的形式存储的（集合的键值都是一样的）。ES6有字典数据结构（Map），字典的常用操作有：键值对的增删改查。

javascript

const m = new Map();
// 增
m.set('a', 'aa');
// 删
m.delete('a');
m.clear();
// 改
m.set('a', 'aaa');
// 查
m.get('a')

推荐题目：力扣第349、20、1、3、76题

树

一种分层数据的抽象模型，前端工作中常见的树包括：DOM树、级联选择、树形控件.......。JS中可以用Object和Array构建树。树的常用操作为：深度/广度优先遍历、先中后序遍历。

javascript

const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'c',
                    children: []
                },
                {
                    val: 'd',
                    children: []
                }
            ]
        },
        {
            val: 'e',
            children: []
        }
    ]
}

推荐题目：力扣第104、111、102、94、112题。

深度/广度优先遍历

深度优先遍历是指尽可能深的搜索树的分支；广度优先遍历是指先访问离根节点最近的节点。

深度优先遍历算法口诀为：先访问根节点，再对根节点的children挨个进行深度优先遍历。

javascript

const dfs = (root) => {
    console.log(root.val)
    root.children.forEach(dfs)
};

广度优先遍历的算法口诀为：先新建一个队列，把根节点入队，然后将队头出队并访问最后把队头的children挨个入队，重复上面的第二第三步，直到队列为空。

javascript

const bfs = (root) => {
    const q = [root];
    while(q.length > 0) {
        const n = q.shift();
        console.log(n.val);
        n.children.forEach(child => {
            q.push(child);
        });
    }
};

二叉树的先中后序遍历

树中每个节点最多两个节点。在JS中通常用Object来模拟二叉树。

javascript

const bt = {
    val: 'a',
    left: {
        val: 'b',
        left: null,
        right: null
    },
    right: {
        val: 'c',
        left: null,
        right: null
    }
}

先序遍历

先访问根节点，再对根节点的左子树进行遍历，最后对根节点的右子树进行遍历。

javascript

// 遍历
const preOrder = (root) => {
    if(!root) return;
    console.log(root.val);
    preOrder(root.left);
    preOrder(root.right);
};
// 非遍历
const preOrder = (root) => {
    if(!root) return;
    const stack = [root];
    while(stack.length) {
        const n = stack.pop();
        console.log(n.val);
        if(n.right) stack.push(n.right);
        if(n.left) stack.push(n.left);
    }
};

中序遍历

先对根节点的左子树进行遍历，再访问根节点，最后对根节点的右子树进行遍历。

javascript

// 遍历
const inOrder = (root) => {
    if(!root) return;
    inOrder(root.left);
    console.log(root.val);
    inOrder(root.right);
};
// 非遍历
const inOrder = (root) => {
    if(!root) return;
    const stack = [];
    let p =  root;
    while(stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop()
        console.log(n.val);
        p = n.right;
    }
};

后序遍历

先对根节点的左子树进行遍历，再对根节点的右子树进行遍历，最后访问根节点。

javascript

// 遍历
const postOrder = (root) => {
    if(!root) return;
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.val);
};
// 非遍历
const postOrder = (root) => {
    if(!root) return;
    const stack = [root];
    const outputStack = [];
    while(stack.length) {
        const n = stack.pop();
        outputStack.push(n);
        if(n.left) stack.push(n.left);
        if(n.right) stack.push(n.right);
    }
    while(outputStack.length) {
        const n = outputStack.pop();
        console.log(n.val);
    }
};

遍历JSON的所有节点值

javascript

const json = {
    a: {
        b: {
            c: 2
        }
    },
    d: [1, 3]
}

const dfs = (n, path) => {
    console.log(n, path);
    Object.keys(n).forEach(k => {
        dfs(n[k], path.concat(k));
    })
}
dfs(json, []);

图

图是网络结构的抽象模型，是一组由边连接的节点，图可以表示任何二元关系。在JS中，我们可以用Array和Object构建图，图的表示法有：邻接矩阵、邻接表、关联矩阵......。图的操作有深度与广度优先遍历。

深度与广度优先遍历

深度优先遍历是指尽可能深的搜索树的分支；广度优先遍历是指先访问离根节点最近的节点。

深度优先遍历算法口诀为：先访问根节点，再对根节点的没访问过的相邻节点挨个进行深度优先遍历。

javascript

const visited = new Set();
const dfs = (n) => {
    console.log(n);
    visited.add(n);
    graph[n].forEach(c => {
        if(!visited.has(c)) dfs(c);
    });
};

广度优先遍历的算法口诀为：先新建一个队列，把根节点入队，然后将队头出队并访问最后把队头的没访问过的相邻节点挨个入队，重复上面的第二第三步，直到队列为空。

javascript

const visited = new Set();
visited.add(2);
const q = [2];
while(q.length) {
    const n = q.shift();
    console.log(n);
    graph[n].forEach(c => {
        if (!visited.has(c)) {
            q.push(c);
            visited.add(n);
        }
    });
}

推荐题目：力扣第65、417、133题

堆

一种特殊的完全二叉树。所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点。在JS中使用数组表示堆，采用广度优先遍历的方式。左侧子节点的位置是2 * index + 1右侧子节点的位置为2 * index + 2。父节点的位置是(index -1)/2。堆能够高效、快速地找到最大最小值（时间复杂度为O(1)）。

第k个最大元素

构建一个最小堆，并将元素依次插入堆中
当堆的容量超过k，就删除堆顶
插入结束后，堆顶就是第k个最大元素

实现最小堆类

在类里，声明一个数组，用来装元素
主要方法：插入、删除堆顶、获取堆顶、获取堆大小

javascript

class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 获取父节点的index
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    // 获取左节点的index
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    // 获取右节点的index
    getRightIndex(i) {
        return i * 2 + 2;
    }
    // 交换操作
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp
    }
    // 上移操作
    shiftUp(index) {
        if(index == 0) return ;
        const parentIndex = this.getParentIndex(index);
        if(this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    // 下移操作
    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if(this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if(this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    // 插入
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    // 删除堆顶
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
    // 获取堆顶
    peek() {
        return this.heap[0];
    }
    // 获取堆的大小
    size() {
        return this.heap.length;
    }
}

推荐题目：力扣第215、347、23题

排序和搜索

排序是把某个乱序的数组变成升序或者降序的数组，搜索是找出数组中某个元素的下标。在JS中，搜索使用数组的sort方法，搜索使用数组的indexOf方法。

排序算法

排序算法有冒泡排序、选择排序、插入排序、归并排序和快速排序等。

图解：排序

冒泡排序

比较所有相邻元素，如果第一个比第二个大，则交换它们，这样一轮下来就可以保证最后一个数是最大的，执行n-1轮，就可以完成排序。

javascript

Array.prototype.bubbleSort = function() {
    for(let i = 0; i < this.length - 1; i++) {
        for(let j = 0; j < this.length - 1 - i; j++) {
            if(this[j] > this[j + 1]) {
                const temp = this[j];
                this[j] = this[j + 1];
                this[j + 1] = temp;
            }
        }
    }
}
const arr = [5, 4, 3, 1, 2];
arr.bubbleSort();

冒泡排序有两层嵌套循环，时间复杂度为O(n ^ 2)。

选择排序

找到数组中最小值，选中它并将其放置在第第一位，接着找到第二小的值，将其放置在第二位，以此类推，执行n-1轮。

javascript

Array.prototype.selectionSort = function() {
    for(let i = 0; i < this.length - 1; i++) {
        let indexMin = i;
        for(let j = i; j < this.length; j++) {
            if(this[j] < this[indexMin]) {
                indexMin = j;
            }
        }
        if(indexMin !== i) {
            const temp = this[i];
            this[i] = this[indexMin];
            this[indexMin] = temp;
        }
    }
    
}
const arr = [5, 4, 3, 1, 2];
arr.selectionSort();

选择排序也是两层嵌套循环，时间复杂度和冒泡排序一样。

插入排序

从第二个数开始往前比，比它大就往后排，以此类推进行到最后一个数。

javascript

Array.prototype.insertSort = function() {
    for(let i = 1; i < this.length; i++) {
        const temp = this[i];
        let j = i;
        while(j > 0) {
            if(this[j - 1] > temp) {
                this[j] = this[j - 1];
            } else {
                break;
            }
            j --;
        }
        this[j] = temp;
    }
}
const arr = [5, 4, 3, 1, 2];
arr.insertSort();
console.log(arr);

插入排序时间复杂度和前面两个排序一样，但是对于小型的数组，其性能比较好。

归并排序

把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数（分）。把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组（合）。

怎么合并两个数组？新建一个空数组用于存放最后排序后的数组。比较两个有序数组的头部，较小者出队并推入新建数组中，如果两个数组还有值，就重复第二步。

javascript

Array.prototype.mergeSort = function() {
    const rec = (arr) => {
        if(arr.length === 1) return arr;
        const mid = Math.floor(arr.length / 2)
        const left = arr.slice(0, mid);
        const right = arr.slice(mid, arr.length);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        const res = [];
        while(orderLeft.length || orderRight.length) {
            if(orderLeft.length && orderRight.length) {
                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
            } else if(orderLeft.length) {
                res.push(orderLeft.shift());
            } else if(orderRight.length) {
                res.push(orderRight.shift());
            }
        }
        return res;
    }
    const res =  rec(this);
    res.forEach((n, i) => {
        this[i] = n;
    })
}
const arr = [5, 4, 3, 1, 2];
arr.mergeSort();
console.log(arr);

归并排序的时间复杂度为O(logN)（分）+ O(n)（合）= O(n * logN)。

快速排序

从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面（分区）。递归地对基准前后的子数组进行分区（递归）。

javascript

Array.prototype.quickSort = function() {
    const rec = (arr) => {
        if(arr.length <= 1) return arr;
        const left = [];
        const right = [];
        const mid = arr[0];
        for(let i = 1; i < arr.length; i++) {
            if(arr[i] < mid) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return [...rec(left), mid, ...rec(right)];
    };
    const res = rec(this);
    res.forEach((n, i) => {
        this[i] = n;
    })
}

const arr = [5, 4, 3, 1, 2];
arr.quickSort();
console.log(arr);

递归的时间复杂度为O(logN)，分区的复杂度是O(n)，总共的时间复杂度为O(n * logN)。

搜索算法

搜索算法包括顺序搜索和二分搜索。

顺序搜索

先遍历数组，然后找到跟目标值相等的元素，就返回它的下标。遍历结束后没有找到搜索的目标值就返回-1。

javascript

Array.prototype.sequentialSearch = function(target) {
    for(let i = 0; i < this.length; i++) {
        if(this[i] === target) {
            return i;
        }
    }
    return -1;
}
const res = [1, 3, 4, 2, 5].sequentialSearch(3);
console.log(res);

遍历数组是一个循环操作，时间复杂度为O(n)。

二分搜索

从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索。

javascript

Array.prototype.binarySearch = function(target) {
    // 保证有序  从小到大
    // this.sort();
    let low = 0;
    let high = this.length - 1;
    while(low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = this[mid];
        if(element < target) {
            low = mid + 1;
        } else if(element > target) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
const res = [1, 2, 3, 4, 5].binarySearch(4);
console.log(res);

该算法的时间复杂度为O(logN)，每一次搜索都使搜索范围减小一半。

推荐题目：力扣第21、374题

分而治之

分而治之是算法设计中的一种方法。它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。其常见的使用场景有：

归并排序
快速排序
二分搜索
翻转二叉树
......

推荐题目：力扣第374、226、100、101题

动态规划

动态规划是算法设计中的一种方法。将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。具体体现有：斐波那契数列问题。

和分而治之的区别在于：子问题是否独立。如果独立就是分而治之，不独立就是动态规划。

推荐题目：第70、198题

贪心算法

贪心算法是算法设计中的一种方法。期盼能通过每个阶段的局部最优选择，从而达到全局的最优，结果不一定是最优。使用的负面场景有：

零钱兑换
天龙八部的珍珑棋局

推荐题目：力扣第455、122题

回溯算法

回溯算法是算法设计中的一种方法。是一种渐进式寻找并构建问题解决方式的策略。回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。使用情况为：有很多的假设，这些可能里有正确的假设也有错误的假设，需要使用递归。使用场景有：

全排列
子集
......

推荐题目：力扣第46、78题

数据结构 #

栈 #

JS中的函数调用堆栈 #

队列 #

js异步中的任务队列 #

链表 #

JS中的原型链 #

面试题1 #

面试题2 #

获取JSON的节点值 #

集合 #

Set操作 #

字典 #

树 #

深度/广度优先遍历 #

二叉树的先中后序遍历 #

先序遍历 #

中序遍历 #

后序遍历 #

遍历JSON的所有节点值 #

图 #

深度与广度优先遍历 #

堆 #

第k个最大元素 #

实现最小堆类 #

排序和搜索 #

排序算法 #

冒泡排序 #

选择排序 #

插入排序 #

归并排序 #

快速排序 #

搜索算法 #

顺序搜索 #

二分搜索 #

分而治之 #

动态规划 #

贪心算法 #

回溯算法 #

数据结构

栈

JS中的函数调用堆栈

队列

js异步中的任务队列

链表

JS中的原型链

面试题1

面试题2

获取JSON的节点值

集合

Set操作

字典

树

深度/广度优先遍历

二叉树的先中后序遍历

先序遍历

中序遍历

后序遍历

遍历JSON的所有节点值

图

深度与广度优先遍历

堆

第k个最大元素

实现最小堆类

排序和搜索

排序算法

冒泡排序

选择排序

插入排序

归并排序

快速排序

搜索算法

顺序搜索

二分搜索

分而治之

动态规划

贪心算法

回溯算法