清风自叙小筑

Appearance

算法面试速查表（25 题） ​

背诵口诀：先懂思路，再背代码，最后手写

一、数组（5 题）—— 双指针是核心 ​

1. 反转数组（双指针经典） ​

LeetCode 344 反转字符串（换皮，数组同理）

题目：给定一个字符数组或普通数组，将其原地反转。

示例：

输入：arr = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

约束：不要分配额外的数组空间，必须原地修改。

js
function reverseArray(arr) {
  let left = 0,
    right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}
  • 时间：O(n)｜空间：O(1)
  • 关键：双指针相向移动，相遇即停

2. 删除排序数组中的重复项（快慢指针） ​

LeetCode 26 Remove Duplicates from Sorted Array

题目：给定一个已排序的数组，原地删除重复元素，使每个元素只出现一次，返回新长度。不需要考虑数组中超出新长度后面的元素。

示例：

输入：nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
输出：5，nums 变为 [0, 1, 2, 3, 4, ...]

输入：nums = [1, 1, 2]
输出：2，nums 变为 [1, 2, ...]
js
function removeDuplicates(arr) {
  if (arr.length === 0) return 0;
  let slow = 0; // 慢指针 = 最后一个唯一元素位置
  for (let fast = 1; fast < arr.length; fast++) {
    if (arr[fast] !== arr[slow]) {
      slow++;
      arr[slow] = arr[fast];
    }
  }
  return slow + 1;
}
  • 时间：O(n)｜空间：O(1)
  • 关键：快指针探索，慢指针记录位置

3. 移除元素（快慢指针） ​

LeetCode 27 Remove Element

题目：给定一个数组和一个值 val，原地移除所有值为 val 的元素，返回新长度。元素顺序可以改变。

示例：

输入：nums = [3, 2, 2, 3], val = 3
输出：2，nums 前 2 个元素为 [2, 2]

输入：nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2
输出：5，nums 前 5 个元素为 [0, 1, 3, 0, 4]
js
function removeElement(arr, val) {
  let slow = 0;
  for (let fast = 0; fast < arr.length; fast++) {
    if (arr[fast] !== val) {
      arr[slow] = arr[fast];
      slow++;
    }
  }
  return slow;
}
  • 时间：O(n)｜空间：O(1)
  • 和上题对比：上题是去重（比较相邻），这题是删指定值（比较目标值）

4. 合并两个有序数组（双指针从后往前） ​

LeetCode 88 Merge Sorted Array

题目：给定两个非递减顺序排列的整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中。nums1 的长度为 m + n，前 m 个是有效元素，后 n 个用 0 占位。

示例：

输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出：[1, 2, 2, 3, 5, 6]

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
js
function merge(nums1, m, nums2, n) {
  let i = m - 1,
    j = n - 1,
    k = m + n - 1;
  while (i >= 0 && j >= 0) {
    nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
  }
  while (j >= 0) nums1[k--] = nums2[j--]; // nums2 有剩余
}
  • 时间：O(m + n)｜空间：O(1)
  • 关键：从后往前填，避免覆盖未处理的元素

5. 盛最多水的容器（双指针进阶） ​

LeetCode 11 Container With Most Water

题目：给定一个数组 height，每个元素代表一条垂直线的高度。找两条线，使其与 x 轴围成的容器能容纳最多水（面积 = 高度 × 宽度）。不能倾斜容器。

示例：

输入：height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
输出：49
解释：height[1]=8 和 height[8]=7 围成的面积 = 7 × 7 = 49，是最大值

输入：height = [1, 1]
输出：1
js
function maxArea(height) {
  let left = 0,
    right = height.length - 1,
    max = 0;
  while (left < right) {
    const h = Math.min(height[left], height[right]);
    const w = right - left;
    max = Math.max(max, h * w);
    // 总是移动较矮的一边
    if (height[left] < height[right]) left++;
    else right--;
  }
  return max;
}
  • 时间：O(n)｜空间：O(1)
  • 关键：宽在缩小，只有高度变高才可能面积更大 → 移动矮边

二、字符串（5 题） ​

1. 反转字符串 ​

LeetCode 344 Reverse String

题目：编写一个函数，将输入的字符数组原地反转。不要分配额外的数组空间。

示例：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
js
function reverseString(s) {
  return s.split("").reverse().join("");
}

// 原地反转字符数组（LeetCode 344 要求）
function reverseCharArr(s) {
  let l = 0,
    r = s.length - 1;
  while (l < r) {
    [s[l], s[r]] = [s[r], s[l]];
    l++;
    r--;
  }
}

2. 验证回文串 ​

LeetCode 125 Valid Palindrome

题目：如果在将所有大写字母转换为小写字母、并移除所有非字母数字字符之后，正着读和反着读一样，就认为它是回文串。返回 true 或 false。

示例：

输入：s = "A man, a plan, a canal: Panama"
输出：true（简化后为 "amanaplanacanalpanama"）

输入：s = "race a car"
输出：false（简化后为 "raceacar"）

输入：s = " "
输出：true（空串视为回文）
js
function isPalindrome(s) {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  return cleaned === cleaned.split("").reverse().join("");
}

// 双指针版（O(1) 空间，面试加分）
function isPalindrome2(s) {
  let l = 0,
    r = s.length - 1;
  while (l < r) {
    while (l < r && !/[a-zA-Z0-9]/.test(s[l])) l++;
    while (l < r && !/[a-zA-Z0-9]/.test(s[r])) r--;
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++;
    r--;
  }
  return true;
}

3. 最长公共前缀 ​

LeetCode 14 Longest Common Prefix

题目：查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例：

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""
js
function longestCommonPrefix(strs) {
  if (!strs.length) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, -1); // 截短一位
      if (!prefix) return "";
    }
  }
  return prefix;
}
  • 关键：以第一个为基准，不断截短直到所有人开头都匹配

4. 字符串查找（实现 strStr） ​

LeetCode 28 Find the Index of the First Occurrence in a String

题目：在字符串 haystack 中查找字符串 needle 第一次出现的位置（下标从 0 开始）。如果不存在则返回 -1。如果 needle 是空串，返回 0。

示例：

输入：haystack = "sadbutsad", needle = "sad"
输出：0（"sad" 开头就匹配）

输入：haystack = "leetcode", needle = "leeto"
输出：-1（找不到）
js
function strStr(haystack, needle) {
  if (!needle) return 0;
  const n = haystack.length,
    m = needle.length;
  for (let i = 0; i <= n - m; i++) {
    if (haystack.slice(i, i + m) === needle) return i;
  }
  return -1;
}

5. 替换空格 ​

LCR 122 路径加密（原 剑指 Offer 05）

题目：将字符串中的每个空格替换成 "%20"。常用于 URL 编码。

示例：

输入：s = "We are happy."
输出："We%20are%20happy."

输入：s = "  hello  "
输出："%20%20hello%20%20"
js
function replaceSpace(s) {
  return s.replace(/ /g, "%20");
  // 或：s.split(' ').join('%20');
}

三、HashMap（5 题）—— Map 是万能工具 ​

1. 两数之和（必背中的必背） ​

LeetCode 1 Two Sum

题目：给定一个整数数组 nums 和一个整数目标值 target，在数组中找出和为目标值的两个整数，返回它们的下标。每种输入只会对应一个答案，且同一元素不能使用两遍。

示例：

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]（因为 2 + 7 = 9）

输入：nums = [3, 2, 4], target = 6
输出：[1, 2]

输入：nums = [3, 3], target = 6
输出：[0, 1]
js
function twoSum(nums, target) {
  const map = new Map(); // 值 -> 下标
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
  return [];
}
  • 时间：O(n)｜空间：O(n)
  • 关键：Map 记录"已看过的值"，O(1) 查补数

2. 字符频率统计（基础模板） ​

用途：很多字符串题的共用模板。不单独作为 LeetCode 题，但几乎是所有 HashMap 题的前置知识。

题目：统计字符串中每个字符出现的次数。

js
function charFreq(s) {
  const map = new Map();
  for (const c of s) {
    map.set(c, (map.get(c) || 0) + 1);
  }
  return map;
}

记忆点：map.get(c) || 0 是处理"不存在"的万能写法

3. 第一个不重复的字符 ​

LeetCode 387 First Unique Character in a String

题目：给定一个字符串，找到它的第一个不重复的字符，并返回它的下标。如果不存在，返回 -1。

示例：

输入：s = "leetcode"
输出：0（'l' 只出现一次，且在最前面）

输入：s = "loveleetcode"
输出：2（'v' 只出现一次，下标 2）

输入：s = "aabb"
输出：-1（没有不重复的字符）
js
function firstUniqChar(s) {
  const freq = new Map();
  for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
  for (let i = 0; i < s.length; i++) {
    if (freq.get(s[i]) === 1) return i;
  }
  return -1;
}
  • 关键：两遍遍历——第一遍统计，第二遍查找

4. 有效的字母异位词 ​

LeetCode 242 Valid Anagram

题目：给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词（字母相同，排列不同）。

示例：

输入：s = "anagram", t = "nagaram"
输出：true

输入：s = "rat", t = "car"
输出：false

输入：s = "ab", t = "a"
输出：false（长度不同直接返回）
js
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Map();
  for (const c of s) count.set(c, (count.get(c) || 0) + 1);
  for (const c of t) {
    if (!count.has(c)) return false;
    count.set(c, count.get(c) - 1);
    if (count.get(c) < 0) return false;
  }
  return true;
}
  • 时间：O(n)｜空间：O(k)，k 为字符集大小
  • 关键：s 加、t 减，最终 count 全为 0 才是异位词

5. 多数元素（摩尔投票法） ​

LeetCode 169 Majority Element

题目：给定一个大小为 n 的数组，找到其中的多数元素（出现次数 > n/2 的元素）。可以假设数组非空且多数元素一定存在。

示例：

输入：nums = [3, 2, 3]
输出：3

输入：nums = [2, 2, 1, 1, 1, 2, 2]
输出：2
js
function majorityElement(nums) {
  let candidate = nums[0],
    count = 1;
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      candidate = nums[i];
      count = 1;
    } else if (nums[i] === candidate) {
      count++;
    } else {
      count--;
    }
  }
  return candidate;
}
  • 时间：O(n)｜空间：O(1)
  • 关键：相同的 +1，不同的 -1，count 归零就换候选人

四、树（5 题）—— 递归是核心 ​

树节点定义 ​

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

1. 前序遍历（根 → 左 → 右） ​

LeetCode 144 Binary Tree Preorder Traversal

题目：按照"根 → 左 → 右"的顺序遍历二叉树，返回节点值数组。

示例：

    1
     \
      2
     /
    3
输入：[1, null, 2, 3]
输出：[1, 2, 3]（根 1 → 右 2 → 左 3）
js
// 递归版
function preorder(root, result = []) {
  if (!root) return result;
  result.push(root.val);
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

// 迭代版（用栈）
function preorderIter(root) {
  if (!root) return [];
  const stack = [root],
    result = [];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.right) stack.push(node.right); // 先右后左！
    if (node.left) stack.push(node.left);
  }
  return result;
}

2. 中序遍历（左 → 根 → 右） ​

LeetCode 94 Binary Tree Inorder Traversal

题目：按照"左 → 根 → 右"的顺序遍历二叉树。

示例：

    1
     \
      2
     /
    3
输入：[1, null, 2, 3]
输出：[1, 3, 2]（左 1 → 根... 等等，这里 1 是根，右子树的左 3 → 根 2）
js
function inorder(root, result = []) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

重点：BST 中序遍历得到升序数组（高频考点）

3. 后序遍历（左 → 右 → 根） ​

LeetCode 145 Binary Tree Postorder Traversal

题目：按照"左 → 右 → 根"的顺序遍历二叉树。

js
function postorder(root, result = []) {
  if (!root) return result;
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.val);
  return result;
}

记忆口诀：前中后 = "根"在输出中的位置

4. 层序遍历（BFS，用队列） ​

LeetCode 102 Binary Tree Level Order Traversal

题目：从上到下、从左到右逐层遍历二叉树，返回一个二维数组，每一层是一个数组。

示例：

      3
     / \
    9  20
       / \
      15  7
输入：[3, 9, 20, null, null, 15, 7]
输出：[[3], [9, 20], [15, 7]]
js
function levelOrder(root) {
  if (!root) return [];
  const queue = [root],
    result = [];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}
  • 关键：用队列，每轮 levelSize 固定当前层节点数

5. 二叉树最大深度 ​

LeetCode 104 Maximum Depth of Binary Tree

题目：给定一个二叉树，找出其最大深度（根节点到最远叶子节点的路径上的节点数）。

示例：

      3
     / \
    9  20
       / \
      15  7
输入：[3, 9, 20, null, null, 15, 7]
输出：3
js
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

一行代码也要会写——这是递归思维的代表作

五、排序（2 题，必须手写） ​

1. 快速排序 ​

题目：实现快速排序算法。核心思想：选基准 → 分区 → 递归。

示例：

输入：[3, 6, 2, 1, 5, 4]
输出：[1, 2, 3, 4, 5, 6]
js
// 简洁版（非原地，面试讲解用）
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [],
    right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 原地版（面试常考，必须会）
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
  if (low >= high) return arr;
  const p = partition(arr, low, high);
  quickSortInPlace(arr, low, p - 1);
  quickSortInPlace(arr, p + 1, high);
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high]; // 取最右为基准
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}
  • 时间：平均 O(n log n)，最坏 O(n²)｜空间：O(log n)
  • 三步：选基准 → 分区 → 递归

2. 归并排序 ​

题目：实现归并排序算法。核心思想：分治 + 合并两个有序数组。

示例：

输入：[3, 6, 2, 1, 5, 4]
输出：[1, 2, 3, 4, 5, 6]
js
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0,
    j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}
  • 时间：O(n log n)（稳定排序）｜空间：O(n)
  • 两步：分治 + 合并两个有序数组

六、简单 DP（3 题）—— 状态转移是核心 ​

DP 三步法 ​

  1. 定义状态：dp[i] 代表什么？
  2. 转移方程：dp[i] 和 dp[i-1] 的关系
  3. 初始值：dp[0]、dp[1] 是多少？

1. 爬楼梯 ​

LeetCode 70 Climbing Stairs

题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次可以爬 1 或 2 个台阶。有多少种不同的方法爬到楼顶？

示例：

输入：n = 2
输出：2（1+1 或 2）

输入：n = 3
输出：3（1+1+1、1+2、2+1）
js
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1,
    prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
  • 转移方程：dp[i] = dp[i-1] + dp[i-2]
  • 关键：到第 i 阶 = 从 i-1 爬 1 步 + 从 i-2 爬 2 步

2. 斐波那契数列 ​

LeetCode 509 Fibonacci Number

题目：计算斐波那契数列 F(n)。F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。

示例：

输入：n = 2 → 输出：1
输入：n = 3 → 输出：2
输入：n = 4 → 输出：3
js
function fib(n) {
  if (n <= 1) return n;
  let prev = 0,
    curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}
  • 转移方程：dp[i] = dp[i-1] + dp[i-2]（和爬楼梯一模一样）
  • 关键：只用两个变量滚动，不用数组（空间 O(1)）

3. 最大子数组和 ​

LeetCode 53 Maximum Subarray

题目：给定一个整数数组，找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6（子数组 [4, -1, 2, 1] 的和最大）

输入：nums = [1]
输出：1

输入：nums = [5, 4, -1, 7, 8]
输出：23
js
function maxSubArray(nums) {
  let maxSum = nums[0],
    currSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // 延续前面的和 vs 从当前重新开始
    currSum = Math.max(nums[i], currSum + nums[i]);
    maxSum = Math.max(maxSum, currSum);
  }
  return maxSum;
}
  • 转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
  • 关键：前面累加是负贡献就扔掉，从当前重新开始

背诵节奏（两周计划） ​

时间内容每天投入
第 1-3 天数组 5 题 + 字符串 5 题1 小时
第 4-7 天HashMap 5 题 + 树 5 题1 小时
第 8-10 天排序 2 题（手写熟练）+ DP 3 题1 小时
第 11-14 天综合复习 + 模拟手写1 小时

背诵四步法 ​

  1. 看懂思路（5 分钟）—— 不要急着写
  2. 关掉答案手写（10 分钟）—— 写不出来再看
  3. 对答案找错（5 分钟）—— 边界、变量名、逻辑
  4. 隔天再写一遍（5 分钟）—— 巩固记忆

验收标准 ​

  • 每题能在 5 分钟内白板手写完成
  • 边写边说思路（模拟面试）
  • 主动说时间 / 空间复杂度

面试现场技巧 ​

答题四步走 ​

  1. 复述题目（30 秒）—— 确认理解
  2. 说思路（1 分钟）—— "我打算用双指针 / HashMap / DP..."
  3. 写代码（5-10 分钟）—— 边写边说
  4. 跑用例 + 说复杂度（1 分钟）—— 主动收尾

高频边界（必说） ​

  • 空数组 / 空字符串
  • 单个元素
  • 全相同 / 全不同
  • 负数 / 0
  • 越界情况

万能开场白 ​

"这道题我用 XX 方法，核心思路是 YY，时间复杂度 O(?)，空间复杂度 O(?)，我开始写代码。"

高频考点速记表 ​

类型标志词解法
双指针"有序" "反转" "去重" "回文"相向 / 同向双指针
HashMap"找两个" "频率" "重复" "异位词"Map 存值 / 计数
BFS"层序" "最短" "最少步数"队列
DFS"所有路径" "排列组合" "深度"递归 / 栈
快排"排序" + "原地在"partition + 递归
归并"排序" + "稳定"分治 + merge
DP"多少种方法" "最大/最小" "最优"状态 + 转移方程

加油，2 周够了。背完这 25 题，深圳中厂算法关基本稳过。