时间复杂度与空间复杂度

数据类型

数组, 链表, 跳表

链表查询 O(n) 优化: 跳表查询 O(logn), 核心: 空间换时间, 升维

跳表
原始链表 ○ -> ○ …
第一级索引 ○ -> -> ○ …
第二级索引 ○ -> -> -> -> ○ …
…
(对于 n 个元素, 增加 log2(n) 级索引)

跳表的工程应用: LRU 缓存, Redis

栈, 队列

栈
先入后出
队列
先入先出
双端队列
头部插入 unshift
头部删除 shift
尾部插入 push
尾部删除 pop
优先队列
插入 O(1), 按元素优先级取出 O(logn)
底层实现多样且复杂, 如 heap(堆), bst(二叉搜索树)
相关算法套路
洋葱型问题 - 栈
用栈实现队列 - 两个栈
用队列实现栈 - 两个队列

哈希表 (散列表)

根据关键码值 (key) 通过映射函数 (hash function) 直接访问到表中的某个位置

哈希冲突: 映射函数的输出结果相同
拉链式解决冲突的方法: 同一个位置拉出链表存储多个内容

工程应用: map, set

树

链表是特殊化的树, 树是特殊化的图 (是否有环)

树节点的定义:

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

递归遍历树

前序遍历 (根-左-右) pre-order

function preorder(root) {
    if (root) {
        process(root.val);
        preorder(root.left);
        preorder(root.right);
    }
}

中序遍历 (左-根-右) in-order

function inorder(root) {
    if (root) {
        inorder(root.left);
        process(root.val);
        inorder(root.right);
    }
}

后序遍历 (左-右-根) post-order

function postorder(root) {
    if (root) {
        postorder(root.left);
        postorder(root.right);
        process(root.val);
    }
}

二叉搜索树 (BST)

BST 定义:
1. 左子树上所有节点的值均小于它的根节点的值
2. 右子树上所有节点的值均大于它的根节点的值
3. 以此类推: 左右子树也分别为二叉搜索树 (重复性)

BST 的中序遍历为升序排列, 其查询与增删的操作都是 O(lgn)

BST 删除节点 (非叶子节点):
1. 找到要删除的节点
2. 在该节点右子树找到最小值
3. 把最小值从原位置删除 (如果最小值不是叶子节点, 则递归), 替换到要删除的节点位置

平衡二叉树

在增删节点过程中保证二叉搜索树的二维结构, 确保其不会退化成一维链表

AVL 树 (平衡二叉树)

平衡因子: 左子树高度减去右子树高度的值在 -1, 0, 1 这个范围里

缺点: 1. 每个节点需要存储平衡因子这个额外信息 2. 调整次数频繁, 维护成本较高

通过旋转操作实现平衡:

右右子树 -> 左旋
A –(right)–> B –(right)–> C
变更为:
B –(left)–> A
–(right)–> C
左左子树 -> 右旋
A –(left)–> B –(left)–> C
变更为:
B –(left)–> C
–(right)–> A
左右子树 -> 左右旋
A –(left)–> B –(right)–> C
第一次左旋变更为:
A –(left)–> C –(left)–> B
第二次右旋变更为:
C –(left)–> B
–(right)–> A
右左子树 -> 右左旋
A –(right)–> B –(left)–> C
第一次右旋变更为:
A –(right)–> C –(right)–> B
第二次左旋变更为:
C –(left)–> A
–(right)–> B

红黑树 (近似平衡二叉树)

确保任何一个结点的左右子树高度差小于 2 倍

特征:
1. 每个结点非红即黑
2. 根结点是黑色的
3. 每个叶子结点 (空结点) 是黑色的
4. 不能有相邻的红色结点
5. 从任一结点到每个叶子结点的所有路径都包含相同数目的黑色结点

字典树 (Trie)

多叉树, 从根节点到叶子节点, 路径经过的字符连起来即构成单词

核心思想: 空间换时间

优点: 最大限度减少字符串比较, 查询效率高于哈希表 (利用字符串的公共前缀来降低查询时间的开销)

典型应用: 搜索引擎系统进行文本词频统计

并查集

典型应用: 朋友圈, 岛屿问题 (判断两个元素在不在一个集合里)

基本操作:
1. 初始化 parent[i] = i (也是领头元素的特征)
2. 找到元素 x 所在集合的领头元素
3. 合并 x, y 元素所在的两个集合 (x, y 所在集合不能相交)

class UnionSet {
    constructor() {
        this.count = 0;
        this.parent = [];
    }
    init(n) {
        this.count = n;
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }
    find(x) {
        // 寻找领头元素并进行路径压缩
        while(x !== this.parent[x]) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX === rootY) return;
        this.parent[rootX] = rootY; // 集合合并
        this.count--; // 独立集合数减一
    }
}

* 路径压缩:
d -> c -> b -> a <-> a 这样的一条集合, 找到 d 的领头元素 a, 同时完成了 d -> a, c -> a, b -> a 的路径压缩

算法

二分查找

适用性前提:
1. 单调递增或单调递减
2. 有上下界
3. 能够通过索引访问

let left = 0, right = arr.length - 1
while(left <= right) {
    const mid = (left + right) / 2 | 0; // 也可 const mid = left + (right - left) / 2 | 0;
    if (arr[mid] === target) break;     // 找到了
    if (arr[mid] < target) left = mid + 1;
    if (arr[mid] > target) right = mid - 1;
}

递归 - 通过函数体来进行的循环

数学归纳法分析, 找到最近最简方法, 将其拆解成可重复解决的问题 (重复子问题):
1. n = 1, n = 2 的简单场景成立
2. 假设 n 成立, 则 n + 1 也应成立

function recursion(level) {
    // recursion terminator 递归终结条件
    if (level > MAX_LEVEL) {
        process_result();
        return;
    }
    // process logic in current level 处理当前层逻辑
    process_this_level();
    // drill down 下探到下一层
    recursion(level + 1);
    // reverse the current level status if needed 清理当前层
    reverse_this_level();
}

分治

function divide_conquer(problem) {
    // recursion terminator
    if (problem == null) {
        process_result();
        return;
    }
    // prepare
    const subproblems = split_problem(problem);
    // conquer subproblems
    const subresults = subproblems.map(subproblem => {
        divide_conquer(subproblem);
    });
    // process and generate the final result
    process_result(subresults);
    // revert the current level states
}

回溯

采用试错的思想, 尝试分步解决问题. 当发现现有分步方式不能获得正确答案时, 则取消上一步或上几步继续尝试.

深度优先搜索

选一条支路下探走到底, 再向上回退走下一条

const visited = new Set();
function dfs(node) {
    // terminator
    if (visited.has(node)){
        return;
    }
    // process current node
    visited.add(node);
    process(node);
    // drill down
    node.children().map(child => {
        if (!visited.has(child)) {
            dfs(child);
        }
    })
}

非递归写法:

const visited = new Set();
function dfs(node) {
    // 递归栈
    const stack = [node];
    // 栈不为空则说明递归没有结束
    while (stack.length) {
        // 取出一个节点
        const job = stack.pop();
        // 添加访问标记
        visited.add(job);
        // 处理该节点
        process(job);
        // 将节点下层推入递归栈中
        job.children().map(child => {
            if (!visited.has(child)) {
                stack.push(child);
            }
        })
    }
}

广度优先搜索

逐层处理, 处理完当前层再向下处理下一层

const visited = new Set();
function bfs(node) {
    // 递归队列
    const queue = [node];
    // 队列不为空则说明递归没有结束
    while (queue.length) {
        // 取出一个节点
        const job = queue.unshift();
        // 添加访问标记
        visited.add(job);
        // 处理该节点
        process(job);
        // 将节点下层推入递归队列中
        job.children().map(child => {
            if (!visited.has(child)) {
                queue.push(child);
            }
        })
    }
}

牵强递归写法:

const visited = new Set();
function bfs(nodes) {
    let newNodes = [];
    while (nodes.length) {
        const node = nodes.pop();
        if (visited.has(node)) continue;
        // process current level
        visited.add(node);
        process(node);
        // prepare next level
        node.children().forEach(child => {
            newNodes.push(child);
        });
    }
    bfs(newNodes);
}

搜索优化

剪枝
实时判断节点有效性, 去除无效节点后续的搜索

双向搜索 (双向 BFS)

// 访问足迹
const visited = new Set();
// 双向扩散数组
const startList = [startNode];
const endList = [endNode];
while(!!startList.length && !!endList.length) {
    // 优先扩散元素少的一侧
    if (startList.length > endList.length) {
        const tempList = startList;
        startList = endList;
        endList = tempList;
    }
    // 单次扩散
    const newStartList = [];
    while(!!startList.length) {
        const node = startList.pop();
        if (visited.has(node)) return; // 双向扩散相遇了, 完成搜索
        // 处理当前访问元素, 扩散下一层
        visited.add(node);
        process(node);
        node.children().map(child => {
            newStartList.push(child);
        })
    }
    startList = newStartList;
}

启发式搜索 (A*)
确定合适的估价函数来判断优先级, 优先级高的先搜索

动态规划 - 动态递推

找到重复子问题, 计算局部最优解; 再通过递推, 不断淘汰次优解, 最终获得全局的最优解.

动态规划 vs 递归 (分治):
共性: 寻找重复性
差异: 最优子结构, 淘汰次优解

贪心

每一步选择都采取当下最优选择, 从而获得全局最优结果 (选择不能回退)

贪心算法的适用场景: 子问题的最优解可以递推到最终问题的最优解 (最优子结构)
例子: 零钱问题, 如果可选零钱具有整除关系则可用贪心, 否则只能回溯

几种算法对比:
贪心 - 局部最优判断, 不能回退
回溯 - 尝试所有可能, 可以回退
动规 - 局部最优判断 + 存储中间过程, 可回退

算法知识点总结