写在正文前：由于近期在LeetCode刷题，遇到了很多很厉害的算法，出于分享同时也是对自己掌握内容的总结，考虑推出这篇博文，欢迎各位指教！
笔者根据知乎提问“世界上有哪些代码量，但很牛逼很经典的算法或项目案例？”以及在LeetCode中遇到的比较经典的一些算法进行了总结，后续看情况不定期更新
附上链接：https://www.zhihu.com/answer/974983270
1. KMP算法（解决字符串模式匹配问题）
字符串的模式匹配，是求一个字符串T（模式串）在另一个字符串S（主串）中的位置
KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
首先，谈一谈解决这个问题有哪些思路：
1. 暴力搜索：
从s的第一个位置开始取跟T等长的子串，将子串依次跟T中的每个元素比较，一旦不同，则s移动至下一个位置重新取子串进行比较，直至成功匹配，或s的所有子串都已经比较完
时间复杂度：O(NM) 空间复杂度：O(1)
int Index(string s, string t) {
int i =0, j = 0;
while(i < s.length() && j < s.length()) {
if(s[i] == s[j]) {
i++;
j++;
}
else {
i = i - j + 1;
j = 0;
}
}
if(j == s.length())
return i - j;
return -1;
} 2. Hash：
设|S| = n , |T| = m。如果不考虑冲突，那么我们可以将 S 的所有长度为 m 的子串hash值都求出来，复杂度为O(N)。将这 n-m+1 个子串与T的hash值在O(1)的时间内一一比对，即可通过hash值是否相同来判断是否匹配成功。
但实际上如果n和m很大(1e6)，那么散列值冲突是不可避免的，此时需要二次判断或者通过其他方法（构造更好的散列函数）来在保证速度的情况下提升正确性。
时间复杂度：O(N) 空间复杂度：O(N)
哈希函数：
H[i] = H[i - 1]*p + val[i]typedef unsigned long long ull;
const ull B = 100000007; //哈希的基数
int Index(string s, string t) {
int n = s.length(), m = t.length();
unordered_map<int, int> hashmap;
ull sh = 0, th = 0, t = 1;
for(int i = 0; i < m; i++)
{
sh = sh * B + s[i]; //s和t长度为m的前缀对应哈希值
th = th * B + t[i];
t *= B;
}
for(int i =0; i < n - m; i++) {
if(sh == th)
return i;
sh = sh * B + s[i + m] - s[i] * t;
}
return -1;
} 3. KMP：
我们可以发现暴力搜索的时候，中间有很多位置重复进行了不必要的判断。
用next数组记录模式串(T)中每个位置上发生匹配失败时，下一次和主串对应位置比对的字符下标
next数组：
假设我们 S[i] 和 T[j] 发生了失配，如果我们知道 “T 中以 j 为末尾的真子串” 和 T[0, j)的最长公共前后缀子串T[0,t)，那么下一次T跟S[i]比较的字符下标就为t，也就是说在next数组中j对应转移下标为t，即next[j] = t。
讲人话就是：对于模式串T，T[0,t)和T[j-t, j)是匹配的，即T[0,t) = T[j-t, j)，而我们又知道S[i-j,i) = T[0,j)，那么必然有S[i-t,i) = T[j-t,j) = T[0,t)，所以我们下一次匹配从t开始即可
时间复杂度：O(M + N) 空间复杂度：O(M)
计算next数组和KMP算法代码如下：
void get_next(string t, int next[]) {
int i = 0;
next[0] = -1; //第一个字符不匹配 next值设为-1
int j = -1;
while(i < t.length()) {
if(j == -1 || t[i] == t[j])
//j == -1判断条件解决了当t[1] != t[0]时 j = next[0] = -1 数组越界
//同时 j == -1时 next[0] = -1符合情况
{
++i;
++j;
next[i] = j; //i和j匹配时 指向j+1
}
else //i和j不匹配时 找更短的前后缀
j = next[j];
}
}
int KMP(string s, string t) {
int i = 0, j = 0;
while(i < s.length() && j < t.length()) {
if(j == -1 || s[i] == s[j])
//j == -1判断条件是因为next数组中有-1的情况 造成数组越界
//j == -1表明第一个字符都不匹配 s应该从下一个位置开始匹配 ++j后 j = 0
{
++i;
++j;
}
else
j = next[j];
}
if(j == t.length()) return i - j;
return -1;
}2. 约瑟夫环
问题来源是LeetCode 面试题62. 圆圈中最后剩下的数字(https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/)
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
解决问题的思路有哪些：
1. 循环链表：
相当于模拟过程，具体代码不展示
时间复杂度：O(mn) 空间复杂度：O(n)
2. 递归(非递归)
我们假设函数f(n,m)表示n个人每隔m个人淘汰一个人，最终留下来的那个人的编号。第一轮我们淘汰编号为m%n的人，此时剩下n-1个人，且下一轮第一个报号的人编号为m%n+1，也就相当于对于只有n-1个人的情况，所有人的编号往后平移m%n，我们假设f(n-1,m) = x，此时我们可以建立递推公式：
f(n,m) = (f(n-1,m) + m % n) % n = (x + m) % n......f(1,m) = 1时间复杂度：O(n) 空间复杂度：O(n)或O(1)
//递归
int lastRemain(int n, int m) {
if(n == 1)
return 1;
int lastRemain(n - 1, m) = x;
return (m + x) % n;
}
//非递归
int lastRemain(int n, int m) {
int x = 1;
for(int i = 2; i <= n; i++)
x = (x + m) % i;
return x;
} 3. 数学方法
假设初始编号为 1,2，…，n，现在考虑一种新的编号方式。
第一个人不会被踢掉，那么他的编号从n开始往后加 1 ，变成 n + 1，然后第二个人编号变为 n + 2，直到第 m个人，他被踢掉了。
然后第 m + 1个人编号继续加 1 ，变成了n + m，依次下去。
考虑当前踢到的人编号为km，那么此时已经踢掉了k个人，所以接来下的人的新编号为n + k(m -1) + 1…(如果没有踢掉人的话，经过k轮编号应该多了km，现在每一轮少一个编号)
所以编号为km + d的人编号变成了n + k(m - 1) + d，其中1 <= d < m。
直到最后，活下来的人的编号为mn（假设一共有n轮，活下来的那个人一定是在第n轮被踢掉的人，所以他的编号一定为nm）
接下来的问题就转换成怎么由新编号得知他之前的原始编号
我们假设第k轮时他的编号是N = n + k(m - 1) + d,那么他上一轮的编号是
km + d = km + N - n - k(m - 1) = k + N - n
递推公式：k + N - m = N(k) = k + N(k + 1) -m
k = (N -n - d)/(m - 1) = floor((N -n -1) / (m - 1))时间复杂度：O(logn) 空间复杂度：O(1)
int lastRemain(int n, int m) {
int N = n*m;
while(N > n) {
int k = floor((N -n -1) / (m - 1));
N = k + N -n;
}
return N;
}3. 投票算法（多数元素）
问题来源于LeetCode 169.多数元素(https://leetcode-cn.com/problems/majority-element/)
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
此题解题方法较多，且不难想到：
1. Hash表：
我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。
时间复杂度：O(n) 空间复杂度：O(n)
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> counts;
int majority = 0, cnt = 0;
for (int num: nums) {
++counts[num];
if (counts[num] > cnt) {
majority = num;
cnt = counts[num];
}
}
return majority;
}
}; 2. 排序
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为floor(n/2)的元素（下标从 0 开始）一定是众数。
时间复杂度：O(nlogn) 空间复杂度：O(logn)
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
}; 3. 分治
如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
我们可以使用反证法来证明这个结论。假设 a 既不是左半部分的众数，也不是右半部分的众数，那么 a 出现的次数少于 l / 2 + r / 2 次，其中 l 和 r 分别是左半部分和右半部分的长度。由于 l / 2 + r / 2 <= (l + r) / 2，说明 a 也不是数组 nums 的众数，因此出现了矛盾。所以这个结论是正确的。
这样以来，我们就可以使用分治法解决这个问题：将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。
时间复杂度：O(nlogn) 空间复杂度：O(logn)
class Solution {
int count_in_range(vector<int>& nums, int target, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; ++i)
if (nums[i] == target)
++count;
return count;
}
int majority_element_rec(vector<int>& nums, int lo, int hi) {
if (lo == hi)
return nums[lo];
int mid = (lo + hi) / 2;
int left_majority = majority_element_rec(nums, lo, mid);
int right_majority = majority_element_rec(nums, mid + 1, hi);
if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
return left_majority;
if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
return right_majority;
return -1;
}
public:
int majorityElement(vector<int>& nums) {
return majority_element_rec(nums, 0, nums.size() - 1);
}
}; 4. Boyer-Moore 投票算法
如果我们把众数记为 +1+1，把其他数记为 -1−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
Boyer-Moore 算法的本质和分治类似：
我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
2.1 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
2.2 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。在遍历完成后，candidate 即为整个数组的众数。
时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};4. 洗牌算法
转载知乎大佬程序员吴师兄的回答(https://www.zhihu.com/question/358255792/answer/974431591)
先来思考一个问题：有一个大小为 100 的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 1 个数？
最简单的方法是利用系统的方法 Math.random() * 100 ，这样就可以拿到一个 0 到 99 的随机数，然后去数组找对应的位置就即可。
接下来在思考一个问题： 有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 50 个数？注意数字不能重复！注意数字不能重复！注意数字不能重复！
如果根据上面的思路，你第一想法是：随机 50 次不就行了？但是，这样做有个很明显的 bug ：数字是会重复的。
修改一下？弄一个数组，把每一次随机的数都放到数组里，下一次随机就看这个数组里面有没有这数，有的话就继续随机，直到这个数组里面有 50 个数字就停止。这样是可以的！但，还是有个小问题，考虑一下极端情况：有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 99 个数。如果按照上面的方法操作，越往后选择的数字跟前面已经挑选的数字重复的概率越高，这就会造成如果数组很大，选择的数字数目也很大的话，重复次数在量级上会很大。
这个时候就需要换一个思路，如果先将数组里面的元素打乱，那么按顺序选择前 50 个不就可以了？
——–接下来就是响当当的洗牌算法出场了——–
这个算法很牛逼却很好理解，通俗的解释就是：将最后一个数和前面任意 n-1 个数中的一个数进行交换，然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换。。。
void shuffle(vector<int>& nums) {
int len = nums.size();
for(int i = len - 1; i >= 0; i--)
swap(nums[i], nums[rand(0,i)]);
}tips：其实就相当于是数学中的全排列，目前库里已经有shuffle函数，可以直接调用，在蚁群算法初始化蚂蚁位置还有遗传算法赌轮盘中还是很有用处滴！
