算法模板学习计划

JS 通用模板

function countByMap(nums) {
  const map = new Map();

  for (const x of nums) {
    map.set(x, (map.get(x) || 0) + 1);
  }

  return map;
}

function hasDuplicate(nums) {
  const seen = new Set();

  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }

  return false;
}

适用：判重、计数、匹配、记录下标。

LeetCode 1：两数之和

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);
  }
}

LeetCode 242：有效的字母异位词

function isAnagram(s, t) {
  if (s.length !== t.length) return false;

  const map = new Map();

  for (const ch of s) {
    map.set(ch, (map.get(ch) || 0) + 1);
  }

  for (const ch of t) {
    if (!map.has(ch) || map.get(ch) === 0) return false;
    map.set(ch, map.get(ch) - 1);
  }

  return true;
}

LeetCode 217：存在重复元素

function containsDuplicate(nums) {
  const seen = new Set();

  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }

  return false;
}

JS 通用模板：dummy + 遍历

function removeWithDummy(head, target) {
  const dummy = new ListNode(0, head);
  let cur = dummy;

  while (cur.next) {
    if (cur.next.val === target) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }

  return dummy.next;
}

适用：删除节点、跳过某类节点、统一头节点边界。

LeetCode 206：反转链表

function reverseList(head) {
  let prev = null;
  let cur = head;

  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }

  return prev;
}

LeetCode 21：合并两个有序链表

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0);
  let cur = dummy;

  while (list1 && list2) {
    if (list1.val <= list2.val) {
      cur.next = list1;
      list1 = list1.next;
    } else {
      cur.next = list2;
      list2 = list2.next;
    }
    cur = cur.next;
  }

  cur.next = list1 || list2;
  return dummy.next;
}

LeetCode 83：删除排序链表中的重复元素

function deleteDuplicates(head) {
  let cur = head;

  while (cur && cur.next) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }

  return head;
}

JS 通用模板：找中点

function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

适用：中点、前后半部分分割、回文链表预处理。

LeetCode 876：链表的中间结点

function middleNode(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

LeetCode 141：环形链表

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

LeetCode 19：删除链表的倒数第 N 个结点

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;

  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }

  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }

  slow.next = slow.next.next;
  return dummy.next;
}

JS 通用模板

function processWithStack(items) {
  const stack = [];

  for (const item of items) {
    if (shouldPush(item, stack)) {
      stack.push(item);
    } else {
      stack.pop();
    }
  }

  return stack;
}

适用：括号匹配、抵消、最近状态维护。

LeetCode 20：有效括号

function isValid(s) {
  const stack = [];
  const map = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (const ch of s) {
    if (!(ch in map)) {
      stack.push(ch);
    } else {
      if (stack.pop() !== map[ch]) return false;
    }
  }

  return stack.length === 0;
}

LeetCode 155：最小栈

var MinStack = function() {
  this.stack = [];
  this.minStack = [];
};

MinStack.prototype.push = function(val) {
  this.stack.push(val);
  if (!this.minStack.length || val <= this.minStack[this.minStack.length - 1]) {
    this.minStack.push(val);
  }
};

MinStack.prototype.pop = function() {
  const val = this.stack.pop();
  if (val === this.minStack[this.minStack.length - 1]) {
    this.minStack.pop();
  }
};

LeetCode 232：用栈实现队列

var MyQueue = function() {
  this.inStack = [];
  this.outStack = [];
};

MyQueue.prototype.push = function(x) {
  this.inStack.push(x);
};

MyQueue.prototype.move = function() {
  if (!this.outStack.length) {
    while (this.inStack.length) {
      this.outStack.push(this.inStack.pop());
    }
  }
};

MyQueue.prototype.pop = function() {
  this.move();
  return this.outStack.pop();
};

JS 通用模板：标准二分

function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

先固定一套模板，再从这个基础上推边界版。

LeetCode 704：二分查找

function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

LeetCode 35：搜索插入位置

function searchInsert(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return left;
}

LeetCode 34：查找第一个和最后一个位置

function lowerBound(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;
  }

  return left;
}

JS 通用模板

function slidingWindow(nums) {
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    add(nums[right]);

    while (needShrink()) {
      remove(nums[left]);
      left++;
    }

    updateAnswer(left, right);
  }
}

核心是先右扩加入状态，再在 while 里左缩。

LeetCode 209：长度最小的子数组

function minSubArrayLen(target, nums) {
  let left = 0;
  let sum = 0;
  let ans = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    while (sum >= target) {
      ans = Math.min(ans, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }

  return ans === Infinity ? 0 : ans;
}

LeetCode 3：无重复字符的最长子串

function lengthOfLongestSubstring(s) {
  let left = 0;
  let ans = 0;
  const set = new Set();

  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    ans = Math.max(ans, right - left + 1);
  }

  return ans;
}

LeetCode 438：找到字符串中所有字母异位词

function findAnagrams(s, p) {
  const need = new Map();
  const window = new Map();
  const res = [];
  let left = 0;
  let valid = 0;

  for (const ch of p) {
    need.set(ch, (need.get(ch) || 0) + 1);
  }

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (need.has(ch)) {
      window.set(ch, (window.get(ch) || 0) + 1);
      if (window.get(ch) === need.get(ch)) valid++;
    }

    while (right - left + 1 > p.length) {
      const d = s[left];
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) valid--;
        window.set(d, window.get(d) - 1);
      }
      left++;
    }

    if (valid === need.size) res.push(left);
  }

  return res;
}

JS 通用模板：前序遍历

function preorderTraversal(root) {
  const result = [];

  function dfs(node) {
    if (!node) return;
    result.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);
  return result;
}

前序：根 → 左 → 右。适合先处理当前节点，再处理子树。

LeetCode 104：二叉树的最大深度

function maxDepth(root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

LeetCode 226：翻转二叉树

function invertTree(root) {
  if (!root) return null;

  const temp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(temp);

  return root;
}

LeetCode 102：二叉树的层序遍历

function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length) {
    const size = queue.length;
    const level = [];

    for (let i = 0; i < size; 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;
}

JS 通用模板：DFS

function dfs(node, visited) {
  if (!node || visited.has(node)) return;
  visited.add(node);

  for (const next of node.neighbors) {
    dfs(next, visited);
  }
}

适用：图连通性、岛屿问题、路径枚举、树深度遍历。

JS 通用模板：BFS

function bfs(start) {
  const queue = [start];
  const visited = new Set([start]);

  while (queue.length) {
    const cur = queue.shift();

    for (const next of cur.neighbors) {
      if (visited.has(next)) continue;
      visited.add(next);
      queue.push(next);
    }
  }
}

适用：最短路径层数、图层级遍历、状态扩散。

LeetCode 200：岛屿数量（DFS）

function numIslands(grid) {
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;

  function dfs(i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== '1') return;
    grid[i][j] = '0';
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);
      }
    }
  }

  return count;
}

LeetCode 111：二叉树的最小深度（BFS）

function minDepth(root) {
  if (!root) return 0;

  const queue = [[root, 1]];

  while (queue.length) {
    const [node, depth] = queue.shift();
    if (!node.left && !node.right) return depth;
    if (node.left) queue.push([node.left, depth + 1]);
    if (node.right) queue.push([node.right, depth + 1]);
  }
}

JS 通用模板

function solve(node) {
  if (isBaseCase(node)) {
    return baseAnswer;
  }

  const left = solve(node.left);
  const right = solve(node.right);

  return combine(left, right, node);
}

适用：树高、分治、结构递归、很多 DFS 子问题。

LeetCode 100：相同的树

function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  if (p.val !== q.val) return false;

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

LeetCode 101：对称二叉树

function isSymmetric(root) {
  function check(left, right) {
    if (!left && !right) return true;
    if (!left || !right) return false;
    if (left.val !== right.val) return false;
    return check(left.left, right.right) && check(left.right, right.left);
  }

  return check(root.left, root.right);
}

LeetCode 50：Pow(x, n)

function myPow(x, n) {
  if (n === 0) return 1;
  if (n < 0) return 1 / myPow(x, -n);

  const half = myPow(x, Math.floor(n / 2));
  if (n % 2 === 0) return half * half;
  return half * half * x;
}

JS 通用模板

function backtrack(nums) {
  const result = [];
  const path = [];

  function dfs(start) {
    if (shouldCollect(path)) {
      result.push([...path]);
    }

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return result;
}

核心固定三步：做选择 → 递归 → 撤销选择。

LeetCode 46：全排列

function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  function dfs() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  }

  dfs();
  return result;
}

LeetCode 78：子集

function subsets(nums) {
  const result = [];
  const path = [];

  function dfs(start) {
    result.push([...path]);

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return result;
}

LeetCode 39：组合总和

function combinationSum(candidates, target) {
  const result = [];
  const path = [];

  function dfs(start, sum) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    if (sum > target) return;

    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      dfs(i, sum + candidates[i]);
      path.pop();
    }
  }

  dfs(0, 0);
  return result;
}