总结
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[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数组。对于二维dp的状态转移方程，大致都会是要从左、上及左上三个方向来推导，即：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])。
组合（子集）和排列的题一般用回溯法。回溯算法：当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止。
算法框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
组合（子集）与排列是不同性质的概念。记住一点：排列是关乎顺序的，而组合（子集）是无关乎顺序的。
组合（子集）是无关顺序的，而排列是和元素顺序有关的，如 [1，2] 和 [2，1] 是同一个组合（子集），但 [1,2] 和 [2,1] 是两种不一样的排列。因此在算法上会有些许差别。
组合（子集）分为三种情况：
这里有一个要素就是：当前元素选择完，即进入path后，下一个选择列表都是原始数据中在它后面的元素。这样必须使用一个start标签来表示，当前这一轮选择过程中的起始位置。
有两个点：
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();
}
}
在【子集】的基础上，或者直接使用【子集】的解法，那么会出现重复的答案进入到result中。
对于原始数据有重复元素的，我们的第一步就是要先排序，让相同的元素排在一起，后面好操作。
第二步进行剪枝：
// 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]);
}
}
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】的解法：
但这还不够，这里有一个重要的点就是：如果当前数据和前一个相同的情况下，如果前一个数据没有使用到，那当前这个也不需要使用了（因为当前这个元素肯定是没有使用的，第一个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;
}
};
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;
}
if (i > 0 && nums[i] == nums[i-1])这一条完全一样。搜索算法分为两种：DFS和BFS。其中DFS和回溯有些相似。
这类题型使用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 可以找到最短距离，但是空间复杂度高，而 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++)
traverse内部，访问完当前节点后，onPath会恢复对应的值，因此对一个起始节点深度访问完后，onPath就恢复到了原始状态，因此不需要再置位。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）的所有顶点的线性序列。且该序列必须满足下面两个条件：
有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
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、栈顶元素出栈。
一般对字符串的问题，可以采用的解决办法有如下几种：
滑动窗口算法过程：
滑动窗口算法通常适用于以下类型的问题：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
在用滑动窗口解时，一定要构造这样一个用例：bcafaxxxxxx。当j来到第二个a时，下一步更新i就直接更新到f这个位置开始下一轮的判断了。所以需要一个哈希表记录者前面所过得字符所在数组的位置，方便更新用。而判断是否有相同的字符时，则需要另外一个哈希表记录。
其他的滑动窗口解的问题：
30. 串联所有单词的子串
76. 最小覆盖子串
159. 至多包含两个不同字符的最长子串
209. 长度最小的子数组
239. 滑动窗口最大值
567. 字符串的排列
632. 最小区间
727. 最小窗口子序列
给你一个整数数组 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;
}
跟上述一样，采用递归的方法。定义的函数签名为：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* 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)
函数签名：ListNode* reverseKGroup(ListNode* head, int k)
同样使用递归的办法。
ListNode* reverse(ListNode* left, ListNode* right)来完成reverseKGroup翻转剩余部分 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。注意边界相同并不算相交。
算法步骤：
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
2数之和，可以采用头尾双指针求得。多数之和，比如3数之和，就固定一个数，在剩余的数中求一个2数之和。4数之和，就是固定一个数，在剩余的数中求一个3数之和。
采用动态规划，定义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 ///
参考：腾讯三面：40亿个QQ号码如何去重
参考：【数据结构】BitMap的理解与应用
给定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次方