Skip to content

README.md

Latest commit

 

History

History
736 lines (604 loc) · 21 KB

README.md

File metadata and controls

736 lines (604 loc) · 21 KB

常用算法与数据结构

参考

目录

展开更多

总纲

题集

基础数据结构

只有两种：数组（顺序存储）和链表（链式存储）

队列、栈、哈希表扩展自数组

树、堆、图扩展自链表

线性非线性

线性: for/while/forEach

非线性: 递归

时间复杂度

常用的JS 数组内置函数

O(1)

  • array.push
  • array.pop
  • array.shift

O(n)

  • array.unshift
  • array.slice
  • array.splice
  • 数组中查找/删除某个元素

O(logn)

  • 二叉搜索

复杂度计算 - 推导大O阶

  • 子问题个数乘以解决一个子问题需要的时间
  • 用常数1来取代运行时间中所有加法常数。
  • 修改后的运行次数函数中，只保留最高阶项
  • 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

复杂度对比

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

普通数组

常用技巧

  1. 前缀和
    • s[0]=0
    • s[i+1] = nums[0] + nums[1] + ⋯ + nums[i]
    • s[i] - s[j]: 序号i到j之间的总和

习题

二叉树

结构：value、left、right

空间复杂度：

  • dfs - O(h)

  • bfs - O(w)

遍历方式：

  • 先序遍历：考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。

    • 访问顺序：根节点 → 左子树 → 右子树
    • 常用：层级遍历、右视图

  • 中序遍历：考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树，即深度遍历。

    • 访问顺序：左子树 → 根节点 → 右子树
    • 常用：排序、找最小

  • 后序遍历：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。

    • 访问顺序：左子树 → 右子树 → 根节点

    • 常用：求直径

解题思路：

  • 分治：后序遍历，问题不断分解为left和right问题

  • 回溯：先序遍历，处理完当层问题，再解决下层

模板

队列遍历

const fn = () => {
  const queue = [root];
  while (queue.length) {
    let len = queue.length;
    const temp = [];
    while (len--) {
      const node = queue.shift();
      temp.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(temp);
  }
};

习题

结构

class Node {
  constructor(data, left, right) {}
}

class Tree {
  constructor(root) {}
  // 根据【概念2】插入节点
  insert(node) {}
  // 获取最左子节点
  getMin() {}
  // 获取最右子节点
  getMax() {}
  // 查找特定node
  getNode(data, node) {}
  // 获取特定节点的深度（左、右子树的最大深度）
  getDeep(node, deep) {}
}

链表

节点结构：

  • 数据：value

  • 指针：pre、next

  • 头尾指针：head、tail

适用场景：

  • 高频插入删除：操作栈、队列

  • 动态数据：内存、文件系统

  • 算法问题：LRU、大数相加

模板

class Node {
    constructor() {
        this.value = null;
        this.pre = null;
        this.next = null;
    }
}


class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

习题

dp

理念：识别子问题 + 设计状态转移方程

核心思路：

  • dp含义：总量是i，最小/少是dp[i]

  • 递推公式：子问题如何推到出更大问题的解，比如dp[i] = dp[i - 1] + dp[i - 2] + ...

  • 初始化状态：dp[0] = 0、dp[1] = 1等

  • 遍历顺序：Math.max(...dp[n])

  • 遍历方式：如果是一维数组，可选项在外层，总量在内层；如果是二维数组，则两者可交换

  • 打印结果：dp[i]

习题

图论

概念

  • 顶点 + 边

存储方式：

  • 朴素存储：一维数组、哈希

  • 邻接表：适合稀疏图，哈希（key是顶点，value是边的集合）

  • 邻接矩阵：适合稠密图，二维数组

模板

广度搜索

适合最短路径、层级遍历、连通检测

function bfs (graph, start) {
    const queue = [start];
    const visited = new Set();
    visited.add(start);
    while (queue.length) {
      const vertex = queue.shift();
      for (const neighbor of graph.vertices.get(vertex)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
}

深度搜索

检测环、路径存在、拓扑排序

function dfs (graph, start) {
    const queue = [start];
    const visited = new Set();
    visited.add(start);
    while (queue.length) {
      const vertex = queue.pop();
      for (const neighbor of graph.vertices.get(vertex)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
}

习题

技巧

习题

遍历方式

先序遍历实现

var preorderTraversal = function (root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      result.push(current.val);
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    current = current.right;
  }
  return result;
};

中序遍历实现

var inorderTraversal = function (root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    // 左子树优先入栈
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    // 右节点再入栈
    current = current.right;
  }
  return result;
};

后序遍历实现

var postorderTraversal = function (root) {
  const result = [];
  const stack = [];
  let last = null; // 标记上一个访问的节点
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack[stack.length - 1];
    if (!current.right || current.right == last) {
      current = stack.pop();
      result.push(current.val);
      last = current;
      current = null; // 继续弹栈
    } else {
      current = current.right;
    }
  }
  return result;
}

哈希

特性：键值存储，常用于两数之和、统计次数、memorize

数据类型：Map、Set

时间复杂度：O(1)

习题

栈

特性：只能在栈顶push和pop，遵循后进先出

时间复杂度：O(1)

边界条件：空栈、栈溢出（无限递归）

习题

回溯

即dfs

目标：在决策树中穷举所有可能性

路径选择：

  • 选择：每步一个选择

  • 递归：当前选择进入下个回溯

  • 撤销：回退上个状态，尝试其他可能性

循环条件：

  • 起始点统一，循环体在回溯函数内

  • 起始点不统一，循环体包在回溯函数外

终止条件：当前路径满足条件，保存结果，返回

剪枝：预排除不满足条件的分支

模板

function backtrack(路径, 选择列表) {
  if (满足终止条件) {
    保存结果;
    return;
  }

  for (const 选择 of 选择列表) {
    if (当前选择不合法) continue; // 剪枝

    做选择;      // 将选择加入路径
    backtrack(路径, 新选择列表); // 递归
    撤销选择;    // 从路径中移除选择（回溯）
  }
}

习题

二分查找

前提条件：数组必须有序

确定边界：初始化左右指针，left=0，right=数组length - 1

循环缩小范围：

  • 中间元素：mid = left + (right - left ) >> 1

  • 匹配到目标值：返回index

  • 目标值小于中间元素：left = mid + 1

  • 目标值大于中间元素：right = mid - 1

循环条件：

  • left和right同时+1-1移动时：left <= right

  • left和right某个+1-1移动时：left < right

终止条件：left > right

习题

双指针

类型：

  • 同向指针：快慢指针同速移动

  • 反向指针：收尾向中间移动

  • 快慢指针：快慢指针以不同速移动（比如2倍）

特点：适合线性、有序（或部分有序）的数据结构

空间复杂度优化：O(n) -> O(1)

习题

贪心算法

理念：每一步都是当前最优解，合起来是全局最优解

适用场景：排序好的数组、遍历

习题

滑动窗口

定义：用left和right表示窗口的左右边界

移动策略：

  • 扩大窗口：right不断右移，直至窗口满足条件

  • 收缩窗口：left不断右移，直至窗口不再满足条件

状态存储：哈希

注意点：

  • 有可变窗口和固定窗口

  • 剪支、边界

模板

function slideWindow(字符串, 目标) {
    let left = 0;
    let right = 0;
    let len = 字符串.length;
    const result = 结果;
    while (right < len) {
        right++;
        while (满足条件) {
            记录结果
            left++;
        }
    }
    return 结果;
}

习题

习题

目录