LeetCode Hot 100

前言

最近开始抽事件刷 Hot 100 了。

后续我会逐步完善题型导航。

题型导航

题目	解法	个人理解
5. 最长回文子串	动态规划
11. 盛最多水的容器	双指针 + 贪心
22. 括号生成	回溯
39. 组合总和	回溯
46. 全排列	回溯
48. 旋转图像	数学	知道矩阵相关数学知识就能做出来
55. 跳跃游戏	贪心 / 动态规划	一开始使用动态规划，通过后发现贪心更快
56. 合并区间	快速排序(等较快的排序)	先根据各个边界的左端点排序，然后再合并
62. 不同路径	动态规划	貌似有数学上的解，更快，但是懒得看
64. 最小路径和	动态规划	到 (i,j) 的最小路径和取决于 (i-1,j) 和 (i,j-1)
75. 颜色分类	快速排序(三路)	这题因为有大量重复项，使用三路快排比较好
78. 子集	回溯
102. 二叉树的层序遍历	BFS	几乎就是纯 BFS，要额外记录每层元素个数而已
279. 完全平方数	动态规划(完全背包)	参考零钱兑换，假设硬币都是完全平方数
322. 零钱兑换	动态规划(完全背包)
337. 打家劫舍 III	DFS + 动态规划(树形DP)	由底朝上不用哈希表，相反则需要
347. 前 K 个高频元素	桶排序 / 快速选择	配合哈希表，两种方法都能完成进阶要求
394. 字符串解码		用纯递归写出来的，感觉没有用到什么算法技巧
399. 除法求值	图(邻接表) + BFS/DFS	邻接表记录权值，然后从一个端点搜索到另一个
416. 分割等和子集	动态规划( 0-1 背包)	类似传统 0-1 背包问题
494. 目标和	回溯 / 动态规划( 0-1 背包)	数学功底不好，一开始没想到可以转为 0-1 背包
581. 最短无序连续子数组	双指针 + 贪心	双指针确定左右边界可做到 O(n)

知识点

桶排序

桶排序（Bucket Sort）的思路是：先按照某种映射规则，把元素分到若干个桶里；再分别对每个桶排序；最后按照桶的顺序把结果合并起来。

它适合以下情况：

• 元素能够映射到一个确定的区间中。
• 数据范围已知，或者能够先求出最大值和最小值。
• 数据分布比较均匀，不会让大量元素都挤在同一个桶中。
• 可以接受额外的空间开销。

假设有 $n$ 个元素、$b$ 个桶，第 $i$ 个桶中有 $m_i$ 个元素，那么桶排序的时间复杂度取决于桶内使用的排序算法。下面的模板使用插入排序，时间复杂度为：

$$O\left(n + b + \sum_{i=1}^{b}m_i^2\right)$$

• 数据分布均匀、桶的数量和大小设置合理时，平均时间复杂度可以达到 $O(n + b)$；当 $b$ 与 $n$ 同阶时，通常记为 $O(n)$。
• 所有元素都落入同一个桶时，会退化为 $O(n^2)$。
• 需要保存所有桶，空间复杂度为 $O(n + b)$。

下面是一个支持负数的整数桶排序模板。bucketWidth 表示每个桶覆盖的数值范围，需要根据数据分布选择；它必须大于 0：

#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <vector>

void bucketSort(std::vector<int>& nums, int bucketWidth) {
    if (nums.size() < 2) {
        return;
    }
    if (bucketWidth <= 0) {
        throw std::invalid_argument("bucketWidth must be positive");
    }

    const auto [minIt, maxIt] = std::minmax_element(nums.begin(), nums.end());
    const long long minValue = *minIt;
    const long long maxValue = *maxIt;
    const std::size_t bucketCount =
        static_cast<std::size_t>((maxValue - minValue) / bucketWidth + 1);

    std::vector<std::vector<int>> buckets(bucketCount);
    for (int value : nums) {
        const std::size_t index =
            static_cast<std::size_t>((static_cast<long long>(value) - minValue) /
                                     bucketWidth);
        buckets[index].push_back(value);
    }

    std::size_t writeIndex = 0;
    for (auto& bucket : buckets) {
        // 对桶内元素使用插入排序
        for (std::size_t i = 1; i < bucket.size(); ++i) {
            const int value = bucket[i];
            std::size_t j = i;
            while (j > 0 && bucket[j - 1] > value) {
                bucket[j] = bucket[j - 1];
                --j;
            }
            bucket[j] = value;
        }

        for (int value : bucket) {
            nums[writeIndex++] = value;
        }
    }
}

在前 K 个高频元素中，不是按照元素值分桶，而是按照元素出现的次数分桶。一个元素最多出现 $n$ 次，因此可以创建 $n + 1$ 个桶，把出现次数为 frequency 的元素放入 buckets[frequency]，再从后向前遍历桶。这样不需要对频次排序，时间复杂度和空间复杂度都是 $O(n)$。

快速选择

Other

枚举
模拟
排序
哈希
前缀和
前后缀
原地置换
矩阵
双指针
滑动窗口
二分查找
中心扩展
快慢指针
递归
分治
回溯
深度优先搜索
广度优先搜索
栈
单调栈
队列
单调队列
堆
链表
二叉树
二叉搜索树
图
拓扑排序
并查集
字典树
贪心
动态规划
记忆化搜索
快速选择
摩尔投票
位运算
数学

总结

总结就等到我把 Hot 100 全部刷完再写吧。

---