简单点

Appearance

必知必会 ​

  • 二叉树
    1. 前中后序遍历
    2. 层序遍历
  • 链表
    1. 反转链表
    2. 合并两个有序链表
    3. 是否有环（环入口）
  • 回溯
    1. 全排列
    2. 子集
    3. 组合总和
  • 排序查找
    1. 快排
    2. 二分查找
  • 数组
    1. 两数之和
    2. 三数之和
    3. 无重复字符的最长子串（lengthOfLongestSubstring）
    4. 盛最多水的容器
    5. 最长回文子串
    6. 旋转矩阵
    7. 螺旋矩阵
    8. 字符串压缩
    9. 数组中重复的数据
    10. 长度最小的子数组（minSubArrayLen）
  • 动态规划：
    1. 爬楼梯
    2. 最大子数组合（maxSubArray）
    3. 买卖股票
    4. 零钱兑换
    5. 不同路径（uniquePaths）
    6. 打家劫舍
    7. 最长递增子序列（lengthOfLIS）
    8. 字符串相关的有
      • 最长公共子序列（longestCommonSubsequence）
      • 单词拆分
      • 编辑距离
    9. 可被三整除的最大和
    10. 打家劫舍二（环状）
  • 手写
    1. 进制转换
  • 设计
    1. LRU
    2. Trie

LIS ​

  • 维护数组 tails，tails[i] 表示长度为 i+1 的递增子序列的最小末尾。
  • 遍历 nums，对每个 num 用二分找到 tails 中第一个 ≥ num 的位置并替换
  • tails 长度即为答案；注意 tails 不一定是真实的 LIS

编辑距离 ​

dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数

边界

dp[0][j] = j（word1 为空，全靠插入）
dp[i][0] = i（word2 为空，全靠删除）

说明

dp[i-1][j],     // 删除 word1 一个字符
dp[i][j-1],     // 在 word1 插入一个字符
dp[i-1][j-1]    // 替换 word1 一个字符

rob & maxSubArray ​

  • rob 是不连续，prev2 prev1 交替前进，5行核心代码
  • maxSubArray 是连续的，用 cur max 记录当下最优和全局最优，4行核心代码
js
function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let prev2 = 0; // dp[i-2]
  let prev1 = 0; // dp[i-1]

  for (const num of nums) {
    const curr = Math.max(prev2 + num, prev1);
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}
js
function maxSubArray(nums) {
  let max = nums[0]; // 全局最大子数组和
  let curr = nums[0]; // 以当前位置结尾的最大和
  for (let i = 1; i < nums.length; i++) {
    curr = Math.max(curr + nums[i], nums[i]); // 要么接着前面，要么重新开始
    max = Math.max(max, curr); // 更新全局最优
  }
  return max;
}

爬楼梯 ​

因为到第 n 阶，最后一步只能是从 n-1 跨 1 步，或从 n-2 跨 2 步

  • 状态：f(n) 爬到第 n 阶的方法数
  • 转移：f(n) = f(n-1) + f(n-2)
  • 初值：f(1) = 1, f(2) = 2
js
let prev1 = 1; // f(n-2)
let prev2 = 2; // f(n-1)
[prev1, prev2] = [prev2, prev1 + prev2]

二分查找 ​

左闭右开，不断压缩右侧空间。寻找左边界，第一个 >= target 的位置

js
if (nums[mid] < target) left = mid + 1
else right = mid

寻找右边界，left 就是第一个 > target 的位置

js
if (nums[mid] <= target) left = mid + 1
else right = mid

无重复字符的最长子串 ​

思路（滑动窗口）：

  1. 用 Map 记录字符 -> 上次出现的下标
  2. 右指针 right 不断右移，遇到重复字符时，左指针 left 跳到重复字符的下一位
  3. 每次更新 max

十进制转任意进制 ​

短除法（除基取余，逆序排列）

js
result = digits[num % base] + result;
num = Math.floor(num / base);

任意进制转十进制 ​

按权展开求和

js
result = result * base + digits.indexOf(str[i].toUpperCase());

反转链表 ​

js
// 解法 1：迭代（推荐，O(n) 时间，O(1) 空间）
// 思路：用三个指针逐个翻转箭头方向
//   原来：prev -> curr -> next -> ...
//   翻转：prev <- curr    next -> ...
function reverseList(head) {
  let prev = null; // 已反转部分的头（初始为空）
  let curr = head; // 当前要处理的节点
  while (curr) {
    const { next } = curr; // 暂存下一个节点（否则断链后丢失）
    curr.next = prev; // 核心：翻转指针方向
    prev = curr; // prev 前进一步
    curr = next; // curr 前进一步
  }
  return prev; // 循环结束时 curr=null，prev 指向新的头节点
}

// 解法 2：递归（O(n) 时间，O(n) 栈空间）
// 思路：先递归到链表尾部，然后在回溯时逐层翻转指针
//   递归到底：newHead = 5（最后一个节点，即新头）
//   回溯时：让 4.next.next = 4（即 5->4），再断开 4->5
function reverseListRecursive(head) {
  if (!head || !head.next) return head; // base case：空节点或只剩一个
  const newHead = reverseListRecursive(head.next); // 递归反转后面的部分
  head.next.next = head; // 让后继节点指向自己（翻转）
  head.next = null; // 断开原来的正向指针（防止成环）
  return newHead; // 始终返回尾节点作为新头
}

零钱兑换 ​

js
function coinChange(coins, amount) {
  // dp[i] = 凑出金额 i 最少需要几枚硬币
  // 初始化为 Infinity 表示"暂时凑不出"
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 凑出金额 0 不需要任何硬币

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      // i - coin >= 0：确保减去这枚硬币后金额不为负数
      // 如果 i = 3, coin = 5，那 i - coin = -2，数组下标越界且无意义
      // 只有 i >= coin 时，才可能"先凑出 i-coin，再加一枚 coin 凑出 i"
      if (i - coin >= 0) {
        // dp[i - coin] + 1：在凑出 (i-coin) 的基础上多用一枚 coin
        // dp[i - coin] 可能是 Infinity（凑不出），Infinity + 1 还是 Infinity，
        // Math.min 会自动跳过，所以不需要额外判断
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  // 如果 dp[amount] 仍为 Infinity，说明无论怎么组合都凑不出，返回 -1
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Trie ​

js
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // 插入单词
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  _searchPrefix(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }

  // 查找完整单词
  search(word) {
    const node = this._searchPrefix(word);
    return node !== null && node.isEnd === true;
  }

  // 查找前缀
  startsWith(prefix) {
    return this._searchPrefix(prefix) !== null;
  }
}

LRU Cache ​

js
// 解法 1：基于 Map（最简洁，JS 特色）
// 利用 JS Map 按插入顺序迭代的特性：最早 set 的在最前面（最旧）
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // Map 天然维护插入顺序
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    // 技巧：先删再 set，让这个 key 变成「最新插入的」
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key); // 已存在则先删除（后面会重新 set 到最新位置）
    } else if (this.map.size >= this.capacity) {
      // 容量满了，淘汰最旧的 → Map 迭代器第一个就是最早插入的
      this.map.delete(this.map.keys().next().value);
    }
    this.map.set(key, value); // 插入到最新位置
  }
}

数组中重复的数据 ​

js
// 方法1：原地标记（取反法） O(n) 时间 O(1) 空间
// 思路：利用 1 ≤ a[i] ≤ n 的性质，将 a[i] 的值作为索引，
// 把对应位置的数取反做标记。如果访问时发现已经是负数，说明之前访问过，即出现了两次。
function findDuplicates(nums) {
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    const idx = Math.abs(nums[i]) - 1;
    if (nums[idx] < 0) {
      result.push(idx + 1);
    } else {
      nums[idx] = -nums[idx];
    }
  }
  return result;
}