难度
题目本身标识的难度级别只是对所有人的平均情况，应该建立自己的难度评估标准
保存和记录自己做过的每一题，可以分为四个等级
trival：能马上想到解法的题目，并且代码量较少，保证能一次写对，比如数组或字符串的简单模拟题easy：能马上想到解法的题目，但实现起来需要注意一些细节、边界情况，能写出来，但需要一些修改调试，如链表类题目medium：能知道大致思路，但实现起来较为繁琐，边界条件较为复杂，比如一些回溯类题目、动态规划题目、二分查找hard：不知道解法（不在常见套路中或者需要一定的问题转换或者需要多个知识点），或者能知道大致思路但需要在常规套路上做较大的变动
刷题是提高自己熟练度的过程，也是把难度一层一层往下降的过程
规模
LeetCode上的很多题目可以根据题目提供的输入规模大致判断时间复杂度的最低要求
| Input Size | Complexity | 可能的解法 |
|---|---|---|
| 位运算/数位运算/数学 | ||
| 二分/倍增/快速幂/辗转相除 | ||
| 单重循环枚举+哈希表(unordered_set/unordered_map)/双指针/滑动窗口/栈(单调栈)/队列/串匹配算法/动态规划/贪心 | ||
| 排序/堆(priority_queue)/红黑树(set/map) | ||
| 双重循环枚举/动态规划/Dijkstra | ||
| 三重循环枚举/动态规划/Floyd | ||
| 回溯（组合）494. 目标和 | ||
| 回溯（组合）491. 递增子序列 | ||
| 回溯（排列） |
思路
突变 -> 二分
有序 -> 二分和双指针
满足xx的最小区间/搬动元素/合并序列 -> 双指针
所有长度为k区间的xx -> 滑动窗口
下一个更大/小 -> 单调栈
最值 -> 回溯/搜索、动态规划、贪心
所有情况 -> 回溯/搜索
TopK/动态维护最值 -> 优先队列
元素不变，前缀查询（或者能通过前缀“差”计算区间“和”） -> 前缀“和”
元素变，前缀查询（或者能通过前缀“差”计算区间“和”） -> 树状数组
元素变，区间查询 -> 线段树
溢出
有符号数的相加/相乘/左移时需注意
相加时如果需要判断是否溢出，可以用INT_MAX-一个加数与另一个加数比较大小
- eg：29. 两数相除
有时候答案是int范围，但计算过程可能超出int，需要使用long long或者调整计算顺序，特别是那种先乘后除或先加后减的情况
- eg：二分查找取中点需要使用
(r - l) / 2 + l，因为(l + r) / 2可能发生溢出
Leetcode的溢出
Java：发生溢出时，直接当成负数来处理（最大与最小值连成环）
这意味着，如果我们在运算过程中如果只涉及「纯加减运算」，而不涉及「乘除」、「取最大值/最小值」和「数值大小判断」的话，不需要使用 long 来确保正确性，只要答案最终是 int 范围，溢出会被转化回来。
System.out.println(Integer.MIN_VALUE); // -2147483648
int a = Integer.MAX_VALUE;
System.out.println(a); // 2147483647
a += 1;
System.out.println(a); // -2147483648
a -= 1;
System.out.println(a); //2147483647
C++：对于 int 溢出的处理也是一样的。
但在 leetcode 上的 C++ 发生溢出时，会直接抛出运行时异常（应该是因为编译选项开启了-fsanitize=undefined）。
因此同样的代码无法被正常执行的
cout << INT_MIN << endl; //-2147483648
int a = INT_MAX;
cout << a << endl; // 2147483647
a += 1; // 运行时报错
cout << a << endl;
a -= 1;
cout << a << endl;
区间
无论是普通的循环还是二分查找的上下界，坚持左闭右开原则，能避免很多off-by-one错误
至少有以下几点显而易见的优雅之处
- 长度就是
- 时就是空区间
相邻的区间，上一个区间的上界是下一个区间的下界，比如
双指针
广义的双指针就是指使用 两个指针 在 两个线性结构上（可以是同一个数组）同时（即交替）地同向（或反向，即首尾分别开始）前进
应用：
- 搬动元素：如原地移除指定或重复的元素、快排划分中交换两侧元素、归并两个有序数组
- 枚举排序数组中的两个元素：如果我们发现随着第一个元素的递增，根据约束条件或者剪枝条件（舍弃的部分不会有更优的解），第二个元素是递减的，可以使用相向双指针的方法，将枚举的时间复杂度从 O(N^2)减少至 O(N)。（枚举的过程，左指针每次向右移动一个位置，而右指针每次向左移动若干个位置，两指针一共会移动的次数为 O(N)，均摊下来，相当于左指针每次向右移动一个位置。）思考：这种双指针是贪心的思想吗？
- eg. 11. 盛最多水的容器
- eg. 排序数组的两数之和
如果是在同一数组上，同向或/且两指针距离保持固定，可以称为滑动窗口
应用：
- 覆盖类问题：满足xx的最小区间，如字符串满足某些字符计数达到指定值、数组区间和达到某些值
- 所有区间的统计值：最值、平均、中位数，需要用另外的数据结构动态维护区间数据
单调栈
求解第一个大于/小于当前元素的下标
以单调递增栈为例
如果将入栈的元素大于栈顶元素，直接入栈，
否则，一直出栈直到栈顶满足上述条件，再入栈
性质1：当一个元素出栈时，将入栈的元素是后面第一个小于等于它的元素
性质2：当一个元素入栈时，此时栈顶元素是前面第一个小于它的元素（第一个小于等于它的元素的前一个元素）
串算法
Manacher 算法
是在线性时间内求解最长回文子串的算法
https://leetcode-cn.com/problems/longest-palindromic-substring/
KMP 算法
读者需要注意以下几点：
KMP 算法虽然有着良好的理论时间复杂度上限，但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时，我们需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度；
学习 KMP 算法时，一定要理解其本质。如果放弃阅读晦涩难懂的材料（即使大部分讲解 KMP 算法的材料都包含大量的图，但图毕竟只能描述特殊而非一般情况）而是直接去阅读代码，是永远无法学会 KMP 算法的。读者甚至无法理解 KMP 算法关键代码中的任意一行。
由于本题就是在一个字符串中查询另一个字符串是否出现，可以直接套用 KMP 算法。因此这里对 KMP 算法本身不再赘述。读者可以自行查阅资料进行学习。这里留了三个思考题，读者可以在学习完毕后尝试回答这三个问题，检验自己的学习成果：
设查询串的的长度为 ，模式串的长度为 ，我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种分析方法？
如果有多个查询串，平均长度为 ，数量为 ，那么总时间复杂度是多少？
在 KMP 算法中，对于模式串，我们需要预处理出一个 数组（有时也称为 数组、 数组等）。这个数组到底表示了什么？
答案
设查询串的的长度为 ，模式串的长度为 ，我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种分析方法？
- 时间复杂度为 ，用到了均摊分析（摊还分析）的方法。
- 具体地，无论在预处理过程还是查询过程中，虽然匹配失败时，指针会不断地根据 数组向左回退，看似时间复杂度会很高。但考虑匹配成功时，指针会向右移动一个位置，这一部分对应的时间复杂度为 。又因为向左移动的次数不会超过向右移动的次数，因此总时间复杂度仍然为 。
如果有多个查询串，平均长度为 ，数量为 ，那么总时间复杂度是多少？
- 时间复杂度为 。模式串只需要预处理一次。
在 KMP 算法中，对于模式串，我们需要预处理出一个 数组（有时也称为 数组、 数组等）。这个数组到底表示了什么？
- 等于满足下述要求的 的最大值： 具有长度为 的完全相同的前缀和后缀。这也是 KMP 算法最重要的一部分。
自定义Hash函数
对于基于hashtable的unordered系列的容器，键类型需要有hash函数，基础类型和string，标准库的std::hash<>提供了特化版本，其他自定义类型或容器类需要自行实现
注意，
hash函数一定会存在冲突，hash函数设计不好会导致分布不均匀，冲突更多，但只不过是影响hash表的效率；为基于哈希表的数据结构
unordered_set<vector<int>>设计自定义的hash函数，即使多个vector<int>对应的hash值冲突，内部也会用链表一一记录但如果是自行使用hash函数将
vector<int>进行hash后得到一个unsigned long long才插入set<unsigned long long>，那么hash值冲突的若干个vector<int>将无法被区分！！
自定义对字符串/字符数组的的哈希函数
自然溢出(mod 2^64)
constexpr unsigned long long base = 131;
unsigned long long charsHash(const char *str, int n) {
unsigned long long h = 0;
for (int i = 0; i < n; i++) {
h = h * base + str[i];
}
};
单哈希
constexpr unsigned long long base = 131, mod = 10e18 + 7;
unsigned long long charsHash(const char *str, int n) {
unsigned long long h = 0;
for (int i = 0; i < n; i++) {
h = (h * base + str[i]) % mod;
}
};
自定义对 array<int, 26> 类型的哈希函数
常见于滑动窗口中统计各种字符的出现次数，由于长度固定为26<32，可用直接右移一位然后累计异或
auto arrayHash = [int_hash = hash<int>{}] (const array<int, 26>& arr) -> size_t {
return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
return (acc << 1) ^ int_hash(num);
});
};
unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
自定义对不定长度序列的哈希函数
以vector<int>为例
一个万用的哈希函数
魔数0x9e3779b9
auto vector_hash = [](const vector<int> & vec) {
unsigned long long seed = vec.size();
for (int v : vec) seed ^= v + 0x9e3779b9 + (seed >> 2) + (seed << 6);
return seed;
};
unordered_set<vector<int>, decltype(vector_hash)> s(0, vector_hash);
另一种思路：转为字符串
把vector<int>转成元素的字符串拼接，string作为容器的key，这样无需提供hash函数
自定义对 pair<T, U> 类型的哈希函数
考虑T/U为基础类型，一种方法是异或，但碰撞较为严重，hash表效率会降低
auto pair_hash = [](const auto p) {
return std::hash<decltype(p.first)>()(p.first) ^ std::hash<decltype(p.second)>()(p.second);
}
另一种方法是借用上面的万用方法
auto pair_hash = [](const auto p) {
unsigned long long v1 = std::hash<decltype(p.first)>()(p.first) + 0x9e3779b9;
unsigned long long v2 = std::hash<decltype(p.second)>()(p.second) + 0x9e3779b9;
return v1 ^ (v2 + (v1 >> 2) + (v1 << 6));
};
仿函数实现
为哈希表自定义hash函数可以有两者写法，一种是上面的lambda，一种是仿函数
对于lambda，它本质是一个匿名类的实例，无法显示调用构造函数，所以只能在构建哈希表时显示传入实例，且decltype作为模板参数
unordered_set<pair<int, int>, decltype(pair_hash)> s(0, pair_hash);
如果这个unordered_set本身再作为某个容器的元素，就会有问题，插入元素内部构造时会调用lambda的构造函数而报错
unordered_map<int, unordered_set<pair<int, int>, decltype(pair_hash)>> d;
这时候就应该用仿函数
int main() {
class PIIHash {
public:
size_t operator()(const pair<int, int> & p) const {
return hash<int>()(p.first) ^ hash<int>()(p.second);
}
};
unordered_map<int, unordered_set<pair<int, int>, PIIHash>> lines1;
lines1[1] = unordered_set<pair<int, int>, PIIHash>();
lines1[1].insert(make_pair(1, 2));
auto pii_hash = [int_hash = hash<int>()](pair<int, int> pii){
return int_hash(pii.first) ^ int_hash(pii.second);
};
unordered_map<int, unordered_set<pair<int, int>, decltype(pii_hash)>> lines2;
lines2.emplace(1, std::move(unordered_set<pair<int, int>, decltype(pii_hash)>(0, pii_hash)));
lines2[1].insert(make_pair(1, 2));
return 0;
}
注意，重载 operator() ，参数要const，成员函数也要const，否则unordered_set模板内部会匹配不上
自定义排序和优先队列比较函数
比较操作符
7种比较操作符，operator==, !=, <, <=, >, >=, <=>(C++20)
比较函数
对于排序或优先队列，可以自定义比较函数
排序过程或中或维护队列过程中任意两个元素都可能被比较，相当于给所有元素定一个全局唯一顺序
因此比较函数是一个全序的二元关系R（对于集合中的任何一对元素，在这个关系下都是相互可比较的），需满足
- 传递性（如果 a R b 且 b R c 则 a R c），
cmp(a, b) && cmp(b, c) == true -> cmp(a, c) == true- 反对称性（如果 a R b 且 b R a 则 a is b），
cmp(a, b) && cmp(b, a) -> a == b- 完全性（即 a R b 或 b R a 必满足其一），
cmp(a, b) || cmp(b, a) == true
<=和>=就是全序关系，
元素的比较函数实现的是<或>语义而不是<=语义或>=语义 ，换句话说，对于语义上相等的元素，必须放回false
排序和优先队列
对应C++的sort函数，默认是升序（第三个模板参数默认为less<T>）
对于C++的优先队列，默认是大根堆（第三个模板参数默认为less<T>）
less<T>或greater<T>是比较操作符的一个包装，会调用对应的operator<和operator>
如果元素是基本类型，使用内建比较操作符
如果元素是自定义结构体或类，默认没有比较操作符，需要自行实现
对于pair和tuple，默认有比较操作符（即朴素地依次比较每个元素），也可重载自行实现
要实现小根堆或降序，可以
- 实现重载
operator<为“语义上”的> - 或者优先队列的第三个模板参数改用
greater<T>（需要该类型有实现operator>） - 直接用lambda或仿函数实现比较函数（第三个模板参数）
auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
随机数
C++标准库 <random>
// random_device 是使用硬件熵源的非确定随机数生成器，可以认为是真随机数
// random_device{}() 即获取一个真随机数，作为预定义随机数生成器mt19937的种子
mt19937 rng{random_device{}()};
mt19937_64 rng{random_device{}()}; //64位版本
// xxx_distribution 是随机数分布，对随机数生成器的产生结果进行变换
// [a, b] 均匀分布 整数
uniform_int_distribution<int> uni(a, b);
// [a, b) 均匀分布 浮点数
uniform_real_distribution<double> uni(a, b);
// 获取
int v = uni(rng);
C标准库 <stdlib.h>
// 用当前时间作为种子进行初始化
srand((unsigned int)time(0));
// 返回[0, RAND_MAX]之间的随机整数（RAND_MAX+1个数中的任意一个）
// 标准规定了RAND_MAX 的值应至少为32767，不同实现上不同
// GNU C 实现为 2147483647
rand();
// 获取[0, 1]的随机浮点数
rand() / (double)RAND_MAX;
// 获取[0, 1)的随机浮点数
// rand() / (double)(RAND_MAX + 1); //RAND_MAX+1可能溢出！
rand() / ((unsigned)RAND_MAX + 1);
rand() / (RAND_MAX + 1U);
rand() / ((double)RAND_MAX + 1);
rand() / (RAND_MAX + 1.0);
// 获取[0, n]的随机整数，下面这样是错误的
// 因为RAND_MAX+1不一定是n+1的整数倍，取余后，存在两种不同概率的数
// 以RAND_MAX==32767，n+1==10000为例，得到[0,2767]的情况有4种，得到[2768,9999]的情况只有3种，
rand() % (n + 1);
// 获取[0, n)的随机整数
(int)(n * rand() / (RAND_MAX + 1.0));
// 获取[a, b]的随机数，拒绝采样法，可能导致超时，特别是N比RAND_MAX/2大一些的情况
inline int randint(int a, int b){
const unsigned int N = b - a + 1;
const unsigned int bound = (RAND_MAX + 1U) / N * N; //超过bound的部分不足N个，重新随机
int r;
do {
r = rand();
} while (r >= bound);
return a + int(r / (double)bound * N);
}
其他注意事项
浮点数相等比较
浮点数转整数（显式或隐式），正负数的处理不同！正数是向下取整，负数是向上取整！
std::accumulate的初始值类型，比如long long s = accumulate(nums.begin(), nums.end(), 0ll); // 注意这里0ll，结果是64位，初始值类型也要是64位，否则模板推导出32位int作为中间变量会溢出unordered容器使用auto遍历，key是无序的
动态规划or背包问题，注意每层循环遍历的方向
剪枝要非常小心，不要把正确答案也剪掉了！先通过再说，没有把握，就不要随便剪枝！
使用contine千万注意，特别是在循环代码里的某些值必须每轮都更新
对于图的题目
- 注意顶点索引是从0开始还是从1开始，
- 注意是有向图还是无向图
- 对于无向图，应该添加两次边，边相关的数组开两倍
- Dijkstra算法如果已经找到目标点到源点的最短距离，就可以提前返回了，剩余点无需再计算
- 注意图中的重边，去除有时候题目要求取最小
- 在正确的时机标记vis
非leetcode平台，需要自行处理IO时，对于输入的一组数据是数组或矩阵
- 如果是按单个元素或单行元素直接处理而不是先存储整组数据，若处理过程中已知道这组数据的对应结果而直接输出，此时要记得清理剩余输入！！！而不是直接break或continue；否则会把剩余数据当成下一组
给定序列，包含
n个元素e_i，需要对序列中的连续相等或连续满足某个条件f(e)的每个子序列(设长度为cnt)进行计算处理p(e, cnt)方法1，记录上一个的结果
pre及其重复次数cnt，遍历每个元素e时判断与pre是否相等，- 相等，则
cnt加1 - 不相等，则处理上一次的结果
p(pre, cnt)，然后重置cnt=1,pre=e - 缺点：
- 第一次循环时，必然不相等，还需要针对第一次判断无效
pre的情况，这对于后面的循环是无意义的 - 最后循环退出时，还需要额外处理最后一次连续的结果，往往需要复制粘贴之前处理的代码然后做一些修改，容易出错！（也可以提取为inline函数，但很多需要修改的局部变量需要传入引用）
- 第一次循环时，必然不相等，还需要针对第一次判断无效
- 相等，则
方法2，双指针，
i下标遍历每个元素e，对于i，j从i开始遍历直到不相等或序列结束，- 这样即避免了第一次特殊判断，也避免了最后一次额外处理，代码如下
for (int i = 0, j = 0; i < s.size(); i = j) { char e = s[i]; while (j < s.size() && e == s[j]) ++j; int cnt = j - i; ...// 处理p(e, cnt) }
遍历临时构建的初始化列表
for (auto V : {1, 2, 3, 4})
二叉树/N叉树
二叉树层序遍历时，队列的大小要在每一层开始遍历时保存
满二叉树（堆）节点顺序与位运算的关系
树序列化
位运算
关于位运算的技巧，请看另一篇博客：C++位运算总结
压缩状态
在字符串和数组的题目中，如果需要编码的状态或存储的映射关系较少，巧妙运用位表示可以加快速度或避免使用集合和哈希表
作为记忆化搜索的状态表示（每个位表示某个对象是否已被选择），即dp[state]，state是整数，
- 这类问题一般规模最多20，用20位就可表示
- [473] 火柴拼正方形
- [464] 我能赢吗
与堆和完全二叉树的关系
异或的性质
异或运算满足结合律和交换律
a ^ a == 0
a ^ b == c <==> a ^ c == b
只出现一次的数字系列
考虑每位对结果的影响，单独计算
困难题
树状数组/线段树
模拟退火
class Solution {
public:
static constexpr double eps = 1e-18;
static constexpr double delta = 0.995; //调了一年的参数一般为0.97~1.0
long ans = LONG_MIN;
long calc(vector<int>& nums, int k) {
long res = 0; int n = nums.size();
for (int i = 0; i < n; i++)
res += (i + k) % n * nums[i];
ans = max(ans, res); //更新答案
return res;
}
void sa(vector<int>& nums) {
int n = nums.size();
long last = LONG_MIN / 2;
for (double t = 1e6; t > eps; t *= delta) {
int k = rand() % n;
long now = calc(nums, k);
long d = now - last;
if (d > 0 || //比当前优秀就接受
exp(-1.0 * d / t) * RAND_MAX > rand() //否则以一定概率接受
) {
last = now;
}
}
}
int maxRotateFunction(vector<int>& nums) {
double t = 0;
while ((t = clock() / (1.0 * CLOCKS_PER_SEC)) <= 0.98) { //不超时的情况下尽可能多计算
// cout << t << endl;
srand(time(0));
sa(nums);
}
return ans;
}
};
REF
https://www.cnblogs.com/wei-li/p/2711629.html
https://blog.csdn.net/github_36778422/article/details/106379106