【找工作】C++和算法复习（自用）

自用随便记录

C++

排序
stl

头文件

全能头文件：

#include<bits/stdc++.h>

自定义排序函数

bool compare(const int &odd1,const int &odd2)
{return odd1>odd2;
}

stl

枚举map

  map<int, string> mapStudent;  mapStudent.insert(pair<int, string>(1, "student_one"));  mapStudent.insert(pair<int, string>(2, "student_two"));  mapStudent.insert(pair<int, string>(3, "student_three"));  map<int, string>::reverse_iterator  iter;  for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)  {  cout<<iter->first<<"   "<<iter->second<<endl;  }  

优先队列

算法

堆

数据结构

堆
图

树状数组

int tree[maxn<<2];
int lowbit(int x){return x & -x;
}
int get_sum(int idx){int sum = 0;while(idx){sum += tree[idx];idx -= lowbit(x);}return sum;
}
void update(int idx, int value){while(idx < LIMIT){tree[idx] += value;idx += lowbit(idx);}
}

数学

快速幂
gcd和最小公倍数（ab的最小公倍数=ab/gcd(ab)）

int gcd(int x, int y){if(x<y) return gcd(y, x);return y == 0?x:gcd(y, x%y);
}

ex_gcd
质数

字符串

manacher

找最长回文子串

void initialize(int n, char ch[maxn]){int nn = n<<1|1;for(int i = nn-1, j=n-1; i>=2; i-=2){ch[i] = '#';ch[i-1] = ch[j];}ch[0] = '#';
}void manacher(int n, char ch[maxn]){memset(d, 0, sizeof(d));//d[i]是不包括i在内的半径int mid = -1;int maxr = -1;for(int i = 0; i < n; i++){if(maxr>d[i]){int other = mid * 2 - i;d[i] = min(d[other], maxr-i);}while(i-d[i]>=0 && i+d[i]<n && ch[i-d[i]]==ch[i+d[i]])i++;d[i]--;if(i+d[i]>maxr){mid = i;maxr = i+d[i];}}
}

kmp

模式匹配
前缀函数https://oi-wiki.org/string/kmp/
特点1：“一个重要的观察是 相邻的前缀函数值至多增加 1。”
特点2：当不符合最优的增加1的情况的时候，如何快速找到下一个可以匹配的对象？
注意 前缀数组pi[0]=0!!!
其他情况下 表示的是重复前后缀的长度，比如对于abab字符串，pi[3]=2（有重复串ab）

KMP：给定一个文本 t 和一个字符串 s，我们尝试找到并展示 s 在 t 中的所有出现（occurrence）
力扣测试题：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

const int maxn = 1e4 + 10;
class Solution {
public:int pi[maxn];//前缀数组void get_pi(string s){int n = s.length();memset(pi, 0, sizeof(pi));for(int i = 1; i < n; i++){int j = pi[i-1];while(j != 0 && s[j] != s[i]){j = pi[j-1];}if(s[i] == s[j]) pi[i] = j+1;else pi[i] = 0;}}int strStr(string haystack, string needle) {int n_needle = needle.length();get_pi(needle);int n = haystack.length();int j = 0;for(int i = 0; i < n; i++){while(j != 0 && haystack[i] != needle[j]){j = pi[j-1];}if(haystack[i] == needle[j]){j++;}//printf("i:%d, ch:%c, j:%d, chj:%c\n", i, haystack[i], j, needle[j]);if(j == n_needle) return i - n_needle + 1;}return -1;}
};