算法

算法	应用
BFS广度优先搜索
DFS深度优先搜索
回溯法(DFS+剪枝)	部分和问题
分治法	快速排序、归并排序
动态规划	背包问题
贪心法	Dijkskra(最短路径)、Prim/Kruskal(最小生成树)

字符串

字符串的旋转

• 三步反转

abcdef
cba fed
defabc

字符串的包含

• 排序后轮询
• 素数相乘
• 位运算法

hash = 0;
hash |= (1<<(a[i]-'A'));
(hash & (1<<(b[i]-'A'))) == 0;

字符串的全排列

• 字典序排列

// 二找、一交换、一翻转
* 找到排列中最后(最右)一个升序的首位位置i,x=ai
* 找到排列中第i位右边最后一个比ai大的位置j,y=aj
* 交换x和y
* 把第i+1位到最后的部分翻转

21543
1 3
2 3 54 1
23145

字符串转化成整数

isspace();
sign;
isdigit();
sign==1&&(n>INT_MAX/10||(n==INT_MAX/10&&t>INT_MAX%10));
sign==-1&&(n<INT_MIN/10||(n==INT_MIN/10&&-1*t<INT_MIN%10));

回文判断

• 两头往中间扫
• 中间往两头扫

最长回文子串

• 中心扩展法
• Manacher算法

回文素数

2,3,5,7,11;
s.size() % 2 != 0;
n % 6 != 1 || n % 6 != 5;

寻找最小的k个数

• 用堆代替数组

寻找和为定值的两个数

• 散列映射
• 排序夹逼

寻找和为定值的多个数

• n问题转换为n-1问题
• 回溯剪枝

最大连续子数组和

• 动态规划

跳台阶问题

• 动态规划

最大连续乘积子数组

• 动态规划