LCR 051. 二叉树中的最大路径和
Note: 直径DP。树有关的DP基本都是子节点上报信息给父节点（如打家劫舍III中的树形DP）。把题中所指的路径想象成圆的直径，经过的最顶上的根节点就是圆的圆心，从圆心往两侧的两条子路径是圆的半径，要求最大直径，很明显，两条半径也需要最大（它们本身不互相影响），因此需要求出每个节点其左子树最大的根->叶子路径和（最大左半径），以及右子树最大的根->叶子路径和（最大右半径），然后加上原节点的值，其和即为该节点为圆心的最大直径，但是要注意的是，并非左右半径都需要包含，如果某侧最大半径为负值，那么就没必要加上这条半径，因此取每侧最大半径和0二者的最大值，然后和根节点值加和得到当前节点的最大路径和（最大直径），此后还要注意的是，要上报的仍然是最大半径而非直径，因此取当前节点值+max(最大左半径, 最大右半径)来上报。
LCR 055. 二叉搜索树迭代器
Note: 方法一：在初始化时将树扁平化（中序遍历）存放在数组中，之后直接迭代即可，这种方式需要O(n)的空间；方法二：在每次迭代时模拟中序遍历迭代法，先生长，生长不动了再从栈中取出一个作为next，然后移动到next的右指针。这种方法只占用O(h)的空间，而且由于每个节点只入栈出栈一次，因此n次操作时间为O(n)，均摊时间复杂度O(1)。
LCR 056. 两数之和 IV - 输入二叉搜索树
Note: 四种方法：递归+哈希表，迭代+哈希表（实际这两种完全一样），递归+双指针（需要先扁平化，最不推荐），迭代+双指针（为两个指针分别设一个栈，然后按类似上题的迭代方法来移动指针，平均空间复杂度理论是最优的）。
LCR 057. 存在重复元素 III
Note: 本题有点SB，因为暴力解法甚至比正解要快，为什么呢，因为题目数据全是卡你边界数值的，然后数据量都非常小，结果暴力反而快……。对于正解，首先基本思想是滑动窗口，实际本题就是求一个数x左侧的最大大小为k的窗口中，是否有值在[x - t, x + t]范围的数（也就是和x距离不大于t的数）。方法一是使用有序集合set来储存窗口中的数，然后用二分（C++ map内置的lower_bound函数）去找窗口中≥ x - t的最小数，然后比较其是否≤ x + t如果是，则找到答案，注意维护窗口。方法二是使用桶的思想，主要是将整个整数集合分割成多个大小为t + 1的桶，每个桶内的数除以t + 1的商相等，那么同一个桶内的两个数距离最多为t（两端点距离，也就是长度t + 1再-1），满足题目要求；如果两个满足题意的数不在一个桶内，那么他们一定在相邻桶，否则它们的最小距离就会是t + 2(桶大小+1)，不满足题目要求。此时就检查这两个数是否距离不大于t，是的话，就找到答案。由于只要找到两个数在一个桶内即结束，因此这种情况（相邻桶）下，每个桶内最多一个数，所以桶可以用map来存储。而这里由于数值可以取到int的最大和最小值，因此所有数值都使用long以防止溢出。
另外上述方法有一个很大的缺陷，由于C++除法向0取整，因此桶[-k, 0]和[0, k]内的数对t + 1的商都是0，造成两个桶内数被视为同一个桶内的数，但是并不一定满足题意。两种解决办法：官解：对于负数桶采取向左偏移1的办法，因此原来映射到0的负数桶[-k, 0]就映射到-1，但是这一方法属实抽象；另外一种方法就是把所有数变成非异号（可以减去INT_MIN全部变为非负，或者减去INT_MAX全部变为非正），也可以避免上述情况。
class Solution {
public:
long getBucketID(long x, long w) {
return (x - INT_MAX) / w;
}
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
// 滑窗+有序集合
set<long> window;;
int n = nums.size();
for (int i = 0; i < n; ++i) {
auto iter = window.lower_bound((long)nums[i] - t);
if (iter != window.end() && *iter <= (long)nums[i] + t) {
return true;
}
window.insert(nums[i]);
if (i >= k) window.erase(nums[i - k]);
}
return false;
// 桶
unordered_map<int, int> bucket;
int n = nums.size();
long w = t + 1ll, x, bucketID;
for (int i = 0; i < n; ++i) {
x = nums[i];
bucketID = getBucketID(x, w);
if (bucket.count(bucketID)) return true;
if (bucket.count(bucketID - 1) && abs(x - bucket[bucketID - 1]) <= t) return true;
if (bucket.count(bucketID + 1) && abs(x - bucket[bucketID + 1]) <= t) return true;
bucket[bucketID] = x;
if (bucket.size() > k) bucket.erase(getBucketID(nums[i - k], w));
}
return false;
}
};
LCR 058. 我的日程安排表 I
Note: 本题就是一个分步的区间合并，由于一开始没有全部的区间列表，因此无法排序，但是可以使用一个排序的数据结构，比如set，使用自定义的排序规则（新建一个节点数据类型，重载其<运算符）。这里记录一下set插入的规则，首先找到待插入节点key_val的lower_bound，也就是≥ key_val的最小节点，如果lower_bound不为空，并且key_val < lower_bound不成立（根据数据结构中<的具体语义确定），那么插入失败，否则插入成功。这里的原理是，lower_bound的前一个节点（如果有）很明显是< key_val的（否则它才是lower_bound），此时如果key_val < lower_bound不成立，那么根据set插入规则，插入节点和lower_bound在语义上是重复的，因此插入失败，否则符合插入规则，可以插入。另外，如果lower_bound为空，那么所有节点都< key_val，那么待插入节点直接插在最后即可。
struct Node {
int start, end;
Node(int _start, int _end): start(_start), end(_end) {};
bool operator < (const Node& rhs) const {
return end <= rhs.start;
}
};
class MyCalendar {
public:
MyCalendar() {
}
bool book(int start, int end) {
return calenders.insert(Node{start, end}).second;
}
private:
set <Node> calenders;
};
LCR 061. 查找和最小的 K 对数字
Note: 本题与前两题类似，都是使用了优先队列，不过具体操作有所不同，由于两个数组均正序排好，因此最小的一对和一定是num1[0]和nums2[0]，之后需要选择的是nums1[1] + nums2[0]或者nums1[0] + nums2[1]，只有这两个组合可能是第2小的。以此类推，假设我们已经找到前m小的数对和索引(a0, b0) …… (am-1, bm-1)，那么下一个最小的数对和索引应该从(a0 + 1, b0), (a0, b0 + 1) …… (am-1 + 1, bm-1), (am-1, bm-1 + 1)中选，也就是说，每次选出一个当前最小数对和索引对(a, b)（使用优先队列，小顶堆），就把(a + 1, b)和(a, b + 1)放入优先队列，等待下一次筛选。
但是这样可能会产生重复，因此我们需要固定一边的索引，选择固定nums1的索引，每次取出数对(a, b)，只将(a, b + 1)放入优先队列，为避免遗漏，预先将(0, 0) …… (min(k, nums1.size()) - 1, 0)放入优先队列（min(k, nums1.size())主要是防止越界，而只选择前k个nums1的索引进入队列，是因为对于索引对(k, 0)，其已经大于等于至少k个数对（就是(0, 0) …… (k - 1, 0)）），因此其不可能是前k小数对，没必要在初始时放进队列，而如果nums2[1]特别大，则上述k个索引对就可能成为前k小的数对和。重复上述过程直到有k个元素出队，或者优先队列空为止。
LCR 062. 实现 Trie (前缀树)
Note: 字典树，或称前缀树，是一种用于高效储存和检索字符串的数据结构，树中每个节点有一个children数组，用来记录当前位置字符对应的子节点，以及一个isEnd标志位，用来记录当前节点是否是字符串结束位置。每次存放字符串时，遍历字符串每一字符，从树根开始，检查children中是否含有当前字符对应的子节点，如果有，则进入子节点继续检索下一字符，如果没有，则新建一个当前字符对应的节点，并放入children数组中，然后再进入子节点继续检索，直到遍历完字符串。在检索时，过程与上面类似，不同点在于，如果找不到当前字符对应的子节点，就直接返回空，否则不断向下检索，最后返回检索结束位置的节点。对于整串检索，如果检索结果为空，直接失败，否则还需要检查返回节点的isEnd标志是否为真，结果为是，才算检索成功（因为前面在存放的时候，在字符串结束位置会把isEnd标记置为1），否则检索失败；对于前缀检索，只要返回结果不为空，那么就检索成功（不需要匹配某个具体字符串）。
class Trie {
public:
/** Initialize your data structure here. */
Trie* children[26]{};
bool isEnd = false;
Trie() {
}
Trie* searchPrefix(string& prefix) {
Trie* cur = this;
for (auto& ch: prefix) {
ch -= 'a';
if (cur) cur = cur->children[ch];
else break;
}
return cur;
}
/** Inserts a word into the trie. */
void insert(string word) {
Trie* cur = this, * node;
for (auto& ch: word) {
ch -= 'a';
if (!cur->children[ch]) {
node = new Trie();
cur->children[ch] = node;
}
cur = cur->children[ch];
}
cur->isEnd = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Trie* res = searchPrefix(word);
return res && res->isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return searchPrefix(prefix);
}
};
LCR 063. 单词替换
Note: 字典树模板题，但是这里sentence可以不用分割，匹配再组合，而是可以在sentence上原地匹配，首先用word中所有的词根建立字典树，然后对于sentence中每一个单词，从首字符和根节点开始匹配，匹配则进入对应子节点，并将当前字符放入答案，直到某个词根匹配完成（isEnd为true），跳出匹配过程，此时匹配完成的词根一定是最短的；如果某个位置字符匹配不上，直接跳出当前单词匹配过程。然后判断当前单词是否匹配完成了某个词根，如果匹配上，一定是最短的，因此我们忽略剩余字符，进入下一个单词；否则，当前单词未匹配任何词根，不是继承词，由于前面的字符已经顺序放入答案，因此我们将剩余字符放入答案即可。（注意每个单词间的空格也要放入答案）。
struct Trie {
Trie* children[26]{};
bool isEnd = false;
} ;
class Solution {
public:
string replaceWords(vector<string>& dictionary, string sentence) {
Trie* root = new Trie(), * cur;
// 建立字典树
for (auto& word: dictionary) {
cur = root;
for (auto& ch: word) {
ch -= 'a';
if (!cur->children[ch]) cur->children[ch] = new Trie();
cur = cur->children[ch];
}
cur->isEnd = true;
}
// 按照sentence匹配字典树
int n = sentence.size(), i = 0, temp;
string ans;
while (i < n) {
cur = root;
while (i < n && sentence[i] != ' ') {
temp = sentence[i] - 'a';
// 当前字符匹配匹配则进入对应子节点，同时将字符放入答案
if (cur->children[temp]) {
cur = cur->children[temp];
ans.push_back(sentence[i++]);
// 直到某个词根匹配完毕，跳出当前单词匹配过程
if (cur->isEnd) break;
}
// 当前字符不匹配则直接跳出当前单词匹配过程
else break;
}
// 当前单词匹配完某个词根（一定是最短的），那就忽略该单词剩余字符
if (cur->isEnd) {
while (i < n && sentence[i] != ' ') ++i;
// 否则当前单词未匹配完任何词根，不是继承词，需要将剩余字符放入答案中
} else {
while (i < n && sentence[i] != ' ') ans.push_back(sentence[i++]);
}
// 放入空格
if (i < n) ans.push_back(sentence[i++]);
}
return ans;
}
};
LCR 064. 实现一个魔法字典
Note: 又一个SB题，数据规模太小，暴力比标准解法快。暴力解法：直接按字符串长度来分类dictionary，查找时只检查长度等于searchWord的字符串，检查其是否满足与searchWord正好有一个字符的距离。找到了直接返回true，没找到则最后返回false；标准解法：使用字典树+递归，用dictionary建立字典树，查找时，如果遇到不匹配字符（对应子节点为空），就找当前节点的其他非空子节点来进入下层递归（同时置修改标志位真），在深度等于searchWord长度时停止，检查结束位置节点是否isEnd，以及当前修改标志是否为真，是则找到目标，否则没有，然后进行回溯。
注意，在这个过程中，如果未找到目标（即子节点回报false），不立即返回，如果找到目标（子节点回报true），就需要立即返回，因此在遇到匹配字符时，不一定立即返回子节点查找结果，只有子节点回报true时才立即返回，否则需要选择其他非空子节点再进入下层递归，直到子节点遍历完或者收到true回报：
bool search(string searchWord) {
int n = searchWord.size();
function<bool(Trie*, int, bool)> dfs = [&](Trie* root, int pos, bool isModified) {
if (pos == n) return root->isEnd && isModified;
int temp = searchWord[pos] - 'a';
// 返回结果为假，不一定要立即返回，寻找别的可能性，但是返回结果真可以立即返回
if (root->children[temp]) {
if (dfs(root->children[temp], pos + 1, isModified)) return true;
}
if (!isModified) {
for (auto& child: root->children) {
if (!child || child == root->children[temp]) continue;
if (dfs(child, pos + 1, true)) return true;
}
}
return false;
};
return dfs(root, 0, false);
}
LCR 065. 单词的压缩编码
Note: 本题本质上是求所有不作为其他单词的后缀的单词的连接总长，因为如果两个单词互相没有后缀关系，其必然在压缩编码的不同段当中（逆否命题，如果两个单词在压缩编码同一段，一个必然是另一个的后缀，这是显然成立的）。有两种方法，一种是枚举全部后缀，由于数据规模不大，因此枚举是可行的，对于字典中每一个单词的全部后缀，判断其是否在字典中，在则删去，相比于储存所有后缀，然后拿单词一一匹配的正向操作，反向的删除操作更节省空间（虽然时间复杂度基本一致）。
class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
// 方法一：枚举所有后缀（每个字符串长度都很短），然后检查单词表里是否有其他单词后缀
// 相比于先枚举完毕，再比较，不如在枚举过程中删除单词表里所有作为其他单词后缀的单词
// 具体来说就是从单词表中删除每个枚举的后缀
unordered_set<string> suffix(words.begin(), words.end());
int size;
// 枚举每个单词的所有后缀
for (auto& word: words) {
size = word.size();
for (int i = 1; i < size; ++i) {
// 从单词表中删去后缀（如果有）
suffix.erase(word.substr(i));
}
}
int ans = 0;
for (auto& word: suffix) {
ans += word.size() + 1;
}
return ans;
}
};
第二种方法则是使用字典树，逆序储存所有单词，官解使用了先储存后判断的方法，我认为这种方法可以优化，于是有如下边储存边判断的方法：
struct Trie {
Trie* children[26] {};
short index = -1;
};
class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
// 方法二：后缀树
Trie* root = new Trie(), * cur;
// isSuffix标志用来判断某个单词是否是一个后缀
int n = words.size(), size, temp, ans = 0; bool isSuffix;
for (int i = 0; i < n; ++i) {
string &word = words[i]; isSuffix = true;
size = word.size(); cur = root;
// 逆序储存单词
for (int j = size - 1; j >= 0; --j) {
temp = word[j] - 'a';
if (!cur->children[temp]) {
cur->children[temp] = new Trie();
// 一旦创建了新节点，说明到目前为止不是后缀
isSuffix = false;
}
// 走到了某个之前单词的终止位置，那么之前那个单词就是后缀了
// 需要从答案中减去其长度并重置终止标记
if (cur->index != -1) {
ans -= words[cur->index].size() + 1;
cur->index = -1;
}
cur = cur->children[temp];
}
// 到目前为止不是后缀，长度加入答案，并且在终止位置标记单词索引
if (!isSuffix) {
ans += word.size() + 1;
cur->index = i;
}
}
return ans;
}
};
这里的主要做法是，使用一个标志位isSuffix来记录当前单词到目前为止是否是后缀，也就是，是否是前面单词的后缀，在插入字典树过程中，一旦新建了节点，那么当前单词到目前为止肯定不是后缀，因为它没有完全走以前单词的路。如果在插入完毕时，我们发现当前单词不是后缀，那么就将其长度加到答案中。
那可能有人会疑惑，到目前为止不是后缀，不代表不会是哪个之后的单词的后缀啊，别急，我们在这里将原理字典树节点的isEnd标志位换成了一个索引标志index，其基本作用和isEnd相同，都是标记单词结束位置，但还有一个额外作用就是，记录这个单词的索引，为什么要记录呢？就是为了在之后检查到其是后缀时，可以从答案中减去这个单词的长度。
如何检查？其实也很简单，在插入新单词过程中，检查当前位置是否是之前某个单词的终止位置（索引标志不为默认值），如果是，那么之前这个单词很明显就是后缀了，并且我们可以获取其在字典中的索引，直接从答案减去这个单词的长度即可，同时别忘了将标志重置为默认值。
LCR 066. 键值映射
Note: 本题有点类似前缀和，对于插入的键值对，对字典树上键单词对应的每一个节点都加上值，不过要注意的是，需要一个额外map来记录插入过的键值对，因为存在键重复的输入，此时应该做的是更换键单词对应的每一个节点的值，可以表现为加上新值 - 旧值。检索时，返回前缀结束位置节点的和即可。
int delta = val;
if (cnt.count(key)) delta -= cnt[key];
cnt[key] = val;
LCR 067. 数组中两个数的最大异或值
Note: 本题也可以用字典树解，原因是每个数字可以视为一个长度为31的字符串，每个位置只能为0或1，对于每一个新增的数字，检查其与前面数字是否可以异或产生最大值，具体表现为检查对于当前数字的每一位，字典树中对应位置是否能找到相反值子节点（比如0和1，1和0），如果能那么结果的对应位置为1（结果*2 + 1），否则结果对应位置为0（结果*2），然后移动到相应子节点，直到当前数字每一位遍历完成，也就确定了当前数字最大可能异或结果的每一位。由于字典树中保存了前面的所有数字，因此一轮遍历下来，也就相当于把所有可能的数字对都检查了一遍，时间复杂度可以达到O(nlogk)，k为最大的数值。这里可以使用压缩字典树，相比于标准字典树，更省空间，使用二维数组存储，第一维是树中最大节点个数，一般是插入元素个数 * 插入元素平均长度，第二维则是每个节点子节点个数（本题中为2）。
class Solution {
public:
// 压缩字典树
int tree[1000000][2]{};
int idx = 0;
static constexpr int HIGH_BIT = 30;
void add(const int& num) {
int x, cur = 0;
for (int i = HIGH_BIT; i >= 0; --i) {
x = (num >> i) & 1;
if (!tree[cur][x]) tree[cur][x] = ++idx;
cur = tree[cur][x];
}
}
int check(const int& num) {
int x, cur = 0, ans = 0;
for (int i = HIGH_BIT; i >= 0; --i) {
x = (num >> i) & 1;
if (tree[cur][!x]) {
ans = (ans << 1) + 1;
cur = tree[cur][!x];
} else {
ans <<= 1;
cur = tree[cur][x];
}
}
return ans;
}
int findMaximumXOR(vector<int>& nums) {
int n = nums.size(), ans = 0;
for (int i = 1; i < n; ++i) {
add(nums[i - 1]);
ans = max(ans, check(nums[i]));
}
return ans;
}
};
LCR 070. 有序数组中的单一元素
Note: 二分主要看mid奇偶性，如果mid为偶数，假设左侧没有目标数，那么明显mid是两连续数的第一个，也就是nums[mid] = nums[mid + 1]，此时left = mid + 2，否则，mid要么是两连续数的第二个，要么是目标数，因此right = mid；如果mid为奇数，假设左侧没有目标数，那么mid就是两连续数的第二个，也就是nums[mid] = nums[mid - 1]，此时left = mid + 1，否则mid只能是两连续数的第一个（目标数索引一定是偶数），且目标数在左侧，此时right = mid - 1。
考虑到mid ^ 1在mid为奇时等于mid - 1，而在mid为偶时等于mid + 1，因此合并上述情况（当然不合并其实更好），在nums[mid] = nums[mid ^ 1]时，left = mid + 1（左边界取小），否则right = mid（右边界取大）。注意当范围被缩小到只剩一个数时，我们就找到结果，因此while的结束条件是l < r.
LCR 071. 按权重随机选择
Note: 这里可以使用类似哈希环的思想来解，对于数组中每一个数，按照其数值放等量的占位符（用对应的原数组索引占位）到一个模拟数组中，当然考虑到空间，这里不可能真的用一个数组来放，比如对于原数组[1, 2, 3, 4]，这个模拟数组就是[0, 1, 1, 2, 2, 2, 3, 3, 3, 3]，如果这个模拟数组以1作为起始索引，那么我们可以发现，i的连续段的结束位置就是前缀和pre[i]（比如原数组索引2连续段的结束位置是pre[2] = 6），而其开始位置是pre[i - 1] + 1。那么我们可以从上述的模拟数组中随机选取一个索引，该索引对应位置的这个原数组索引就是我们要找的权重随机索引。
如何随机呢？可以使用rand，也可以使用mt19937和uniform_int_distribution的组合。获取到随机索引x后，对于满足题意的原数组索引i，x必然在pre[i]的连续段上，因此pre[i - 1] < x ≤ pre[i]，又因为pre是升序数组，那么我们可以使用二分查找在pre数组中查找满足x ≤ pre[i]的最小的原数组索引i，也就是所求的随机索引。
LCR 072. x 的平方根
Note: 关于二分模版I的一点思考：
while (l <= r) {
mid = l + (r - l) / 2;
if (cond(mid)) l = mid + 1;
else r = mid - 1;
}
如上是非等量二分的模版，非等量意味着我们是在找满足/不满足cond(i)的边界索引i，而不是在搜索某个具体的值target（如果我们是在搜索具体值，需要加上等量返回的语句（找到了就返回），或者像LCR 070. 有序数组中的单一元素一样，是在逐步减小范围直到左右范围相等）。那么此时找到的最终找到的l值是不满足cond(i)的索引i的最小值，而找到的r是满足cond(i)的索引i的最大值，注意这里cond的选取也有讲究，对于升序（非降序）数组，索引i从小到大应该是从满足cond到不满足cond的过程，因此cond需要是个类似nums[mid] <= target的lt条件；对于降序（非升序数组），索引i从小到大也是满足cond到不满足cond的过程，因此cond需要是gt条件（nums[mid] >= target）。
如果是这样写（模版II）：
while (l <= r) {
mid = l + (r - l) / 2;
if (cond(mid)) r = mid - 1;
else l = mid + 1;
}
那么cond对于升序数组应该为gt条件（索引从左到右是不满足到满足），对于降序数组应该为lt条件（索引从左到右也是不满足到满足），由于在满足cond时是到左边找（r变小），不满足时是到右边找（l变大），因此最终l应该是满足cond的最小索引，而r是不满足cond的最大索引。
LCR 073. 爱吃香蕉的狒狒
Note: 经典的二分题，在吃的速度小的时候，吃完所有香蕉所花的时间会比较大，而我们需要找到某个速度，在这个速度及以上可以吃完所有香蕉，但在这个速度一下就无法在H小时内吃完所有香蕉。这个速度应该尽量小，因此总计用时应该尽量大，但不能> H。
假设当前吃的速度speed，则对于任意一堆香蕉pile，吃完的时间是ceil(pile / speed)，也就是(pile + speed - 1) / speed，对所有堆计算时间总和，就得到在当前速度speed下吃完所有香蕉的总用时time，我们需要让这个用时尽量大，可以对可能的速度范围进行二分搜索，来确定使得总计用时time ≤ H的最大用时/最小速度。
由于如果速度取最大堆香蕉数量，一定可以在H小时内吃完全部香蕉（再增大没有意义），因此我们将这一速度设为速度右边界，左边界取1，然后使用二分来确定使得总计用时time ≤ H的最小速度，等价于确定speed ≥ s（s是某个未知速度）的最小值。根据前面的二分模版II，speed是升序数组，要求满足speed ≥ s（s是某个未知速度）的最小值，cond取等价条件也就是time ≤ H，最终二分查找如下：
int left = 1, right = maxTime, speed, time;
while (left <= right) {
speed = left + (right - left) / 2;
time = getTime(piles, speed);
if (time <= h) {
right = speed - 1;
} else {
left = speed + 1;
}
}
return left;
再总结一下，选择哪个二分模版（I还是II）主要看数组顺序和所求条件，如果是同方向（升序和lt条件，降序和gt条件），就使用模版I；否则使用模版II。如果要求最小值，那么就返回l，否则返回r。
实际上只有四种情况：
- 升序数组，求
lt条件的最大索引：模版I + 返回r - 升序数组，求
gt条件的最小索引：模版II + 返回l - 降序数组，求
lt条件的最小索引：模版II + 返回l - 降序数组，求
gt条件的最大索引：模版I + 返回r
LCR 077. 排序链表
Note: 如果要求时间复杂度O(nlogn)，那么只能使用归并排序（快排实际时间不稳定）。有两种方法：
- 自顶向下的分治归并
使用分治思想，用快慢指针找中点法将链表逐步分解为多个长度为1的短链表，然后两两有序合并，最终形成整体的有序链表，空间复杂度为递归深度O(logn)。
class Solution {
public:
ListNode* mergeList(ListNode* head1, ListNode* head2) {
ListNode* dummy;
// 不使用新建的dummy节点主要是减少new和delete开销
if (head1->val <= head2->val) {
dummy = head1; head1 = head1->next;
} else {
dummy = head2; head2 = head2->next;
}
ListNode* cur = dummy;
while (head1 && head2) {
if (head1->val <= head2->val) {
cur->next = head1;
head1 = head1->next;
}
else {
cur->next = head2;
head2 = head2->next;
}
cur = cur->next;
}
cur->next = head1 ? head1 : head2;
return dummy;
}
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* slow = head, * fast = head;
// 快慢指针找中点
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = nullptr;
head = sortList(head);
fast = sortList(fast);
return mergeList(head, fast);
}
};
- 自底向上二路归并
使用迭代的归并排序，不使用分治，而是从长度为1的短链表开始，两两有序合并，然后逐步倍增（1 -> 2 -> 4）短链表长度，直到长度大于链表总长度，即为排序完成。一趟的时间是O(n)，总共需要logn趟，因此时间复杂度是O(nlogn)，而空间复杂度是O(1)（不需要递归）。链表归并排序和数组不一样，数组是必须使用额外O(n)的辅助空间，主要原因就是在于链表在物理空间上不是连续的，而数组是，直接原地合并会导致覆盖，链表的原地合并则只需要修改next指向。这里的二路归并方法不将短链表断开（断开再接回有点浪费时间），所以在mergeList函数中传入了三个参数：前置节点prev（用作合并时的dummy），第二段链表起点mid（同时作为第一段链表的结束位置），第二段链表结束位置tail，这里的mid和tail对于待合并的两段链表相当于空节点，是其结束标志。要注意的是，不同于两个以null结束的链表合并，在两段链表的指针有一个为空的时候（head1 == mid或者head2 == tail），需要继续遍历不为空的那个链表（不可以将其直接接在末尾！），原因是需要找到合并后的最后一个节点，改变其next指向到tail，否则会出现指向问题。注意三个指示指针prevmid和tail在寻找过程中如果为空则停止。
class Solution {
public:
// 二路归并版合并链表（不断开，故返回空）
void mergeList(ListNode* &prev, ListNode* &mid, ListNode* &tail) {
ListNode* cur = prev;
ListNode* head1{prev->next}, * head2{mid};
while (head1 != mid && head2 != tail) {
if (head1->val <= head2->val) {
cur->next = head1;
head1 = head1->next;
} else {
cur->next = head2;
head2 = head2->next;
}
cur = cur->next;
}
while (head1 != mid) {
cur->next = head1;
head1 = head1->next;
cur = cur->next;
}
while (head2 != tail) {
cur->next = head2;
head2 = head2->next;
cur = cur->next;
}
cur->next = tail;
}
ListNode* sortList(ListNode* head) {
// 二路归并排序（迭代）
ListNode* dummy = new ListNode(-1, head);
int subLen = 1, n = 0, subLen_2;
ListNode* cur = head;
while (cur) {++n; cur = cur->next;}
ListNode* prev, * mid, * tail;
// 短链表长度倍增
while (subLen < n) {
prev = dummy;
while (prev) {
mid = prev->next;
// 找出mid
for (int i = 0; i < subLen && mid; ++i) mid = mid->next;
tail = mid;
// 找出tail
for (int i = 0; i < subLen && tail; ++i) tail = tail->next;
// 原地合并
mergeList(prev, mid, tail);
subLen_2 = subLen << 1;
// 找下一个prev
for (int i = 0; i < subLen_2 && prev; ++i) prev = prev->next;
}
subLen <<= 1;
}
return dummy->next;
}
};
LCR 078. 合并 K 个升序链表
Note: 递归（O(logk)空间）或者优先队列（O(k)空间），时间均为O(nklogk)。
LCR 080. 组合
Note: 限定个数的组合问题别忘记剪枝。（剩余可遍历数字个数一定要≥答案待填充数字个数）：
// 别忘了剪枝，设i最大可为p，那么n - p + 1 >= k - path.size()
// 因此p <= n + 1 - (k - path.size())
int upper = n + 1 - (k - path.size());
for (int i = startIdx; i <= upper; ++i) {
path.emplace_back(i);
dfs(i + 1);
path.pop_back();
}
LCR 081. 组合总和
Note: 由于都是正整数且限制了最大总和，同时数据量很小，因此可以先排序然后剪枝。（遇到超限的元素直接break）这里由于可以多次选择同一数字，因此递归进入i而非i + 1。
LCR 082. 组合总和 II
Note: 注意排序去重（这里排序是必要的）。递归下一层进入i + 1。
LCR 083. 全排列
Note: 基于选择/基于交换选一种，后者理论上更优（不需要额外的used数组来记录上层访问过的位置 (注意是下标！)）。
LCR 084. 全排列 II
Note: 如果基于选择，不能像有重复元素的组合一样直接排序去重，而应该加上一个条件!used[i - 1]。如果used[i]，这个索引已被上层使用，本层不能再用；而如果i > 0 && nums[i] == nums[i - 1] && !used[i - 1]（注意多出的条件），那么i - 1一定未被上层使用，那由于索引从大到小，其一定在本层被使用过，因此也不能再使用。上述两个条件加在一起去重；
如果基于交换，不可以排序去重，因为交换会打乱原有顺序，在遍历到索引i时，判断本层开始位置startIdx到i之间是否有和i处数字相等的索引k，如果有，很明显，i应该被跳过（因为对nums[i]和nums[startIdx]的交换已经做过一次，再交换就是重复了）。
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> permuteUnique(vector<int>& nums) {
int n = nums.size();
// 检查位置i是否合法
function<bool(int&, int&)> isValid = [&nums](int& start, int& cur) {
for (int i = start; i < cur; ++i) {
if (nums[i] == nums[cur]) return false;
}
return true;
};
function<void(int)> backtrace = [&](int startIdx) {
if (n == path.size()) {
ans.emplace_back(path);
return;
}
for (int i = startIdx; i < n; ++i) {
if (!isValid(startIdx, i)) continue;
path.emplace_back(nums[i]);
swap(nums[startIdx], nums[i]);
backtrace(startIdx + 1);
swap(nums[startIdx], nums[i]);
path.pop_back();
}
};
backtrace(0);
return ans;
}
};
LCR 086. 分割回文串
Note: 奇怪的是这题如果先计算好isPalindrome就会很慢（笑）。猜想可能原因是，如果提前计算好，会有大量冗余。
LCR 087. 复原 IP 地址
Note: 主要是注意判断子串是否合法，即是否有前导0，不合法字符，或者越界（值大于255）。
bool isValid(string& s, int start, int end) {
// 前导0
if (s[start] == '0' && start != end) return false;
int num = 0;
for (int i = start; i <= end; ++i) {
// 非法符号
if (s[i] > '9' || s[i] < '0') return false;
num = num * 10 + s[i] - '0';
// 越界
if (num > 255) return false;
}
return true;
}
LCR 092. 将字符串翻转到单调递增
Note: 因为本题字符串每个位置只有0和1两种情况，因此可以考虑使用二维dp，第二维长度为2，其中dp[i][0]代表s[0:i]在以0结尾时的最小翻转次数，dp[i][1]则代表s[0:i]在以1结尾时的最小翻转次数。
其递推公式不难想，如果s[0:i]要是以0结尾，那么其要变为递增字符串，则s[0:i - 1]必须以0结尾，如果s[i]为1还要额外翻转一次，因此dp[i][0] = dp[i - 1][0] + (s[i] == 1)；但若s[0:i]以1结尾，那么无论s[0:i-1]以0还是1结尾都无所谓，因此取最小值，然后在原本s[i]为0的情况下还要额外翻转一次，因此dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] == 0)。最后取dp[n - 1][0]和dp[n - 1][1]的最小值即可。
这是一道很不错的多状态dp题，也启示我们在仅用一维dp无法解决问题时，去尝试多状态的二维dp，尤其是当数组或者字符串元素表现出明显的状态时，比如上题的三种颜色，本题的0和1。
LCR 093. 最长的斐波那契子序列的长度
Note: 假设某斐波那契最长的子序列的结尾三个序列位置分别是j k i（顺序从小到大），那么必然有arr[j] + arr[k] == arr[i]，而且这个子序列一定是由arr[i]和arr[k]唯一确定了（也就等价于由索引i和k唯一确定），就像由斐波那契数列最初两项可以递推出整个数列一样，斐波那契子序列的最后两项也可以倒推出整个序列。那么我们假设由索引i和k唯一确定的斐波那契子序列长度为dp[i][k]，找到满足arr[j] + arr[k] == arr[i]的j（j < k < i），可以得出由i和k确定的斐波那契子序列长度应该为k和j确定的斐波那契子序列长度+1，因为此时j k和i都在同一斐波那契子序列上。
但是这里有一个小问题，如果k和j还未确定子序列，此时dp[k][j]为0，也就是说，这两个数刚好是子序列中最小的两个数，怎么办？那么dp[i][k]应该直接取3，综上dp[i][k] = max(dp[k][j] + 1, 3)，或者写成dp[i][k] = dp[k][j] ? dp[k][j] + 1 : 3。那么对于一个确定的i，如何寻找满足要求的j和k呢，考虑到原数组是有序的，我们可以使用双指针来在arr[0:i - 1]段上寻找满足arr[j] + arr[k] == arr[i]的j和k（类似于三数之和，同样也可以加入剪枝），然后记录最大的dp[i][k]即可。
最后一个问题，为什么不在递推公式里做类似dp[i][k] = max(dp[i][k], ...)的操作，因为这里每一个不同i和k组合最多访问一次。不妨假设我们找到了满足要求的三个索引j k i，如果我想继续找下一组满足要求的j k i，我的j和k指针必须同时向中间移动（只有这样才能让和不变，只右移j会导致和变大，只左移k会导致和变小），因此在一个给定的i下，一个k值最多访问一次，所以在整个递推过程中，不可能出现i和k都相等的组合，也就是说，每一个不同的i和k组合最多被访问一次，那么dp[i][k]是不可能被覆盖的。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(n));
int i, j, k, temp, ans = INT_MIN;
for (i = 2; i < n; ++i) {
if (arr[0] + arr[1] > arr[i]) continue;
if (arr[i - 2] + arr[i - 1] < arr[i]) continue;
j = 0; k = i - 1;
while (j < k) {
temp = arr[j] + arr[k];
if (temp == arr[i]) {
dp[i][k] = dp[k][j] ? dp[k][j] + 1 : 3;
ans = max(dp[i][k], ans);
++j; --k;
} else if (temp < arr[i]) ++j;
else --k;
}
}
return ans == INT_MIN ? 0 : ans;
}
};
LCR 094. 分割回文串 II
Note: 本题除了常规解法（先算好isPalindrome，然后再递推dp），还可以在算isPalindrome的过程中直接去求dp（实际上isPalindrome都不需要求了）。这里为了统一各种情况，设置dp[i]表示以s[i - 1]结尾的子串，即s[0:i - 1]可分割成的最小子段个数（最小分割次数也就=这个值-1），就不需要单独处理最小分割次数为0的情况（见后面详解）。
以中心扩散为例，在对s[l:r]判别成功（是回文串）后，s[0:r]可分割成的最小子段个数可以为s[0:l-1]可分割成的最小子段个数+1，也就是dp[r + 1] = min(dp[r + 1], dp[l] + 1)（在指针中间靠拢之后，也就是--l和++r之后，这个方程变为dp[r] = min(dp[r], dp[l + 1] + 1)，这可以减少一次计算）。在中心扩散过程中不断执行这个方程，最终便可以计算所有的dp[i]。由于这里的dp数组需要有n + 1个位置，因此要初始化dp[0]，从意义上说，s[0:-1]能分割出的最小子段个数当然为0，因此dp[0] = 0。而其他dp[i]统一设为INT_MAX。
这里与方法一主要不同的一点是，dp在中心扩散的过程中计算，并且不需要对s[0:i]为回文串的情况特殊考虑，因为方法一中的dp[i]表示的是s[0:i]的最小分割次数，一旦s[0:i]为回文串，那么dp[i] = 0，无法使用dp[i] = min(dp[i], dp[j] + 1)（s[j + 1:i]为回文串）来计算。
class Solution {
public:
int minCut(string s) {
int n = s.size();
int * dp = new int[n + 1];
memset(dp, 1, sizeof(int) * (n + 1));
dp[0] = 0;
function<void(int, int)> centerDiffuse = [&](int l, int r) {
while (l >= 0 && r < n) {
if (s[l] != s[r]) return;
--l; ++r;
dp[r] = min(dp[r], dp[l + 1] + 1);
}
};
for (int i = 0; i < n; ++i) {
centerDiffuse(i, i);
centerDiffuse(i, i + 1);
}
return dp[n] - 1;
}
};
LCR 095. 最长公共子序列
Note: 记录一下双变量空间压缩方法，防止忘记（不是）：
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size(), temp, prev;
vector<int> dp(n + 1);
for (int i = 1; i <= m; ++i) {
prev = 0;
for (int j = 1; j <= n; ++j) {
// 1. 在每次计算本层dp[j]之前保存上一层dp[j], 也就是dp[i - 1][j]
temp = dp[j];
// 3. 在下一个dp[j]计算时，prev实际就是dp[i - 1][j - 1]
if (text1[i - 1] == text2[j - 1]) dp[j] = prev + 1;
else dp[j] = max(dp[j], dp[j - 1]);
// 2. 保存dp[i - 1][j]到下一个j
prev = temp;
}
}
return dp[n];
}
};
LCR 096. 交错字符串
Note: 本题可以使用双指针的思想，两个指针在s1和s2上不断移动去寻找和s3匹配的位置，匹配则前进，不匹配则切换指针，但主要问题是s1和s2的当前字符相等时，不知道应该用哪个去匹配s3，那么就需要尝试，也就是使用回溯方法，如果s1[idx1]和s3[idx3]相等，就让s1[idx1 + 1]和s3[idx3 + 1]尝试去进行下一次匹配，如果s2[idx2]和s3[idx3]相等，就让s2[idx2 + 1]和s3[idx3 + 1]尝试去进行下一次匹配，也就是每一层有两个选择：让s1前进或者让s2前进，直到匹配完成为止（三个索引同时到达末尾）。
但是这里有重复的问题，因为s1和s3前进1，接着s2和s3前进1和s2和s3前进1，接着s1和s3前进1是一样的，但在回溯中，这两个操作会重复出现，因为每次向下一层是s3前进1，每层两个选择，那么回溯树中最多有2m+n个节点（m和n分别为s1和s2长度，这里s3长度必须为这两者和，否则肯定是无法找到匹配的），也就是时间复杂度最坏为O(2m+n)，必定超时，主要原因是其中大量的重复计算，如何减少呢？用一个二维数组visited来记录某个下标组合(idx1, idx2)是否访问过，如访问过，由于此时idx3 = idx1 + idx2，idx3也肯定是访问过的，这条路径我们已经计算过，不需要再访问了，这样的话，时间复杂度也就减少为该组合的数量，也就是O(m * n)。这里的递归函数返回类型为bool，因为我们只需要找到一条满足条件的路径，找到直接返回true，没找到则继续另一分支，还没找到则返回false。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// 双指针回溯，记忆化搜索！
bool visited[101][101]{};
int m = s1.size(), n = s2.size(), o = s3.size();
function<bool(int, int, int)> backtrace = [&](int idx1, int idx2, int idx3) {
if (visited[idx1][idx2]) return false;
if (idx1 == m && idx2 == n && idx3 == o) return true;
visited[idx1][idx2] = true;
if (idx1 < m && idx3 < o && s1[idx1] == s3[idx3]) {
if (backtrace(idx1 + 1, idx2, idx3 + 1)) return true;
}
if (idx2 < n && idx3 < o && s2[idx2] == s3[idx3]) {
if (backtrace(idx1, idx2 + 1, idx3 + 1)) return true;
}
return false;
};
return backtrace(0, 0, 0);
};
实际上我们要解决的就是s3的某一位置是由s1来匹配还是s2来匹配的问题，那么就可以用动态规划，设dp[i][j]表示的是s1[0:i - 1]和s2[0:j - 1]是否能交错匹配形成s3[0:i + j - 1]（布尔类型），那么如果s1[i - 1] == s3[i + j - 1]，那么s1[0:i - 1]和s2[0:j - 1]是否能交错匹配形成s3[0:i + j - 1]就取决于s1[0:i - 2]和s2[0:j - 1]是否能交错形成s3[0:i + j - 2]，也就是dp[i][j] = dp[i - 1][j]，而如果s2[j- 1] == s3[i + j - 1]，那么dp[i][j] = dp[i][j - 1]，上述两个只要有一个为真，dp[i][j]就为真，都为假则dp[i][j]为假（类似于上面的回溯），因此dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i][j]) | (s2[j - 1] == s3[i + j - 1] && dp[j - 1])。
这里注意一下i和j的范围以及dp的初始化，如果i为0，j大于0，代表s1为空串，问题变为s2[0:j - 1]与s3[0:j - 1]是否匹配，因此dp[i][j] = s2[j - 1] == s3[j - 1] && dp[j - 1])，可以统一到上式中；j为0，i大于0也同理。如果i j同时为0，代表此时待匹配s1 s2 s3均为空串，必定可匹配，因此dp[0][0] = true。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// 动态规划
int m = s1.size(), n = s2.size(), o = s3.size();
if (m + n != o) return false;
vector<bool> dp(n + 1);
dp[0] = true;
// 滚动数组优化后的写法
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
int p = i + j - 1;
if (i > 0) dp[j] = (s1[i - 1] == s3[p] && dp[j]);
if (j > 0) dp[j] = dp[j] || (s2[j - 1] == s3[p] && dp[j - 1]);
}
}
return dp[n];
}
};
这里时间复杂度也为O(m * n)，和回溯的方法是一样的，但是空间复杂度会更优一点，因为不需要递归。
LCR 097. 不同的子序列
Note: 编辑距离系列，这里注意只有s才可删除，而在s和t子串末尾匹配的时候，可以选择删s，也可以不删s，因为求的是可行的方法数量，必须统计所有的可能，这一点和编辑距离不一样，因为编辑距离求的是从s到t的最小步数，能少操作就少操作，那么在s和t子串末尾匹配的情况下，我们肯定是选择不删不增的，否则岂不是白多一次操作。