题目本身标识的难度级别只是对所有人的平均情况，应该建立自己的难度评估标准
保存和记录自己做过的每一题，可以分为四个等级
trival：能马上想到解法的题目，并且代码量较少，保证能一次写对，比如数组或字符串的简单模拟题easy：能马上想到解法的题目，但实现起来需要注意一些细节、边界情况，能写出来，但需要一些修改调试，如链表类题目medium：能知道大致思路，但实现起来较为繁琐，边界条件较为复杂，比如一些回溯类题目、动态规划题目、二分查找hard：不知道解法（不在常见套路中或者需要一定的问题转换或者需要多个知识点），或者能知道大致思路但需要在常规套路上做较大的变动刷题是提高自己熟练度的过程，也是把难度一层一层往下降的过程
LeetCode上的很多题目可以根据题目提供的输入规模大致判断时间复杂度的最低要求
| Input Size | Complexity | 可能的解法 |
|---|---|---|
突变 -> 二分
有序 -> 二分和双指针
满足xx的最小区间/搬动元素/合并序列 -> 双指针
所有长度为k区间的xx -> 滑动窗口
下一个更大/小 -> 单调栈
最值 -> 回溯/搜索、动态规划、贪心
所有情况 -> 回溯/搜索
TopK/动态维护最值 -> 优先队列
元素不变，前缀查询（或者能通过前缀“差”计算区间“和”） -> 前缀“和”
元素变，前缀查询（或者能通过前缀“差”计算区间“和”） -> 树状数组
元素变，区间查询 -> 线段树
有符号数的相加/相乘/左移时需注意
相加时如果需要判断是否溢出，可以用INT_MAX-一个加数与另一个加数比较大小
有时候答案是int范围，但计算过程可能超出int，需要使用long long或者调整计算顺序，特别是那种先乘后除或先加后减的情况
(r - l) / 2 + l，因为(l + r) / 2可能发生溢出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错误
至少有以下几点显而易见的优雅之处
相邻的区间，上一个区间的上界是下一个区间的下界，比如
广义的双指针就是指使用 两个指针 在 两个线性结构上（可以是同一个数组）同时（即交替）地同向（或反向，即首尾分别开始）前进
应用：
如果是在同一数组上，同向或/且两指针距离保持固定，可以称为滑动窗口
应用：
求解第一个大于/小于当前元素的下标
以单调递增栈为例
如果将入栈的元素大于栈顶元素，直接入栈，
否则，一直出栈直到栈顶满足上述条件，再入栈
性质1：当一个元素出栈时，将入栈的元素是后面第一个小于等于它的元素
性质2：当一个元素入栈时，此时栈顶元素是前面第一个小于它的元素（第一个小于等于它的元素的前一个元素）
是在线性时间内求解最长回文子串的算法
https://leetcode-cn.com/problems/longest-palindromic-substring/
读者需要注意以下几点：
KMP 算法虽然有着良好的理论时间复杂度上限，但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时，我们需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度；
学习 KMP 算法时，一定要理解其本质。如果放弃阅读晦涩难懂的材料（即使大部分讲解 KMP 算法的材料都包含大量的图，但图毕竟只能描述特殊而非一般情况）而是直接去阅读代码，是永远无法学会 KMP 算法的。读者甚至无法理解 KMP 算法关键代码中的任意一行。
由于本题就是在一个字符串中查询另一个字符串是否出现，可以直接套用 KMP 算法。因此这里对 KMP 算法本身不再赘述。读者可以自行查阅资料进行学习。这里留了三个思考题，读者可以在学习完毕后尝试回答这三个问题，检验自己的学习成果：
设查询串的的长度为
，模式串的长度为 ，我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种分析方法？如果有多个查询串，平均长度为
，数量为 ，那么总时间复杂度是多少？在 KMP 算法中，对于模式串，我们需要预处理出一个
数组（有时也称为 数组、 数组等）。这个数组到底表示了什么？答案
设查询串的的长度为
，模式串的长度为 ，我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种分析方法？如果有多个查询串，平均长度为
，数量为 ，那么总时间复杂度是多少？在 KMP 算法中，对于模式串，我们需要预处理出一个
数组（有时也称为 数组、 数组等）。这个数组到底表示了什么？对于基于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;
}
};
常见于滑动窗口中统计各种字符的出现次数，由于长度固定为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函数
考虑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>）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);
<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);
<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千万注意，特别是在循环代码里的某些值必须每轮都更新
对于图的题目
非leetcode平台，需要自行处理IO时，对于输入的一组数据是数组或矩阵
给定序列，包含n个元素e_i，需要对序列中的连续相等或连续满足某个条件f(e)的每个子序列(设长度为cnt)进行计算处理p(e, cnt)
方法1，记录上一个的结果pre及其重复次数cnt，遍历每个元素e时判断与pre是否相等，
cnt加1p(pre, cnt)，然后重置cnt=1,pre=epre的情况，这对于后面的循环是无意义的方法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})
二叉树层序遍历时，队列的大小要在每一层开始遍历时保存
满二叉树（堆）节点顺序与位运算的关系
树序列化
关于位运算的技巧，请看另一篇博客：C++位运算总结
在字符串和数组的题目中，如果需要编码的状态或存储的映射关系较少，巧妙运用位表示可以加快速度或避免使用集合和哈希表
作为记忆化搜索的状态表示（每个位表示某个对象是否已被选择），即dp[state]，state是整数，
异或运算满足结合律和交换律
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;
}
};
https://www.cnblogs.com/wei-li/p/2711629.html
https://blog.csdn.net/github_36778422/article/details/106379106