1、全排列
[leetcode] 46.全排列
解法一：不修改原始数组，使用visited记录已使用过的元素，以及level记录已排列的个数；
解法二：通过交换start的元素实现；
解法三：逐渐增加排列的元素数目；
[leetcode] 47.全排列II
解法一：不修改原始数组，使用visited记录已使用过的元素，以及level记录已排列的个数，但需要排除当前一个数字已经排列过的情况，即
nums[i] == nums[i - 1] && visited[i - 1] == 0
解法二：通过交换start的元素实现，但需要排除当前一个数字已经排列过的情况，即
while (j >= start && nums[j] != nums[i]) --j;
if (j != start - 1) continue;
解法三：逐渐增加排列的元素数目，使用set去除重复结果；
set<vector<int>> res;
[leetcode] 60.序列排序：给定你n和k，返回第k个排列。
解法一：记录n！
f[i] = f[i - 1] * i;
2、数组相关
[leetcode] 55.跳跃游戏：有一个非负整数的数组，每个数字表示在当前位置的基础上最多可以走的步数，求判断能不能到达最后一个位置。
解法一：动态规划Dynamic Programming来解，dp[i]表示达到i位置时剩余的步数，由上一个位置的剩余步数和上一个位置的可以跳的最大步数有关。
dp[i] = max(dp[i - 1], nums[i - 1]) - 1
当某一个时刻dp数组的值为负时，返回false，否则返回true；
解法二：贪婪算法Greedy Algorithm，记录当前能到达的最远位置，当不能到达当前位置时返回false，或能到达终点返回true。
[leetcode] 45.跳跃游戏II：求到达最后一个位置的最少跳跃数，默认一定能到达最后位置。
解法一：贪婪算法Greedy，找到当前位置一个能到达的最远范围，我们遍历当前跳跃能到的所有位置，然后根据该位置上的跳力来预测下一步能跳到的最远距离，贪出一个最远的范围，一旦当这个范围到达末尾时，当前所用的步数一定是最小步数。
解法二：
3、字符串相关
3.1回文字符串
[LeetCode] 5.最长回文子串：返回一个字符串中最长的回文子串。
解法一：遍历字符串中每个字符或每两个字符，分别向两边扩展left--和right++，返回s.substr(start, maxLen)；
解法二：在解法一的基础上利用右边剩余长度n-i<maxlen/2时直接break，并保持left不变，向右遍历跳过重复项right++（此时包含长度为偶数的情况）；
解法三：动态规划，维护一个二维数组 dp，其中 dp[i][j] 表示字符串区间 [i, j] 是否为回文串，如下
dp[i, j] = 1 if i == j
= s[i] == s[j] if j = i + 1
= s[i] == s[j] && dp[i + 1][j - 1] if j > i + 1
解法四：马拉车算法 Manacher‘s Algorithm，时间复杂度O(n)。
1）插入“#”得 t[i] ：#n#o#o#n#
2）获取数组p，p[i] 表示以 t[i] 字符为中心的回文子串的半径
[LeetCode] 9.验证回文数字：验证数字是否为回文数字。
解法一：利用取整/和取余%
解法二：求数字X倒序的数reverseX，并判断是否相等
[LeetCode] 125.验证回文字符串：判断是字符串是否为回文，包括空格和非字母数字的字符，跳过非字母数字的字符。
解法一：构建判断是否为字符的，‘A‘是65而‘a‘是97，相差32；
[LeetCode] 131.拆分回文串：返回所有可能拆分成回文子串的情况
解法一：DFS深度优先搜索，遍历拆分第一刀的位置，判断是否为回文字符isPalindrome，再遍历第二刀的位置；
解法二：递归方法，调用递归函数返回剩下字符串的切分，并将目前的切分插入进去。
解法三：动态规划，先建立字符串s的子串回文的dp数组，dp[i][j] 表示 [i, j] 范围内的子串是否为回文串，代替解法一中的判断会问字符串函数；
解法四：构建一个二维数组dp[j][i]同前，同时构建一个三维数组res，其中res[i]表示前i个字符组成的子串，当dp[j][i] 为true则将res[j]的组合与当前子串一起加入res[j+1]中。
[LeetCode] 132.拆分回文串之二：返回将原字符串拆分成回文串的最小切割数。
解法一：动态规划，使用两个动态规划，dp[i]记录[0,i]范围子串最小分割数，初始化为dp[i]=i，用j遍历[0,i]区间，二维数组p[j][i] 表示区间 [j, i] 内的子串是否为回文串，p[j][i] =(s[i]==s[j])&&p[j+1][i-1]，当p[j][i]==true时若j=0,dp[i]=0，若j>0,dp[i]=dp[j-1]+1；
解法二：
4、查找
5、回溯
[LeetCode] 10.正则化匹配：*匹配之前字符串0个，1个或多个，.匹配一个任意字符
解法一：针对第二个是否为“*”，进行if判断；
解法二：使用dp记录是否匹配
[LeetCode]44.外卡匹配：*匹配任意字符串，？匹配一个任意字符
解法一：记录p中*位置以及s串中*匹配到的位置，然后遍历s和p；
解法二：使用dp[m+1][n+1]记录是否匹配
[LeetCode]46.全排列（无重复）
[LeetCode]47.全排列（有重复）
[LeetCode]51.N-Queen（输出解）
[LeetCode]52.N-Queen（输出解的个数）
[LeetCode]37.数独
[LeetCode]39.组合之和（可重复使用）
[LeetCode]40.组合之和（不可重复使用）
解法一：回溯，类似全排列
[LeetCode]17.电话号码的字母组合
解法一：类似全排列，递归和循环方法
[LeetCode]22.生成括号
解法一：类似全排列，以及二叉树遍历
原文：https://www.cnblogs.com/chengmm/p/11382180.html