算法问题详解

时间复杂度

时间复杂度是指执行这个算法所需要的计算工作量，其复杂度反映了程序执行时间随输入规模增长而增长的量级

• 大 O 计算法 算法的复杂度通常用大 O 符号表述，定义为 T(n) = O(f(n))

常数型 O(1)
对数型 O(log n)
线性型 O(n)
线性对数型 O(n log n)
多项式型 平方型 O(n^2)、立方型 O(n^3)、K 次方型 O(n^k)
指数型 平方底指数型 O(2^n)、立方底指数型 O(3^n)、K 次底指数型 O(k^n)
阶乘型 O(n!)

• 时间复杂度只关注最高数量级，且与之系数也没有关系。

• 时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析;如果遇到函数调用，就要深入函数进行分析。

1. 算法执行所需要的临时空间，不随着变量大小而变化，空间复杂度为一个常量，可以表示为 O(1)

• 暴力枚举，二分查找，双指针，哈希表

空间复杂度

算法的空间复杂度指的是在运行过程中临时占用的存储空间大小的量度

• 代码所占用的空间：与算法本身的书写长短有关
• 输入数据所占用的空间：调用函数时传递而来，与算法本身无关
• 辅助变量所占用的空间

一个算法的空间复杂度只考虑在运行过程中为局部变量所分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间、在函数体中定义的局部变量分配的存储空间两个部分

时间复杂度和空间复杂度仅仅代表了一种趋势，是一种预估; 好的算法往往更注重时间复杂度，空间复杂度在一个合理的范围即可~

二叉树

二叉树是由根节点，左子树，右子树组成，左子树和右子树分别是一个二叉树。

class TreeNode {
    value: number
    left?: TreeNode
    right?: TreeNode
    constructor(value: number, left?: TreeNode, right?: TreeNode){
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

• 广度优先遍历（BFS）

广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

• 递归遍历/深度优先遍历（DFS）

D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。

1. 先序遍历：DLR
2. 中序遍历：LDR
3. 后序遍历：LRD

    D
L       R

Q: 后序遍历更好用？

前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

图

图真的没啥高深的，本质上就是个高级点的多叉树而已，适用于树的 DFS/BFS 遍历算法，全部适用于图。

// 图
class Vertex {
    id: number
    neighbors: Vertex[] // 邻接节点
}


// 多叉树
class TreeNode {
    value: number
    children: TreeNode[]
}

用邻接表和邻接矩阵的存储图。

• 空间复杂度

1. 邻接表： O(E)
2. 邻接矩阵：O(V^2)

• 邻接表，好处是占用的空间少, 邻接表无法快速判断两个节点是否相邻。

度

在无向图中，「度」就是每个节点相连的边的条数。

由于有向图的边有方向，所以有向图中每个节点「度」被细分为入度（indegree）和出度（outdegree）.

图的遍历

各种数据结构被发明出来无非就是为了遍历和访问，所以「遍历」是所有数据结构的基础。

type Graph = number[][]
const graph: Graph = [
    [4, 3, 1],  // 表示 0 到 4 , 0 到 3 ， 0 到 1 各有一条边
    [3, 2, 4],  // 表示 1 到 3 , 1 到 2 ， 1 到 4 各有一条边
    [3],        // 表示 2 到 3 有一条边
    [4],        // 表示 3 到 4 有一条边
    []          // 没有从4出去的边
]

• DFS

图和多叉树最大的区别是，图是可能包含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点，而树不会出现这种情况，从某个节点出发必然走到叶子节点，绝不可能回到它自身。

二叉树算是特殊的图。

// 记录被遍历过的的节点  
let visited: boolean[] = [];  
// 记录从起点到当前节点的路径  
let onPath: boolean[] = [];  
  
/* 图遍历框架 */  
function traverse(graph: Graph , s: number): void {  
    if (visited[s]) return;  
    // 经过节点 s，标记为已遍历  
    visited[s] = true;  
    console.log(s)
    // 做选择：标记节点 s 在路径上  
    onPath[s] = true;  
    for (let neighbor of graph[s]) {  
        traverse(graph, neighbor);  
    }  
    // 撤销选择：节点 s 离开路径  
    onPath[s] = false;  
}

• BFS

备注

• js手写一个二叉树，手写前序遍历，中序遍历，后序遍历？

class TreeNode {
    constructor(public value: number, public left?: TreeNode, public right?: TreeNode) { }
}

const node3 = new TreeNode(3)
const node4 = new TreeNode(4)
const node7 = new TreeNode(7)
const node6 = new TreeNode(6, node7)
const node2 = new TreeNode(2, node3, node4)
const node5 = new TreeNode(5, node6)
const node1 = new TreeNode(1, node2, node5)


// 广度优先遍历
function bfs(root: TreeNode) {
    const queue = new Array<TreeNode>()
    queue.push(root)

    while (queue.length) {
        const size = queue.length
        for (let i = 0; i < size; i++) {
            const curr = queue.shift()!
            // 访问当前元素
            console.log(curr.value)
            if (curr.left) {
                queue.push(curr.left)
            }
            if (curr.right) {
                queue.push(curr.right)
            }
        }
        console.log("------------")
    }
}

// bfs(node1)

// 先序遍历：DLR
function preOrder(root?: TreeNode) {
    if (!root) return
    console.log(root.value)
    preOrder(root.left)
    preOrder(root.right)
}


// 中序遍历：LDR
function inOrder(root?: TreeNode) {
    if (!root) return
    inOrder(root.left)
    console.log(root.value)
    inOrder(root.right)
}

// inOrder(node1)

// 后序遍历：LRD
function postOrder(root?: TreeNode) {
    if (!root) return
    postOrder(root.left)
    postOrder(root.right)
    console.log(root.value)
}


function framework(root?: TreeNode) {
    if (!root) return
    // 先序位置
    postOrder(root.left)
    // 中序位置
    postOrder(root.right)
    // 后序位置
}
// postOrder(node1)


// BFS计算二叉树最大深度
function maxDepthBFS(root: TreeNode | null) {
    if (!root) return 0

    const queue = new Array<TreeNode>()
    queue.push(root)
    let height = 0

    while (queue.length) {
        const size = queue.length
        for (let i = 0; i < size; i++) {
            const curr = queue.shift()!
            // 访问当前元素
            // console.log(curr.value)
            if (curr.left) {
                queue.push(curr.left)
            }
            if (curr.right) {
                queue.push(curr.right)
            }
        }
        height++
    }
    return height
}

// DFS计算最大深度
function maxDepthDFS(root: TreeNode | null) {
    return help(root ?? undefined)
}
function help(root?: TreeNode): number {
    if (!root) return 0
    return Math.max(help(root.left), help(root.right)) + 1
}


// 计算二叉树直径：任意两个节点间最大长度
let len = 0
function diameterOfBinaryTree(root: TreeNode | null): number {
    len = 0
    help2(root ?? undefined)
    return len - 1
};

function help2(root?: TreeNode): number {
    if (!root) return 0
    const lh = help2(root.left)
    const rh = help2(root.right)
    len = Math.max(len, lh + rh + 1)
    return Math.max(lh, rh) + 1
}

console.log(diameterOfBinaryTree(node1))

• 图的遍历：DFS遍历，DFS遍历？ 邻接表和邻接矩阵？

• 动态规划？

收藏

• leetcode (opens new window)

• 310. 最小高度树 (opens new window)

• 15. 三数之和 (opens new window)

• 常见面试题详解 (opens new window)

• 常见面试题详解 更新版 (opens new window)

参考

• 算法入门：树，图 (opens new window)

• 常见算法 (opens new window)