面试常用算法归纳
注意：这里需要使用一个pair记录前一个dp[i]的最长子串的始末位置，在判断s[i]与s[i-1]不等时，需要继续往前判断s[i]是否包含在前一个dp[i-1]的子串中，如果在，则当前的dp[i]需要减去dp[i-1]子串的前一部分。对于二维dp的状态转移方程，大致都会是要从左、上及左上三个方向来推导，即：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1
算法时间复杂度
总结
for循环的时间复杂度往往是O(n)
树的高度的时间复杂度往往是O(lg(n))
二分查找的时间复杂度是O(lg(n))，快速排序的时间复杂度n*(lg(n))
二叉查找树的时间复杂度
通过 BST 查找节点，理想情况下我们需要检查的节点数可以减半。如下图中的 BST 树，包含了 15 个节点。从根节点开始执行查找算法，第一次比较决定我们是移向左子树还是右子树。对于任意一种情况，一旦执行这一步，我们需要访问的节点数就减少了一半，从 15 降到了 7。同样，下一步访问的节点也减少了一半，从 7 降到了 3，以此类推。
根据这一特点，查找算法的时间复杂度应该是 O(log2n)，简写为 O(lg n)。最佳情况是 O(log2n)，而最坏情况是 O(n)。
参考：二叉查找树
递归和分治
参考：一文教你学会递归解题
递归思维
- 不要思考整体，而是把目光聚焦局部。
解决递归相关的算法问题，就是一个化整为零的过程，你必须瞄准一个小的突破口，然后把问题拆解，大而化小，利用递归函数来解决。 - 定义好递归函数
明确递归函数的定义是什么，相信并且利用好函数的定义。这也是前文经常提到的一个点，因为递归函数要自己调用自己，你必须搞清楚函数到底能干嘛，才能正确进行递归调用。 - 结束递归的点
汉诺塔问题
力扣：https://leetcode.cn/problems/hanota-lcci/
力扣：241
参考：https://mp.weixin.qq.com/s/fcCJFk89w953gXDjnlZFIA
排序算法
最长子串、子序列
先说明下子串和子序列的问题：对于s = “pwwkew"来说，其中一个子串为"wke”，而"pwke" 是一个子序列。
子序列：一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
对于求最长子串、最长序列的问题：
基本上需要用到动态规划的dp数组来辅助。主要原因是，如果暴力求各个子串或者序列的话，算数量太大，容易超时。
在使用dp数组时，有两种类型，一种是一维的dp数组，一种是二维的dp数组。
一维dp
对于一个字符串或者数组中求最大值时，一般考虑一维的dp数组，并且对于其定义为dp[i]表示为从S[0]到S[i]间符合题意的最大值。但如果用这个定义会导致转移状态方程不好推导，dp[i]和dp[i-1]中间有断层，则需要考虑更改dp[i]的定义。可以考虑把dp[i]表示为以S[i]为结尾的子串或者子数组的符合题意的最大值，比如力扣如下题：
有断层
对于有断层的，一般都要在推导dp[i]时，需要在0 ~ i -1间找到一个最大的，来推导dp[i]。
最长递增子序列
对于dp数组的定义：
这个题是有断层的。如果把dp[i]定义为，nums[0 … i]子数组中的最长递增子序列的长度，那么当第i个元素要加入时，就会出现问题，如下图所示，当前nums[i]不好去找dp[i-1]的元素去比较，从而推导出dp[i]。此时需要更换对于dp[i]的定义。
当我们把dp[i]定义为：以nums[i]为结尾的子数组的最长递增子序列的长度。那么断层就不会出现，dp[i-1]中的子数组，永远会包含nums[i-1]自己。如下图：
那么我们就在比较dp[i]和dp[i-1]的大小，就能推导出dp[i]的值。也需要一种逆向思维，从转移公式开始去推导对dp[i]定义的修改。
对于dp数组的转移公式：
当我们要求dp[i]时，即需要把nums[i]插入进去。那么它应该在哪个位置比较合适呢？
这里最关键，如果不加思考，可能会觉得如果nums[i] > nums[i - 1]的话，就让dp[i] = dp[i -1] + 1。这里有个问题，就是原nums数组并不是有序的，你不能确保dp[i -1]就是dp[0] ~ dp[i -1]里头最大的那个啊！nums[i] < nums[i - 1]时的操作也一样。
最直观的方式就是，从i-1往前找，找到一个nums[j]小于等于nums[i]的，并且dp[j]是当中最大的，这样就可以推导出dp[i]了，因为dp[i]一定包含自己，那是否要包含[0 ~ i-1]中的元素，那就得去找到一个满足值小于自己的，并且dp又是最大的来计算。
另外，这里找到这么一个j后，还要看nums[j]是否与nums[i]，相等，如果相等，那么dp[i] = dp[j]；不相等（肯定是小于nums[i]的），则dp[i] = dp[j] + 1。
最大子数组和
对于dp[i]的定义为：以nums[i]为结尾的「最大子数组和」
无重复字符的最长子串
如果定义dp[i]为：s[0 … i]的【无重复字符的最长子串】的长度，那么就会有断层，我并不知道dp[i - 1]表示的那个满足题意的连续子串的位置在哪里，这样我也不好去推导dp[i]出来。如下图：
所以必须针对这个断层，修改定义。对于dp[i]的定义为：以s[i]为结尾的【无重复字符的最长子串】的长度。
在推导dp[i]时，需要去检测从start开始到i-1，处是否有nums[i]这个元素，对于dp[i]的值应该是从i-1开始到第一个出现nums[i]元素间的距离。
注意：这里需要使用一个pair<int, int>记录前一个dp[i]的最长子串的始末位置，在判断s[i]与s[i-1]不等时，需要继续往前判断s[i]是否包含在前一个dp[i-1]的子串中，如果在，则当前的dp[i]需要减去dp[i-1]子串的前一部分。
买卖股票的最佳时机
- 定义推导
这里如果定义dp[i]为[0 … i]里最大收益，那么同样是会出现断层，即买卖点不知道在哪里。这个时候我们一定要确定一个卖点时间。那么自然会把dp[i]定义为：第i天卖出股票能获得的最大收益。 - 状态转移方程推导：
这里如果按照前面的方式会进入一个误区，就是dp[i]由dp[i-1]来计算出来。但是你并不知道dp[i-1]是在哪天买入的。这里有一个非常重点的东西就是，收益最大，那么一定要买入价格最低，反正我都必须在第i天卖出。那就扫描数组的时候记录下[0 ~ i-1]区间里的最小值即可。
dp[i] = prices[i] - minPrices; 再注意更新下minPrices即可。
二维dp
如果涉及到两个字符串或者数组的，基本上需要用到二维dp数组。对于二维dp的状态转移方程，大致都会是要从左、上及左上三个方向来推导，即：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])。
-
- 最长公共子序列
这里对于dp的定义需要使用到二维数组，因为这里涉及到两个字符串。
定义dp[i][j]为：s1[0…i-1]及s2[0…j-1]两个字符串的【最长公共子序列】的长度。
dp[0][x]/dp[x][0]表示其中有一个是空字符串，那它们的最长公共子序列的长度自然为0；
转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
- 最长公共子序列
-
- 最长回文子序列
定义dp[i][j]为：s[i … j]之间的最长回文子序列的长度。
那么dp[i][j]要从dp[i+1][j-1]、dp[i][j-1]、dp[i+1][j]三者中取出。
当s[i] == s[j]时，比较简单，显然dp[i][j] = d[i+1][j-1] + 2
当s[i] != s[j]时，说明s[i]和s[j]不能同时出现在s[i…j]的最长回文子序列中。那么就只能在s[i]或者s[j]中取一个去加入到上一个回文子序列中，形成新的回文子序列。即dp[i][j] = max(dp[i][j-1], dp[i+1][j])
- 最长回文子序列
组合（子集）和排列
回溯算法
组合（子集）和排列的题一般用回溯法。回溯算法：当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止。
算法框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
组合（子集）和排列的区别
组合（子集）与排列是不同性质的概念。记住一点：排列是关乎顺序的，而组合（子集）是无关乎顺序的。
组合（子集）是无关顺序的，而排列是和元素顺序有关的，如 [1，2] 和 [2，1] 是同一个组合（子集），但 [1,2] 和 [2,1] 是两种不一样的排列。因此在算法上会有些许差别。
组合（子集）
组合（子集）分为三种情况：
- 原始数据互不相同，选择不能重复
- 原始数据有相同，选择不能重复
- 原始数据互不相同，选择能重复
子集（原始数据互不相同，选择不能重复）
这里有一个要素就是：当前元素选择完，即进入path后，下一个选择列表都是原始数据中在它后面的元素。这样必须使用一个start标签来表示，当前这一轮选择过程中的起始位置。
有两个点：
- 每次选择一个后，选择列表都是当期这个元素后面的元素。因此，需要一个标识起始位置的start，来确定每一层遍历过程中的起始值。
- 每次回溯回去时，都是找当前选择列表已做选择的下一个元素，加入到path中。因此，在进行下一次递归的时候，需要在当前的基础上加1。即：
backTrace(nums, path, i + 1);
// start: 表示当前选择列表在原始数组nums的起始位置
void backTrack(vector<int>& nums, vector<int> &path, int start) {
result.push_back(path);
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]);
backTrace(nums, path, i + 1);
path.pop_back();
}
}
子集 II（原始数据有相同，选择不能重复）
在【子集】的基础上，或者直接使用【子集】的解法，那么会出现重复的答案进入到result中。
对于原始数据有重复元素的，我们的第一步就是要先排序，让相同的元素排在一起，后面好操作。
第二步进行剪枝：
- 对于剪枝操作，基本上都是在进行选择前进行剪枝。
- 剪枝的关键是要针对i和start做处理。
当对i1位置的2加入到path后，很明显需要进入到i2处递归了（这是从【子集】的解答中得到的流程），但是i2位置的2跟前面i1位置的2是一样的，显然在遍历时需要跳过它（或者说这个2不应该在下一个选择的选择列表中，因为前面已经选择过2了）。那么自然而然的，我们需要去判断nums[i]是否与nums[i-1]相等，如相等，则剪枝。而这里i-1必须保证不能越界到start前面去，又显然的能推导只有在i>start时才需要做剪枝。
// start: 表示当前选择列表在原始数组nums的起始位置
void backTrack(vector<int>& nums, vector<int> &path, int start) {
result.push_back(path);
for (int i = start; i < nums.size(); i++) {
// 在做选择前进行剪枝
if (i > start && nums[i] == nums[i-1]) {
continue;
}
path.push_back(nums[i]); // 做出选择
backTrace(nums, path, i + 1);
path.pop_back(); // 撤销选择
}
}
组合总和（原始数据互不相同，选择能重复）
这个题是nums元素无重复，但可以重复选择。
这个题如果是不可以重复选择，那么比较简单。按照前面【子集】的方法，增加一个sum的变量记录当前path里的总和，在sum==target时，把path加入到result中，代码实现如下：
// start: 表示当前选择列表在原始数组nums的起始位置
void backTrack(vector<int> &nums, vector<int> &path, int start) {
if (sum == _target) {
result.push_back(path);
return;
} else if (sum > _target) {
return;
}
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]); // 做出选择
sum += nums[i]; // 总和增加
backTrace(nums, path, i + 1); // 递归到右边节点
path.pop_back(); // 撤销选择
sum -= nums[i]; // 总和减去
}
}
但是，这里允许元素重复选择。例如：[2,3,6,7]，在选择完2到path中，后你还可以继续在下一层递归中重复选择2到path中，从这点出发，很容易的就知道要把上面实现中的i+1改为i，这样让下一个递归的起始点还是i，表示这个值还是可以选择。
backTrace(nums, path, i); // 改为i
组合（子集）总结
总结就是，都是基于最基础的【子集】的流程框架，对于i的位置，即对【下一个选择列表】进行了不同的处理而已。
- 原始数据互不相同，选择不能重复【最基础】
- 原始数据有相同，选择不能重复
数据有相同的话，那我的【下一个选择列表】就需要去掉跟前一个已经处理的数据相同的数据。 - 原始数据互不相同，选择能重复
选择能重复的话，那我的【下一个选择列表】就依旧能以当前这个起始开始，已经能选择当前值。
排列
排列和组合的区别就是，每次都可以从原始数据的头开始取数据，也就是取过的数据，依旧可以取。关键在于排列是有顺序的，所以取到的数据放在第一个位置和第二个位置是不同的排列。
全排列（原始数据互不相同）
全排列的规律比较简单：如果我们选择了某个数，那么他的下一层的选择列表就是——除去这个数以外的其他数！
所以，根据前面的【子集】的解决思路，可以先把全排列写成下面这样：
void backTrace(vector<int> &nums, vector<int> &path) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
path.push_back(nums[i]);
backTrace(nums, path, i + 1);
path.pop_back();
}
}
跟【子集】对比就是少了一个start，以及结束条件不一样。这两点都比较容易理解。但是这个答案还是不正确，是因为，每次都从起始位置选，选择列表中对于【除去这个数以外的其他数】并没有体现出来。因此，我们也同样需要对其进行剪枝操作。
要做【除去这个数以外的其他数】，那我们可以添加一个已访问的表used来记住哪些在添加到path中已经访问了（其实每次去path路径里查也可以，这里使用哈希表来记录已访问的，时间效率上更快，一个O(N)，一个O(1)）。
void backTrack(vector<int> &nums, vector<int> &path) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used.count(nums[i])) { // 重点
continue;
}
path.push_back(nums[i]);
used.emplace(nums[i]);
backTrace(nums, path);
path.pop_back();
used.erase(nums[i]);
}
}
- 对于【除去这个数以外的其他数】，这里有一个要注意的点是：当原始数据互不相同的情况下，你可以使用一个已访问的表used或者在path中去查元素来解决，不访问重复的元素。但是如果当原始数据有相同的情况下，使用这种used或者path中查具体的元素就不合适了，因为，当前面已经有一个相同元素在used里的时候，你当前的这个元素直接就会放不进path，在
if (used.count(nums[i]))这里就直接排除了。所以这里建议使用原始数据的序号作为key值，放入到used中。这样一来，当原始元素存在相同的数据时，这个框架也能使用！
推荐的解法：
class Solution {
public:
vector<vector<int>> result;
vector<bool> used;
void backTrack(vector<int> &nums, vector<int> &path) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backTrack(nums, path);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> path;
used.resize(nums.size());
backTrack(nums, path);
return result;
}
};
另外，这里也没必要用到unordered_set这个复杂的数据结构，直接用数据做used记录最好，节约空间，并且时间复杂度都一样（都是O(1)）。
全排列 II（原始数据有相同的）
显然【全排列】算法直接往上用，会多处一些相同的序列。那么我们需要在【全排列】的算法框架上做剪枝。前面说了，剪枝就得在做选择前进行。
此次结合【子集 II】的解法：
- 排序
- 增加判断if (i > 0 && nums[i] == nums[i - 1])
但这还不够，这里有一个重要的点就是：如果当前数据和前一个相同的情况下，如果前一个数据没有使用到，那当前这个也不需要使用了（因为当前这个元素肯定是没有使用的，第一个if (used[i])能过，说明当前这个肯定是没有被使用的）。
所以，最终增加的剪枝判断就是：
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
整体解答：
class Solution {
public:
vector<vector<int>> result;
vector<bool> used;
void backTrack(vector<int> &nums, vector<int> &path) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) {
continue;
}
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) { // 2.
continue;
}
path.push_back(nums[i]);
used[i] = true;
backTrack(nums, path);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
std::sort(nums.begin(), nums.end()); // 1.
vector<int> path;
used.resize(nums.size());
backTrack(nums, path);
return result;
}
};
分割回文串
- 1、区分这里是一个组合还是一个序列
显然这里可以套用组合的模式。那么我们先写出来如下代码：
class Solution {
public:
vector<vector<string>> result;
vector<string> path;
void backTrack(string& s, int start) {
for (int i = start; i < s.length(); i++) {
path.push_back(?);
backTrack(s, i + 1);
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
backTrack(s, 0);
return result;
}
};
其中path里要装一个什么呢？按题意是要装一个搜索过一遍的字符串，且是满足回文的字符串。 每次执行backTrack时，都是以start为起点的一个搜索过程。那么就要看start到i这个字符串是否满足回文。那么就可以改为如下的代码：
for (int i = start; i < s.length(); i++) {
string tmp = s.substr(start, i - start + 1);
if (isHuiwen(tmp)) {
path.push_back(tmp);
backTrack(s, i + 1);
path.pop_back();
}
}
那么何时把path放到result中呢？显然是要在以start遍历到了s字符串尾的时候加入。因为path里的都是回文字符串，并且到s尾了，说明path.pop_back();是没有执行的，等于一层一层的递归到了s尾了，而且还没有开始回溯，那说明这个path里面的数据都是符合题意的，那就加入到result中。
void backTrack(string& s, int start) {
if (start == s.length()) {
result.push_back(path);
return;
}
组合、排列算法总结
- “排列”问题使用used数组来标识选择列表，而“子集、组合”问题则使用start参数来标识选择列表。
- 对于【原始数据有重复】的情况下，排列、组合都需要先排序，再剪枝。剪枝条件判断
if (i > 0 && nums[i] == nums[i-1])这一条完全一样。
组合、排列算法参考
搜索算法
搜索算法分为两种：DFS和BFS。其中DFS和回溯有些相似。
- DFS和回溯
DFS 是一个劲的往某一个方向搜索（一条路走到黑的算法，走不通了就往回走），而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置。 - DFS与BFS
找最短距离，使用BFS搜索。
因为DFS是一种一种的尝试，在把所有可能情况尝试完之前，无法确定哪个是最短，所以DFS必须把所有情况都找一遍，才能确定最终答案（DFS的优化就是剪枝，不剪枝很容易超时）。而BFS从一开始就是尝试所有情况，所以只要找到第一个达到的那个点，那就是最短的路径，可以直接返回了，其他情况都可以省略了，所以这种情况下，BFS更高效。
找某一个结果是否存在，使用DFS搜索
因为DFS会首先把一种可能的情况尝试到底，才会回溯去尝试下一种情况，只要找到一种情况，就可以返回了。但是BFS必须所有可能的情况同时尝试，在找到一种满足条件的结果的同时，也尝试了很多不必要的路径；
DFS（深度优先搜索）
岛屿的最大面积
这类题型使用DFS算法，在一个方向上递归搜索。注意以下几点：
- 以一个点为起始点，往四面八方搜索。因此一般的都要定义一个i/j的参数。
- 判断DFS的终止条件，一般是出界或者不满足题目条件
- 向四面八方搜索。这里一般是根据题意推断方向，二维数组一般是上下左右四个方向，再加上斜对角方向，多叉树，则是对应的子树。
- 根据题意适当的添加visited标识，或者直接修改原数组，用来规避重复搜索。
- DFS函数的返回值，有时候可以用作答案的累加计算等。
岛屿最大面积，解题可作为一个类似的模板：
class Solution {
public:
int n;
int m;
// 返回以grid[i][j]为起点搜索的岛屿个数
int dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || i > n - 1 || j < 0 || j > m - 1) {
return 0;
}
if (grid[i][j] == 0) {
return 0;
}
int count = 1; // 当前有一个岛屿
grid[i][j] = 0; // 把当前访问过的岛屿置位
count += dfs(grid, i - 1, j); // 上
count += dfs(grid, i + 1, j); // 下
count += dfs(grid, i, j - 1); // 左
count += dfs(grid, i, j +1); // 右
return count;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
int maxCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 从每一个满足条件的位置作为起始点，开启一轮DFS深度搜索
if (grid[i][j] == 1) {
maxCount = std::max(maxCount, dfs(grid, i, j));
}
}
}
return maxCount;
}
};
单词搜索
这里也是从一个点向上下左右四个方向搜索，但这里需要一个visited记录是否 已经搜索过了。
对于dfs的参数需要增加一个k，用来记录搜索比较word中的第几个词。
对于dfs的返回值，需要返回是否找到结果。递归去搜索上下左右时，总有一条路会找到结果，那么后面就不需要再继续搜索了。
代码：
class Solution {
public:
vector<vector<bool>> mask;
string _word;
bool dfs(vector<vector<char>>& board, int i, int j, int k) {
if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() ||
k >= _word.length()) {
return false;
}
if (mask[i][j] || board[i][j] != _word[k]) {
return false;
}
if (k == _word.length() - 1) {
return true;
}
mask[i][j] = true;
bool ret = false;
ret |= dfs(board, i - 1, j, k + 1); // 上
ret |= dfs(board, i + 1, j, k + 1); // 下
ret |= dfs(board, i, j - 1, k + 1); // 左
ret |= dfs(board, i, j + 1, k + 1); // 右
mask[i][j] = false;
return ret;
}
bool exist(vector<vector<char>>& board, string word) {
_word = word;
mask.resize(board.size());
for (int i = 0; i < mask.size(); i++) {
mask[i].resize(board[0].size());
}
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j] == word[0]) {
if (dfs(board, i, j, 0)) {
return true;
}
}
}
}
return false;
}
};
BFS（ 广度优先搜索）
BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。
BFS算法框架，关键数据结构：队列，已访问标记数组，步数。
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
queue<Node> q; // 核心数据结构
set<Node> visited; // 避免走回头路
q.push(start); // 将起点加入队列
visited.insert(start);
int step = 0; // 记录扩散的步数
while (!q.empty()) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
auto cur = q.front(); q.pop();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.push(x);
visited.insert(x);
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
二叉树的最小深度
换句话就是求根节点到所有叶子节点的【最小距离】，直接套用BFS的算法框架即可。
打开转盘锁
题意也是求一个最小次数，而且也有起点“0000”，终点target。套用BFS框架即可。
水壶问题
给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。
这里应该是求最小的步骤，假设起始是800，那么结束条件就是4xx或者x4x。这对应着BFS的特性。
参考：字面试题 —— 水壶问题
图论
主要是使用拓扑排序，解决依赖关系的问题。
图的建立
图的遍历
从一个起点开始，遍历这个当前点，然后循环依次遍历当前点的邻接点。
这里需要一个visited数组记录，当前点是否曾经被访问过，防止死循环。
框架如下：
// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;
/* 图遍历框架 */
void traverse(Graph graph, int s) {
if (visited[s]) return;
// 经过节点 s，标记为已遍历
visited[s] = true;
// 做选择：标记节点 s 在路径上
onPath[s] = true;
for (int neighbor : graph.neighbors(s)) {
traverse(graph, neighbor);
}
// 撤销选择：节点 s 离开路径
onPath[s] = false;
}
图的环路检查
课程表
在遍历图的基础上增加一个onPath的数组，记录当前节点是否在onPath上，如果在，则表示：当前深度递归寻找节点时，找到了自己。则存在循环。
for (int i = 0; i < numCourses; i++)
可能每个点单独形成了一个环，因此需要对每个点进行遍历检查。- for循环内部不置位onPath和visited
visited不用置位是因为，比如从2到0及之后的节点，遍历完后，没有环路，那么当1到0，开始检测时，就可以跳过了，因为0后面的节点都不含环路。
onPath不用置位的原因是，traverse内部，访问完当前节点后，onPath会恢复对应的值，因此对一个起始节点深度访问完后，onPath就恢复到了原始状态，因此不需要再置位。 - // visited[i] = false;
traverse内部的后续遍历中的visited[i]不需要置位为false。visited[i]表示的是，当前这个节点是否在一轮循环中访问过了，它是为了避免死循环。另外一个是用于对那些多头结点的图时进行的遍历。
bool haveCircy = false;
vector<bool> visited;
vector<bool> onPath;
void traverse(vector<vector<int>> &graphic, int i) {
if (onPath[i]) {
haveCircy = true;
}
if (visited[i] || haveCircy) {
return;
}
onPath[i] = true;
visited[i] = true;
for (auto e : graphic[i]) {
traverse(graphic, e);
}
onPath[i] = false;
// visited[i] = false;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graphic;
graphic.resize(numCourses);
for (auto &e : prerequisites) {
graphic[e[1]].push_back(e[0]);
}
onPath.resize(numCourses, false);
visited.resize(numCourses, false);
for (int i = 0; i < numCourses; i++) {
traverse(graphic, i);
}
return !haveCircy;
}
拓扑排序
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
- 拓扑排序前提是要图不含环路，所以需要判断一个图是否含环。
- 拓扑排序需要有一个path来记录路径，并且需要在后续遍历的时候记录。之所以拓扑排序的基础是后序遍历，是因为一个任务必须等到它依赖的所有任务都完成之后才能开始开始执行。
课程表 II
class Solution {
public:
vector<int> path;
bool haveCir = false;
vector<bool> visited;
vector<bool> onPath;
void traverse(vector<vector<int>> &graphic, int i) {
if (onPath[i]) {
haveCir = true;
}
if (visited[i] || haveCir) {
return;
}
onPath[i] = true;
visited[i] = true;
// 深度搜索
for (auto &e : graphic[i]) {
traverse(graphic, e);
}
onPath[i] = false;
// 后序记录
path.push_back(i);
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
onPath.resize(numCourses, false);
visited.resize(numCourses, false);
// 建图
vector<vector<int>> graphic;
graphic.resize(numCourses);
for (auto &e : prerequisites) {
graphic[e[0]].push_back(e[1]);
}
// 图遍历
for (int i = 0; i < numCourses; i++) {
traverse(graphic, i);
}
// 拓扑不能有环
if (haveCir) {
return vector<int>{};
}
return path;
}
};
对于onPath/visited也可以改为使用
unordered_map<string, bool> visited;
unordered_map<string, bool> onPath;
因为unordered_map的这种操作：onPath[s] = true; visited[s] = true;，是不需要向vector一样先分配好初始大小的。所以尽量建议使用unordered_map。
二叉树
二叉树的中序遍历（非递归）
从根节点开始一直往左子树节点访问，并入栈。
当碰到左子树为空时，停止。出栈一个节点，访问它。然后让p指向它的右节点，继续上一步。
// 二叉树的非递归中序遍历
void inverser(TreeNode* root) {
auto p = root;
stack<TreeNode*> s;
while(p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top();
cout<<p->val<<" ";
s.pop();
p = p->right;
}
}
}
二叉树的后续遍历（非递归）
算法思想：
1、沿着根的左孩子，依次入栈，直到左孩子为空；
2、读栈顶元素进行判定，若右孩子不空且未被访问，将右孩子执行第一步；
3、栈顶元素出栈。
字符串问题
一般对字符串的问题，可以采用的解决办法有如下几种：
- 同向双指针（滑动窗口）
- 相向双指针
- dp数组（动态规划）
滑动窗口
滑动窗口算法过程：
- 定义两个指针：left = right = 0
- 开始让right向右移动，并判断[left, right)间的数是否满足要求，right向右移动，直到满足要求为止 【找到了一个解】
- 开始让left向右移动，直到[left, right)不满足要求 【优化上一步找到的解】
- 重复上述两步，直到right到达字符串尾
滑动窗口算法通常适用于以下类型的问题：
- 子数组和子字符串问题： 求最大、最小、连续、不重复等子数组或子字符串的问题。
- 匹配问题： 在字符串中找到符合某种条件的子串或子数组。
- 字符频率问题： 统计窗口内某些字符的频率等。
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
在用滑动窗口解时，一定要构造这样一个用例：bcafaxxxxxx。当j来到第二个a时，下一步更新i就直接更新到f这个位置开始下一轮的判断了。所以需要一个哈希表记录者前面所过得字符所在数组的位置，方便更新用。而判断是否有相同的字符时，则需要另外一个哈希表记录。
其他的滑动窗口解的问题：
30. 串联所有单词的子串
76. 最小覆盖子串
159. 至多包含两个不同字符的最长子串
209. 长度最小的子数组
239. 滑动窗口最大值
567. 字符串的排列
632. 最小区间
727. 最小窗口子序列
找出连续子数组之和等于k
给你一个整数数组 nums 和一个整数 k ，找出第一个连续子数组之和等于k。如果有返回这个子数组，找不到返回空。
例如：nums = [9,5,4,8,9,1], k = 17。它的连续子数组为：[5,4,8]
用滑动窗口，从头开始挪动第二个指针，找到合适的子数组。
双指针
最长回文子串
- 求回文，从中心向两端扩散的双指针技巧。
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r)
- 求最长回文子串
for 0 <= i < len(s):
找到以 s[i] 为中心的回文串
找到以 s[i] 和 s[i+1] 为中心的回文串
更新答案
盛最多水的容器
双指针，left、right，从两边往中间挤，求出最大的矩形面积即可。因为两边往中间挤，这样宽会慢慢变小，如果所有高都一样的情况下，第一次计算的面积就是最大面积，这样宽的变化可以去掉。接下来讨论高的影响。
每次判断height[left]和height[right]，哪个值小，让对应的下标挪动。因为你如果移动较低的那一边，那条边可能会变高，使得矩形的高度变大，进而就「有可能」使得矩形的面积变大；相反，如果你去移动较高的那一边，矩形的高度是无论如何都不会变大的，所以不可能使矩形的面积变得更大。
- 替换后的最长重复字符
链表问题
合并链表
必定要先new一个头结点，最后返回这个头结点的next指针即可。
链表是否相交
A/B两个链表是否相交，可以同时遍历 A-B/B-A这两条链表，如果相交，必定在遍历时同时碰到。
是否有环
判断链表是否有环，是通过快、慢指针来处理。如果有环，那么快指针一定会在一个时间上套圈慢指针，即它们会相等。对于判断链表有环的题目会比较明显，而下面这个【快乐数】的问题，比较隐晦。
快乐数
不是快乐数的，特点，比如2：
2 -> 4 -> 16 -> 37 -> 51 -> 26 -> 40 -> 16（环）...
而是快乐数的，特点，比如19：
19 -> 82 -> 68 -> 100 -> 1 -> 1 -> 1 .....（永远为1）
从这可以想到使用快慢指针去做，有环时就不是快乐数，而没有环的情况下，快指针是永远追不到慢指针的，因此最终慢指针指向了1，就是快乐数结束条件了。因为如果是快乐数，是没有环的，这个链条会一直持续下去，采用【快慢指针破循环】。
反转链表
总结：其实用迭代（非递归）的方法更简单。
反转整个链表
简单的可以采用头插入的方法。但这里为了后面复杂的反转链表，这里需要知道使用递归的方式来处理。
递归流程：1、定义函数签名表示的意思 2、结束（最小）条件 3、下一个递归项
函数签名：ListNode* reverseList(ListNode* head) ，表示翻转以head为头结点的链表，并返回翻转后的链表的头节点。
结束（最小）条件：当只有一个节点，或者节点为空。一个节点，那不需要执行翻转，为空时直接返回空。
下一个递归：递归翻转head->next。然后连接两段。
ListNode* reverseList(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
if (head->next == nullptr) {
return head;
}
auto last = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return last;
}
- 非递归方法（迭代方法）
ListNode* reverseList(ListNode* head) {
if (!head) {
return head;
}
auto tail = head;
auto p = head;
while(p) {
auto tmp = p->next;
p->next = head;
head = p;
p = tmp;
}
tail->next = nullptr; // 让链表有结尾
return head;
}
这里有另外一个版本，就是定义一个pre和cur，pre指向cur的前面一个节点，初始设置pre=nullptr，设置为null后，在第一轮while循环中，就把这个链表尾部节点的next指针置空了，就不需要tail->next = nullptr;这一行了。
ListNode* reverse(ListNode* head) {
ListNode* cur, *pre;
pre = nullptr; // 注意这里的初始化
cur = head;
while(cur != nullptr) {
auto tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
翻转链表前N个节点
跟上述一样，采用递归的方法。定义的函数签名为：ListNode* reverseList(ListNode* head, int n)表示翻转以head为头节点的链表前n个节点，并返回翻转后的链表头结点。
这里注意翻转到最后时，即翻转到第n个节点时，需要记录下第n+1个节点。
ListNode* reverseList(ListNode* head, int n) {
if (n == 1) {
tail = head->next; // 需要记录下第n+1个节点
return head;
}
auto last = reverseList(head->next, n - 1);
head->next->next = head;
head->next = tail;
return last;
}
翻转链表的一部分
这里的思路是，当left=1时，这个题目变为【翻转链表前N个节点】，那么我们在递归的时候，尽量往【翻转链表前N个节点】这个题目上靠。
当翻转[m,n]间点的元素，如果我们把head的索引视为 1，那么我们是想从第m个元素开始反转对吧；如果把head.next的索引视为 1 呢？那么相对于head.next，反转的区间应该是从第m - 1个元素开始的；
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
- 迭代的方法
翻转ListNode* left和ListNode* right之间的节点。参考【反转整个链表】的迭代方法。【反转整个链表】其实就是翻转head到nullptr之间的节点。那这里其实就是把nullptr替换为right即可。
ListNode* reverse(ListNode* left, ListNode* right) {
ListNode* cur, *pre;
pre = nullptr; // 注意这里的初始化
cur = head;
while(cur != nullptr) {
auto tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
如果要实现翻转前m,n直接的元素，则函数签名需要：ListNode* reverse(ListNode* head, ListNode* left, ListNode* right)
K个一组翻转链表
函数签名：ListNode* reverseKGroup(ListNode* head, int k)
同样使用递归的办法。
- 1、先翻转head为表头的前K个元素，找到第K个元素，使用接口
ListNode* reverse(ListNode* left, ListNode* right)来完成 - 2、调用
reverseKGroup翻转剩余部分 - 3、把第一步和第二步，连接起来。这里有个关键就是，
ListNode* reverse(ListNode* left, ListNode* right)返回了翻转后的新头结点，但它的尾节点就是left，需要利用这一点做到连接。
ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0; i < k; i++) {
// 不足 k 个，不需要反转，base case
if (b == null) return head;
b = b.next;
}
// 反转前 k 个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}
区间问题
这是一类问题，计算区间重叠个数。
问题概述：给你很多形如[start,end]的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。举个例子，intvs=[[1,3],[2,4],[3,6]]，这些区间最多有两个区间互不相交，即[[1,3],[3,6]]，你的算法应该返回 2。注意边界相同并不算相交。
算法步骤：
- 按end给原始数据从小到大排序
- 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
- 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
- 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集
框架如下：
int intervalScheduling(vector<vector<int>>& intervals) {
// 排序
sort(intervals.begin(), intervals.end(), [] (vector<int> &a, vector<int> &b) {
if (a[1] < b[1]) {
return true;
} else {
return false;
}
});
int end_x = intervals[0][1]; // 初始时是第一个值的end
int count = 1; // 不相交个数
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= end_x) {
// 不相交
end_x = intervals[i][1];
count++;
}
}
}
无重叠区间
结果为：intervals.size()减去不相交的个数。
备忘录
使用备忘录剪枝。
在遍历或者运行过程中采用一个unordered_map的键值对记录下某个key的值，然后在后面的计算过程中，如果发现有这个key的值，则直接从备忘录中拿出来使用。
其他
两个栈实现一个队列
力扣：剑指 Offer 09. 用两个栈实现队列
最长回文字符串
参考：https://mp.weixin.qq.com/s/ux6VSWAPwgOS32xlScr2kQ
N数之和问题
两数之和
2数之和，可以采用头尾双指针求得。多数之和，比如3数之和，就固定一个数，在剩余的数中求一个2数之和。4数之和，就是固定一个数，在剩余的数中求一个3数之和。
coins硬币问题
最少的硬币数目
采用动态规划，定义dp[i]为：总金额 i所需的最少的硬币个数。
括号匹配
括号匹配，一般都是用两个栈去做。毕竟你不知道括号是否匹配。
一个操作符栈，一个数据栈。操作符栈放’('，数据栈放入字符数据，当碰到‘)’时，则数据栈中的所有数据
反转每对括号间的子串
多链表合并
/// 请实现下面这个函数，其功能为打印多个链表中出现相同的元素 ///
/// @param lists 多个链表,lists[i]表示第i个链表的表头 ///
/// 每个链表都是升序排序好的 ///
/// 需要考虑链表中的重复元素 ///
/// 例子1 ///
/// list[0]: 2->2->2->3->4->5 ///
/// list[1]: 2->5->7->8 ///
/// 输出:2->5 ///
/// 例子2 ///
/// list[0]: 2->2->2->3->4->5 ///
/// list[1]: 2->2->5->7->8 ///
/// 输出:2->2->5 ///
面试算法题
20亿个电话号码去重
参考：腾讯三面：40亿个QQ号码如何去重
参考：【数据结构】BitMap的理解与应用
求4个数组中和为0的元组有多少个
给定4个数组A B C D，然后计算一个元组[i,j,k,l]，满足A[i]+B[j]+C[k]+D[l]=0，这样的元组[i,j,k,l]的个数。
比如：A[0, 0] B[2, -1] C[-1, 1] D[0, -1]，结果有4对满足。
思路：计算AB和CD相互间所有的和，用一个map记住。map的key是和，value是这个和出现的次数。
然后再遍历map1，当找到一个key时，则在map2中找对应的-key，即可。
数学接口
头文件：#include<math.h>
求根：sqrt(double)
次方：pow(2, 3) 2的3次方
算法总结
- 求连续子串或者子数组，采用滑动窗口。
- 求最值问题，考虑动态规划。【参考硬币问题】
- 在字符串、数组里求最长（大）之类的，可以考虑动态规划，注意dp定义及断层问题。关键字：【最大】
- 求起点到重点的最短距离，用BFS算法。关键字：【最小】、【目标】
- 求某一结果是否存在，用DFS算法。关键字：【有或者没有】、【可达】、【是否存在】
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
6
0- 0
已为社区贡献2条内容
所有评论(0)