数据结构与算法

数据结构可视化

0. 基础概念

时间复杂度 (Time Complexity)

描述算法执行时间随数据规模增长的变化趋势。

• O(1): 常数时间 (Array 索引访问, Map get/set)
• O(log n): 对数时间 (二分查找)
• O(n): 线性时间 (遍历数组)
• O(n log n): 线性对数时间 (快速排序, 归并排序)
• O(n²): 平方时间 (冒泡排序, 双重循环)

空间复杂度 (Space Complexity)

描述算法执行过程中所需存储空间随数据规模增长的变化趋势。

---

1. 常见数据结构

1.1 栈 (Stack)

• 特性: 先入后出 (LIFO - Last In First Out)。
• 场景: 函数调用栈、浏览器历史记录 (前进/后退)、括号匹配。

const stack = [];
stack.push(1); // 入栈
stack.pop();   // 出栈

1.2 队列 (Queue)

• 特性: 先入先出 (FIFO - First In First Out)。
• 场景: 任务队列 (Event Loop)、消息队列。

const queue = [];
queue.push(1); // 入队
queue.shift(); // 出队

1.3 链表 (Linked List)

• 特性: 内存不连续，通过指针连接。增删快 (O(1))，查询慢 (O(n))。
• 场景: React Fiber 树的实现。

// 定义链表节点
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 反转链表 (LeetCode 206)
function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next; // 暂存后继
    curr.next = prev;       // 反转指针
    prev = curr;            // 推进 prev
    curr = next;            // 推进 curr
  }
  return prev;
}

1.4 树 (Tree)

• 二叉树 (Binary Tree): 每个节点最多有两个子节点。
• 二叉搜索树 (BST): 左子树 < 根节点 < 右子树。

// 二叉树遍历
const traverse = (root) => {
  if (!root) return;
  console.log(root.val); // 前序遍历位置
  traverse(root.left);
  // console.log(root.val); // 中序遍历位置 (BST 排序输出)
  traverse(root.right);
  // console.log(root.val); // 后序遍历位置
}

---

2. 排序算法

2.1 冒泡排序 (Bubble Sort)

• 思路: 两两比较，大的沉底。
• 复杂度: O(n²)

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

2.2 快速排序 (Quick Sort)

• 思路: 分治法。选基准值 (pivot)，小的放左边，大的放右边，递归。
• 复杂度: 平均 O(n log n)，最坏 O(n²)

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const mid = [];

  for (let num of arr) {
    if (num < pivot) left.push(num);
    else if (num > pivot) right.push(num);
    else mid.push(num);
  }
  
  return [...quickSort(left), ...mid, ...quickSort(right)];
}

2.3 归并排序 (Merge Sort)

• 思路: 分治法。先递归切分，再合并有序数组。
• 复杂度: 稳定 O(n log n)

---

3. 查找与搜索

3.1 二分查找 (Binary Search)

• 前提: 数组必须有序。
• 复杂度: O(log n)

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

3.2 深度优先搜索 (DFS)

• 思路: 一条路走到黑，撞墙回头。
• 实现: 递归 或 栈。

// 树的 DFS (递归)
function dfs(node) {
  if (!node) return;
  console.log(node.val); // 处理节点
  dfs(node.left);
  dfs(node.right);
}

3.3 广度优先搜索 (BFS)

• 思路: 层层递进。
• 实现: 队列 (Queue)。

function bfs(root) {
  if (!root) return;
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.val); // 处理节点
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

---

4. 常见算法思想

4.1 双指针 (Two Pointers)

• 场景: 链表判环、数组去重、两数之和 (有序数组)。
• 类型: 快慢指针、左右指针。

4.2 动态规划 (Dynamic Programming)

• 思路: 将大问题分解为小问题，并缓存小问题的解 (Memoization)。
• 示例: 斐波那契数列、爬楼梯。

// 爬楼梯 (LeetCode 70)
// 状态转移方程: f(n) = f(n-1) + f(n-2)
function climbStairs(n) {
  if (n <= 2) return n;
  let dp = [0, 1, 2];
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
// 优化空间版: 只需要记录前两个状态
function climbStairsOptimized(n) {
  if (n <= 2) return n;
  let prev1 = 1, prev2 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev1 = prev2;
    prev2 = curr;
  }
  return prev2;
}

4.3 贪心算法 (Greedy)

• 思路: 每一步都选择当前最优解，期望全局最优。
• 示例: 买卖股票的最佳时机 II。