LeetCode 刷题笔记

双指针的核心思想是利用两个指针在数据结构上协同移动，从而将暴力 $O(n^2)$ 的搜索优化到 $O(n)$。常见的手段有：

• Swap 交换 left 和 right 指针的值
• 数组两侧交替移动指针（对撞指针）
• 快慢指针（同向移动，速度不同）

回文链表 (LC 234)

方案：找到链表中点，翻转后半部分，然后前后比较。使用快慢指针找中点。

class Solution:
    def reverseList(self, head):
        if not head:
            return None
        cur = head
        while cur.next is not None:
            temp = head
            head = cur.next
            cur.next = head.next
            head.next = temp
        return head

    def half_of_the_list(self, head):
        slow, fast = head, head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow

    def isPalindrome(self, head):
        first_half_end = self.half_of_the_list(head)
        second_half_reversed = self.reverseList(first_half_end.next)
        while second_half_reversed is not None:
            if second_half_reversed.val != head.val:
                return False
            second_half_reversed = second_half_reversed.next
            head = head.next
        return True
  

移动零 (LC 283)

双指针，一个指向当前待填入位置，一个扫描非零元素。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = size(nums), j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (j <= i) j = i + 1;
                while (nums[j] == 0) j++;
                nums[i] = nums[j];
                nums[j] = 0;
            }
        }
    }
};
  

盛最多水的容器 (LC 11)

面积公式：$area = (j - i) \times \min(height[i], height[j])$。保持短板不动去移动长板，容积只会变少，因此使用对撞双指针，每次移动短板。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int max_area = 0;
        int left = 0, right = n - 1;
        while (left < right) {
            int area = (right - left) * min(height[left], height[right]);
            max_area = max(max_area, area);
            if (height[left] > height[right]) right--;
            else left++;
        }
        return max_area;
    }
};
  

Python 版本同理：

class Solution:
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        max_water = (right - left) * min(height[left], height[right])
        while left < right:
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
            water = (right - left) * min(height[left], height[right])
            max_water = max(max_water, water)
        return max_water
  

三数之和 (LC 15)

排序 + 双指针。固定第一个数，将三数之和转化为两数之和问题。由于不能有相同的结果，需要跳过重复元素。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        sort(nums.begin(), nums.end());

        for (int first = 0; first < n; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) continue;
            int target = -nums[first];
            int third = n - 1;
            for (int second = first + 1; second < third; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) continue;
                while (second < third && nums[second] + nums[third] > target) third--;
                if (second == third) break;
                if (nums[second] + nums[third] == target)
                    ans.push_back({nums[first], nums[second], nums[third]});
            }
        }
        return ans;
    }
};
  

哈希表提供 $O(1)$ 的查找效率，常用于「查找某个元素是否存在」或「统计频率」。

两数之和 (LC 1)

经典哈希表入门题。遍历数组，对每个元素查找 target - nums[i] 是否已在哈希表中。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); i++) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end())
                return {it->second, i};
            hashtable[nums[i]] = i;
        }
        return {};
    }
};
  

最长连续序列 (LC 128)

要求 $O(n)$，不能排序。把所有数字加入集合，然后逐个检查是否为序列起始数字（即 num - 1 不在集合中），从起始数字向上延伸。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set(nums.begin(), nums.end());
        int maxlen = 0;
        for (auto num : num_set) {
            if (num_set.find(num - 1) != num_set.end()) continue;
            int cur = num;
            while (num_set.find(cur + 1) != num_set.end()) cur++;
            maxlen = max(maxlen, cur - num + 1);
        }
        return maxlen;
    }
};
  

排序的作用：方便去重、确定相对顺序。一般来说，如果想要应用排序，都需要保证输出结果里只包含结果本身，不包含元素在原数组中的位置。

合并区间 (LC 56)

按左端点排序后，逐个合并重叠区间。

class Solution:
    def merge(self, intervals):
        n = len(intervals)
        if n == 1:
            return intervals
        sorted_intervals = sorted(intervals, key=lambda x: x[0])
        merged = []
        begin = 0
        i = 0
        while i < n:
            while i < n and sorted_intervals[i][0] <= sorted_intervals[begin][1]:
                i += 1
            merged.append([
                sorted_intervals[begin][0],
                max(sorted_intervals[i-1][1], sorted_intervals[begin][1])
            ])
            begin = i
        return merged
  

快速排序

基于分治思想，平均时间复杂度 $O(n \log n)$。

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)
  

快速选择

基于快速排序思想的选择算法，用于找第 $k$ 小/大元素，平均时间复杂度 $O(n)$。

并查集是一种树型数据结构，用于处理不交集的合并及查询问题。核心操作是 find(x)（查找集合代表元素）和 union(x, y)（合并两个集合）。

两种优化手段：

• 路径压缩：在 find 时将路径上的所有节点直接连接到根节点
• 按秩合并：将较小的树连接到较大的树下

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        # 按秩合并
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True
  

岛屿数量 (LC 200)

使用 DFS 将相邻的陆地沉没（标记为 '0'），每次启动新 DFS 就是一个新岛屿。

class Solution:
    def numIslands(self, grid):
        m, n = len(grid), len(grid[0])

        def visit(i, j):
            if grid[i][j] == '0':
                return
            grid[i][j] = '0'
            if i > 0 and grid[i-1][j] == '1':     visit(i-1, j)
            if i < m-1 and grid[i+1][j] == '1':   visit(i+1, j)
            if j > 0 and grid[i][j-1] == '1':      visit(i, j-1)
            if j < n-1 and grid[i][j+1] == '1':   visit(i, j+1)

        cnt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    visit(i, j)
                    cnt += 1
        return cnt
  

最小堆是完全二叉树，每个节点的值都小于等于其子节点的值。Python 的 heapq 模块提供基于列表的堆操作。

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))  # 输出 1
  

数组中第 K 个最大元素 (LC 215)

使用最小堆维护前 $k$ 个最大元素。当堆大小超过 $k$ 时弹出最小元素，最终堆顶即为第 $k$ 个最大元素。

• 时间复杂度：$O(n \log k)$
• 空间复杂度：$O(k)$

差分数组是高效处理区间更新的数据结构。核心思想：对原数组构造差分数组 diff[i] = arr[i] - arr[i-1]，区间 $[l, r]$ 加 $val$ 操作只需 diff[l] += val 和 diff[r+1] -= val，通过前缀和还原。

差分数组定义：

区间 $[l, r]$ 加 $val$：$\text{diff}[l] \leftarrow \text{diff}[l] + val$，$\text{diff}[r+1] \leftarrow \text{diff}[r+1] - val$

def corpFlightBookings(bookings, n):
    diff = [0] * (n + 2)
    for first, last, seats in bookings:
        diff[first] += seats
        diff[last + 1] -= seats
    res = [0] * n
    res[0] = diff[1]
    for i in range(1, n):
        res[i] = res[i-1] + diff[i+1]
    return res
  

背包问题的核心是在有限资源约束下选择物品以实现目标最优化。分类：

• 0-1 背包：每件物品只有选或不选
• 完全背包：物品可以重复选
• 多重背包：物品有固定的可用数量

思路：从第一件物品开始，逐件考虑。需要计算加入一件物品后所有可能的价值。

将一个数字表示成幂的和的方案数 (LC 2787)

本质是 0-1 背包：每个数字 $i$ 的价值为 $i^x$，问凑出和为 $n$ 的方案数。

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            val = i ** x
            for j in range(n + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= val:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - val]) % MOD
        return dp[n][n]
  

前缀和将「耗时的计算」从「每次查询时」转移到「查询前的准备阶段」，通过牺牲空间复杂度（存储预处理结果）来换取时间复杂度的降低（加速查询）。

用两种颜色给图的顶点着色，使得相邻顶点颜色不同。从任意顶点开始 DFS/BFS 着色，检查是否冲突：

def is_bipartite(graph):
    n = len(graph)
    color = [-1] * n
    for i in range(n):
        if color[i] == -1:
            stack = [i]
            color[i] = 0
            while stack:
                node = stack.pop()
                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        color[neighbor] = color[node] ^ 1
                        stack.append(neighbor)
                    elif color[neighbor] == color[node]:
                        return False
    return True
  

将数据按规则分配到多个「桶」中，每个桶独立处理，最后合并结果。适用于数据分布均匀、范围已知的场景。

前 K 个高频元素 (LC 347)

import collections

def topKFrequent(nums, k):
    freq = collections.Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, count in freq.items():
        buckets[count].append(num)
    res = []
    for i in range(len(buckets) - 1, 0, -1):
        if buckets[i]:
            res.extend(buckets[i])
        if len(res) >= k:
            break
    return res[:k]
  

换水问题 (LC 1642)

数学推导：只需要瓶子数量 $b$ 大于交换数 $e$，每一次交易消耗 $e - 1$ 个空瓶、多喝一瓶水。总额外喝到的瓶数：

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        return numBottles >= numExchange
            ? numBottles + (numBottles - numExchange) / (numExchange - 1) + 1
            : numBottles;
    }
};
  

多数元素 (LC 169)

多数元素占总数一半以上，可以用投票抵消法（Boyer-Moore），也可以用随机化。

class Solution:
    def majorityElement(self, nums):
        candidate, count = None, 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate
  

幂的乘积查询 (LC 2438)

将 $n$ 转为二进制得到 2 的幂的和，然后用前缀积优化区间查询。

class Solution:
    def productQueries(self, n, queries):
        MOD = 10**9 + 7
        powers_prefix = [1]
        t, k = 0, 0
        while n > 0:
            if n & 1:
                powers_prefix.append((2 ** t * powers_prefix[k]) % MOD)
                k += 1
            t += 1
            n >>= 1
        answers = []
        for q in queries:
            ans = (powers_prefix[q[1]+1] // powers_prefix[q[0]]) % MOD
            answers.append(ans)
        return answers
  

24 点游戏 (LC 679)

由于总共只有 4 个数字与 3 个运算符，暴力搜索即可。用前缀表达式的思路递归枚举所有可能：

class Solution:
    def judgePoint24(self, cards):
        TARGET, EPS = 24, 1e-6
        def solve(nums):
            if len(nums) == 1:
                return abs(nums[0] - TARGET) < EPS
            for i, x in enumerate(nums):
                for j, y in enumerate(nums):
                    if i == j: continue
                    rest = [z for k, z in enumerate(nums) if k != i and k != j]
                    for op in range(4):
                        if op < 2 and i > j: continue  # 交换律去重
                        if op == 0:   val = x + y
                        elif op == 1: val = x * y
                        elif op == 2: val = x - y
                        else:
                            if abs(y) < EPS: continue
                            val = x / y
                        if solve(rest + [val]):
                            return True
            return False
        return solve(cards)
  

包含所有 1 的最小矩形面积 II (LC 3197)

分类讨论 + 枚举分割线。所有的情况只有 6 种，其中 3 种可以通过转置合并。

class Solution:
    def minimumSum(self, grid):
        def area2(u, d, l, r):
            mi, mj, Mi, Mj = d+1, r+1, u-1, l-1
            for i in range(u, d+1):
                for j in range(l, r+1):
                    if grid[i][j] == 1:
                        mi, mj = min(mi,i), min(mj,j)
                        Mi, Mj = max(Mi,i), max(Mj,j)
            return (Mi-mi+1)*(Mj-mj+1) if mi <= Mi else float('inf')

        def solve(g):
            n, m = len(g), len(g[0])
            res = n * m
            # 上下分割 + 右下再分
            for i in range(n-1):
                for j in range(m-1):
                    res = min(res,
                        area2(0,i,0,m-1) + area2(i+1,n-1,0,j) + area2(i+1,n-1,j+1,m-1))
                    res = min(res,
                        area2(0,i,0,j) + area2(0,i,j+1,m-1) + area2(i+1,n-1,0,m-1))
            # 三横分割
            for i in range(n-2):
                for j in range(i+1, n-1):
                    res = min(res,
                        area2(0,i,0,m-1) + area2(i+1,j,0,m-1) + area2(j+1,n-1,0,m-1))
            return res

        def rotate(vec):
            n, m = len(vec), len(vec[0])
            return [[vec[n-1-j][i] for j in range(n)] for i in range(m)]

        return min(solve(grid), solve(rotate(grid)))
  

二分查找与排序紧密关联。有两种实现方式：递归和循环。核心是每次将搜索空间缩小一半，时间复杂度 $O(\log n)$。

滑动窗口是双指针的特殊应用，用两个指针维护一个窗口，通过扩大和收缩窗口来解决问题。典型场景：最长/最短满足条件的子串、子数组。

核心要素：有序列表、最小堆、双向队列——总得用一种特殊数据结构来维护窗口内的极值。

回溯算法就是保存上一步的状态以方便恢复。本质是带剪枝的深度优先搜索。