LCR 151. 彩灯装饰记录 III
Note: 使用双端队列，在奇数层，向前弹出取节点，使用后插插入子节点，先插左，后插右；在偶数层，向后弹出取节点，使用前插插入子节点，先插右，后插左。
LCR 152. 验证二叉搜索树的后序遍历序列
Note: 两种方法，第一种方法是首先确定根，然后找前面的左右子树分割点，然后再去验证其左右子树是否合法。这里找分割点不可以使用二分，因为是否合法是不知道的，只有确定合法才能用二分找左右子树分割点。因此必须遍历来找分割点，此时花掉时间O(n)，最差情况树退化为链表，需要对n个结点都去找左右子树分割点，时间复杂度O(n2)，空间复杂度O(n)。
class Solution {
public:
bool verify(vector<int>& postorder, int left, int right) {
if (left >= right) return true;
int &root = postorder[right];
int border = left;
while (postorder[border] < root) ++border;
int temp = border;
while (postorder[temp] > root) ++temp;
if (temp != right) return false;
return verify(postorder, left, border - 1) && verify(postorder, border, right - 1);
}
bool verifyTreeOrder(vector<int>& postorder) {
return verify(postorder, 0, postorder.size() - 1);
}
};
第二种方法使用范围查询，只去验证每个（根）节点是否符合范围，类似于 98. 验证二叉搜索树，如何确定根？使用一个全局变量index来记录当前根，初始指向后序序列最后一个位置，此后在每次递归到左右子树之前-1，而左右子树的递归顺序是先右后左，因为后序左右中的反向是中右左，根是从右至左的。在递归函数中，如果index < 0说明序列已经（倒序）遍历完成，直接返回，如果根节点值不在当前合法范围，也直接返回，注意这里的递归函数的返回值是void而不是bool，因为序列是没有空节点的，不像98. 验证二叉搜索树 这里有一颗完整的树，递归时是在往两端移动，并且可以在进入空节点时返回true，在这里我们实际上只是在往一端移动（左端）。最后判断index是否< 0 ，如果是那么说明树是合法的，在这个过程中，没有遇到不合法的情况，否则不合法。这个方法时间复杂度和空间复杂度都是O(n)，因为他只对每个节点检查了一次。
class Solution {
public:
int index;
void verify(vector<int>& postorder, int lower, int upper) {
if (index < 0) return;
int rootVal = postorder[index];
if (postorder[index] <= lower || postorder[index] >= upper) return;
--index;
verify(postorder, rootVal, upper);
verify(postorder, lower, rootVal);
}
bool verifyTreeOrder(vector<int>& postorder) {
index = postorder.size() - 1;
verify(postorder, INT_MIN, INT_MAX);
return index == -1;
}
};
第三种实际和上面一样但是十分抽象，使用单调栈，仍然是倒序遍历后序序列（中右左），遇到比栈顶大的直接入栈，相当于向右子树扩展，一旦遇到比栈顶小的，说明右子树结束了，就需要找到底是谁的左子树（不一定是栈顶节点的左子树），假设记为root，由于当前栈顶是最下层的根节点，因此不断出栈直到当前节点大于栈顶节点，那最后一个出栈的节点就恰好是当前节点的根节点。此后序列中所有节点一定是当前节点子节点，因此在下一次遍历时判断那时的当前节点是否小于root，如果大于是不合法的，因为那时的当前节点一定是此时当前节点的子节点，此时当前节点一定是小于root的，因此那时的当前节点也一定小于root。
这里的栈的目的其实是保留数据范围，类似于方法二中递归传递数据范围，可以想象，每一个从后序序列中取出的节点就是递归中遍历的当前节点，栈中元素从栈底到栈顶是升序的，栈顶元素是最大的，而栈中每两个元素之间都是一个范围（比如[1, 3]，[3, 5]，[5, 无穷)），我们要做的是找到当前节点应该插入的位置，如果能找到栈中的连续元素a和b，使得a < 当前节点值 < b，那么当前节点应该插入在b的左边 a的右边，并且b是当前节点父节点，这也对应 “不断出栈直到当前元素大于栈顶元素，取最后一个出栈元素为父节点”，此时栈顶元素就相当于a，最后一个出栈元素就相当于b；但如果当前元素直接就大于栈顶元素，那么就应该插入在栈顶元素右子节点。
为什么这里只在左插的时候更新root呢？因为右插的时候，当前元素节点是栈顶元素节点的右子节点，再下一个节点范围是(负无穷，正无穷)，无法用范围信息来判断是否合法。但在左插的时候，由于当前节点是root的左子节点，因为逆后序序列是中右左，此时root的右子树一定已经构建完成，则下一个节点如果大于root是不合法的，因为此时大于root的节点一定是root的后续元素，因此其不是在root右子树，就是在root的祖先节点的右子树上（这种情况下root是其父节点的左子树），但是很明显如果root是其祖先节点的左子树，那么其祖先节点的右子树一定构建完毕，下一个节点不可能出现在这些树上。综上只有这一情况是不合法的，或者说下一个节点的插入范围只能是(负无穷, root]。
class Solution {
public:
bool verifyTreeOrder(vector<int>& postorder) {
// 单调栈
stack<int> st;
int n = postorder.size(), root = INT_MAX;
for (int i = n - 1; i >= 0; --i) {
if (postorder[i] > root) return false;
while (!st.empty() && postorder[i] < st.top()) {
root = st.top();
st.pop();
}
st.emplace(postorder[i]);
}
return true;
}
};
扩展： 与本题类似的另一题：1008. 前序遍历构造二叉搜索树，该题也可使用递归和单调栈方法，递归时，与本题方向相反，index从0开始，不断+1，另一个不同是递归函数的返回值，由于要构建树因此需要返回TreeNode*，这里的逻辑和本题是如出一辙的，index越界，则树已经构建完成，返回空节点；index对应节点不在当前范围内时，不可在当前子树构建节点，也返回空节点。然后建立根节点，再依次递归到左右子节点并缩小范围。
class Solution {
public:
int index = 0;
int n;
TreeNode* buildTree(vector<int>& preorder, int upper, int lower) {
// 越界说明遍历完成，返回空
if (index == n) return nullptr;
int rootVal = preorder[index];
// 范围不合法则不可构建子树，返回空
if (rootVal > upper || rootVal < lower) return nullptr;
// 构建子树
TreeNode* root = new TreeNode(rootVal);
++index;
// 依次进入左右子树递归
root->left = buildTree(preorder, rootVal, lower);
root->right = buildTree(preorder, upper, rootVal);
return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
n = preorder.size();
return buildTree(preorder, INT_MAX, INT_MIN);
}
};
另一种还是使用单调栈，单调栈的用法和上一题一致（不过方向相反），而且由于已经确认序列合法，要做的只是找出每个当前节点的父节点，然后根据大小关系来安插节点位置。
class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
// 单调栈做法
int n = preorder.size();
stack<TreeNode*> st; TreeNode* root = new TreeNode(preorder[0]);
st.emplace(root);
for (int i = 1; i < n; ++i) {
TreeNode* cur = new TreeNode(preorder[i]), * father = st.top();
while (!st.empty() && cur->val > st.top()->val) {
father = st.top(); st.pop();
}
if (cur->val < father->val) father->left = cur;
else father->right = cur;
st.emplace(cur);
}
return root;
}
};
LCR 154. 复杂链表的复制
Node: 使用哈希表，选择两遍遍历或者递归，两遍遍历时，先一遍遍历复制全部节点，第二遍遍进行指针指向的更改，或者修改为一遍遍历，每次遍历将当前节点复制与next和random的复制一起做了；递归方法从头结点开始，与一遍递归做法相同。
LCR 157. 套餐内商品的排列顺序
Note: 全排列，基于穷举或者交换都可以，基于穷举的话需要排序以及used数组（本题可以用一个int数来代替used，因为数字位数有限，只有8位），基于交换的话则不需要，判重要用额外的函数。
LCR 158. 库存管理 II
Note: 如果要求O(1)空间，那么就使用一个times来记录当前目标数的出现次数，遇到一样的数就+1，遇到不同的数就-1，次数变为0就要换目标数。由于一定存在题目要求的出现次数超过一半的数，因此这个数出现次数一定比其他数数量加起来还要大至少1，最后的目标数一定是要求的数。
LCR 159. 库存管理 III
Note: 找topk元素主要用优先队列或者快排思想。优先队列需要O(nlogk)的时间，n为数组元素个数，k为要求的topk数的个数，因为最坏情况下数组所有的元素都被插入优先队列，优先队列最长长度k，每次插入删除时间是O(logk)。使用快排思想，则复杂度为O(n)，但是这里的复杂度取决于pivot的选取，为了尽量降低实现难度以及复杂度，使用随机下标选取。
class Solution {
public:
void partition(vector<int>& stock, int left, int right, int k) {
// 防止越界
if (left >= right) return;
// 随机选取pivot
int pivotIdx = rand() % (right - left + 1) + left, pivot = stock[pivotIdx], l = left, r = right;
// pivot交换到最左
swap(stock[left], stock[pivotIdx]);
while (true) {
while (l <= r && stock[l] <= pivot) ++l;
while (l <= r && stock[r] > pivot) --r;
if (l >= r) break;
swap(stock[l], stock[r]);
}
// r此时指向左半部分右边界，该位置以及左边都是<=pivot，右边都>pivot，
// 也就是说，r是pivot元素的正确位置，因此交换r和left位置（原pivot元素）数
swap(stock[left], stock[r]);
// 这里的k是待查找下标，等于r的话，本次分割完成
// 如果小于r，那么到左半找，否则到右半找。
if (k < r) partition(stock, left, r - 1, k);
else if (k > r) partition(stock, r + 1, right, k);
else return;
}
vector<int> inventoryManagement(vector<int>& stock, int cnt) {
// 快排找
srand((unsigned int)NULL);
partition(stock, 0, stock.size() - 1, cnt - 1);
return {stock.begin(), stock.begin() + cnt};
}
};
这里l <= r的目的是确保l和r错开，故不能使用l < r。
LCR 160. 数据流中的中位数
Note: 分两个堆（优先队列），一个保留数组左半边（最大堆，堆顶元素是左半边的最大数），一个保留右半边（最小堆，堆顶元素是右半边的最小数），其中左半边比右半边多一个数（如果总数为奇数）或者正好对半分（总数为偶数），最后取中位数时，如果两半元素数量相等，就各取对顶元素然后计算和的一半，否则直接取左半边（最大堆）的堆顶元素。
在插入时，如果当前两半数量相等，那么我们应该将元素插入左半边（最大堆），但是这个元素实际并不一定在左半边，可能在右半边，因此需要先插入右半边，然后把右半边堆顶元素弹出，插入左半边，这样不管当前元素实际在左半边还是右半边，都插入了正确的位置（如果实际在左半边，那么其在插入右半边时就会成为堆顶；如果实际在右半边，那么右半边的堆顶（最小值）应该到左半边去，来维持左右数量关系不变）；两半数量不等的时候，则应该把当前元素插入到右半边，同样的道理，先插左半边，然后把左半边堆顶弹出，插入右半边。
LCR 162. 数字 1 的个数
Note: 本题考查数位dp，统计每个位上可能出现1的次数，假设当前位数字为cur（位置为i，从右往左，最低位为0），其左边数为high，右边数为low，原数被拆成三部分有三种情况：
- 假设
cur为0，那么要想让该位出现1，则左边数最多为high - 1，不能为high，否则该位最多为0。而右边数可以任取，最多有10i种搭配（0到10i - 1，因为第i位数右边有i个数字，每个数字有10种取法），记digit = 10i，则该位出现1的次数为high * digit。 - 假设
cur为1，那么要想让该位出现1，则左边数最多为high，但是但其为high时，右边数最多为low（不能再大了），当其为0 ~ high - 1时，右边数可以任选，同样是digit种取法，因此该位出现1的次数是high * digit + low + 1。 - 假设
cur大于1，那么该位取1时，左右数都可以任取，左边数可取0 ~ high，右边数有digit种取法，因此该位出现1的次数是(high + 1) * digit。
因此主要任务就变成，从最低位开始，不断获取原数的三部分high cur和low，首先初始化i为0，也就是digit为1，high为num / 10（第0位数的左边部分），cur为num % 10（第0位数），low则为0（第0位数右边部分）。然后进行一次三种情况的判断，之后更新上述变量，更新顺序很重要！应当按照从右到左的顺序更新，也就是先更新low为cur * digit + low（相当于把本次的cur添加到low的最高位），然后更新cur为high % 10（也就是本次high的最后一位），最后更新high为high / 10，也就是本次high除掉最后一位的部分。最后在更新digit为digt * 10（因为我们的i左移了一位）。注意终止条件为high和cur均为0（或者low == num），因为此时我们才检查完了原数的每一位。
class Solution {
public:
int digitOneInNumber(int num) {
int high = num / 10, cur = num % 10, low = 0, ans = 0;
long digit = 1;
while (high || cur) {
if (!cur) ans += high * digit;
else if (cur == 1) ans += high * digit + low + 1;
else ans += (high + 1) * digit;
low = cur * digit + low;
cur = high % 10;
high /= 10;
digit *= 10;
}
return ans;
}
};
LCR 163. 找到第 k 位数字
Note: 就是找第k位究竟位于哪个数字，统计每个位数的数字总数并依次减去（从大到小），如1位数总共9个，每个1位，共9位；2位数共90个，每个2位，共180位；这里的数位dp维护三个变量，digit位数，start该位数的首个数字，total该位数总计数字位数和，递推过程为：
++digit;
start *= 10;
total = start * 9 * digit;
每次把k减去total直到total <= k，便可计算到底是在哪个数中，应该是在start + (k - 1) / digit这个数中，为什么要-1呢？比如k是10，减去9后为1，这里的1是二位数中的第一个数字位，下标应该是0，因此要-1。求在该数中具体哪个位置也是同理，(k - 1) % digit。
LCR 164. 破解闯关密码
Note: 贪心，只考虑局部，按照a + b < b + a的顺序排序。
LCR 168. 丑数
Note: 每一个丑数一定是前面的某一个丑数乘上2 3或者5得来，因此使用动态规划，设三个指针来分别指向2 3 5所乘的前面的丑数。初始时都指向第一个丑数1（dp[0]），然后开始递推，每次递推取三个乘积的最小值并且对指针做移动，使用了哪个指针，哪个指针就右移，注意这里并不一定只使用了某一个指针，可能用了多个（因子不同但乘积相等的情况），因此都要判断一遍。
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp[0] = 1;
int factor2 = 0, factor3 = 0, factor5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = 2 * dp[factor2], next3 = 3 * dp[factor3], next5 = 5 * dp[factor5];
int res = min(next2, min(next3, next5));
if (res == next2) ++factor2;
if (res == next3) ++factor3;
if (res == next5) ++factor5;
dp[i] = res;
}
return dp[n - 1];
}
};
LCR 170. 交易逆序对的总数
Note: 归并排序过程中求逆序对个数，注意数组的归并排序需要额外的辅助空间，在辅助数组中合并两个有序子数组，然后拷贝回原数组。合并过程中，如果左边数组当前元素nums[l]>右边数组当前元素nums[r]，那么逆序对个数要增加lend - l + 1个，因为l以及后面的左边数组元素一定都是>nums[r]的，否则不会增加新的逆序对。
LCR 171. 训练计划 V
Note: 思考：为什么走到空节点只移动到另一链表头结点，而不再走一步？这样可能导致错过了交点，因为交点可能是另一链表的头节点，而这个节点被忽略了（一个链表是另一个链表的子链表，比如1, 3和3，如果走到空节点再走一步，那么最终相遇的地方是null）。
LCR 173. 点名
Note: 本题由于数组本身有序，因此可以使用二分，转化过来就是找最小的不满足nums[i] == i的下标i，而且数组从第一个错位下标开始，每一个下标都不满足该条件，而之前都是满足的，也就是说，该条件从左到右是从满足到不满足，也就是相当于lt条件，因此采用二分模版I:
while (l <= r) {
mid = l + (r - l) / 2;
if (cond(mid)) l = mid + 1;
else r = mid - 1;
}
获取l作为不满足num[i] == i的最小下标i，即为答案。
LCR 177. 撞色搭配
Note: 等价于找出两个只出现一次的数，首先对整个数组做异或，得到结果res是两个目标数的异或值，如何分开这两个数呢？我们可以找到他们的最低的不同位，这个不同位可以通过res & (-res)来得到？为什么，这个结果是res的最后一个1，由于两个数异或，相同的位都变为0，不同的位才变为1，因此最后一个1也就等价于最后一个不同位。
然后根据这个最低的不同位，把数组分成两部分，一部分是在上述位（两个目标数的最后一个不同位）为1的（包括一个目标数），一部分是在上述位为0的（包含最后一个目标数）。由于除了两个目标数，其他数都是成对的，因此对两组数分别进行异或，最终可得到两个目标数。这里分割数组并不是真的分割，而是设置两个变量，对于该位为1的数，异或到一个数去，否则异或到另一个数，在分组的同时进行异或计算。
class Solution {
public:
vector<int> sockCollocation(vector<int>& sockets) {
int res = 0;
for (auto& socket: sockets) res ^= socket;
vector<int> ans(2);
// 获取最后一个1的位置，也是两目标数最后一个不同的位置。
int lastOne = res & (-res);
for (auto& socket: sockets) {
// 一边分组一边异或
if (socket & lastOne) ans[0] ^= socket;
else ans[1] ^= socket;
}
return ans;
}
};
LCR 180. 文件组合
Note: 本题双指针不可从两端开始，因为更像滑动窗口，是否可以这样理解，找两个数满足要求，就可以左右双指针；而找一个合适的窗口，则必须从左边开始扩张，为什么呢？如果是找两个端点，那么端点的和往中间靠拢时可能不变，但是窗口的和一定会减小，因此该题必须使用滑动窗口。
LCR 181. 字符串中的单词反转
Note: 倒序遍历，获取每个单词加入到答案末尾。
LCR 184. 设计自助结算系统
Note: 队列的最大值，与栈的最大值主要不同在于栈是先进后出，后面入栈的最大值会被先弹出栈（同时也先获取），不影响前面的，因此直接将最大值从小到大累积到栈里没有问题，因为后进栈的先出，如何是当前最大值出栈，那么出栈后最大值栈顶就是次最大值。但是队列是先进先出，后进队列的最大值需要后出队列，但是需要先于前面入队的最大值获取，并且还会影响前面的最大值（如果比前面的最大值大，前面的最大值是无效的），如果只使用一个普通队列来存的话，是没办法做到的。
因此最大值队列需要使用双端队列deque，每次入队时，使用单调队列思想，如果当前元素比队尾元素大，就一直向后弹出，直到当前元素<=队尾元素，然后当前元素入队，因为队尾元素如果比当前元素小，说明他们是无效的前面的最大值，需要弹出。此时最大值队列是递减队列，获取最大值直接从队头获取即可，出队时，检查当前出队元素是否是最大值队列队头元素，是的话，就需要把最大值队列的队头出队。其实使用双端队列最主要的原因就是后面入队的元素可能使得前面的最大值无效，而栈则不会有这一问题。
LCR 185. 统计结果概率
Note: 与骰子数量和点数有关的动态规划，骰子数量n，当前点数x，那么dp[n][x] = Σdp[n - 1][x - k] / 6, k = 1~6，因为每一个扔出的骰子可能是1~6点，而每一情况的概率都是1 / 6，故第n个骰子扔出时总和为x可视为由第n - 1个骰子扔出时总和为x - k，并且该骰子扔出k得到（k为1~6）得到。这里要注意的是，k并不是一直可以任取1~6，而是有限制的，原因是x - k受到n - 1的限制，因为扔n - 1个骰子时，总和的范围是[n - 1, 6 * (n - 1)]，因此x - k必须只在此范围内。
另外一个就是下标问题，在使用一维数组时，如果骰子数为n，数组第一个下标0实际代表的是总和n，可以理解为下标j满足x = j + n，其中x为总和值，j为对应该总和的数组下标，则j = x - n。在递推时，要找到x - k对应上一层的数组下标，因为总和x对应的上一层数组下标j'有x = j' + n - 1，即j' = x - n + 1，那么上一层数组中x - k对应的下标j'也就是x - k - n + 1 = j - (k - 1)，其中k = 1~6，因此我们用一个k' = 0~5来取代(k - 1)，得到j' = j - k'。那么上面的递推式可以写成dp[j] = Σdp[j - k'] / 6，由于本层计算j时依赖左上，因此需要倒序遍历以防止覆盖。
再考虑之前所说的范围问题，因为x - k = j + n - k = j + n - (k - 1) - 1 = j + n -k' - 1，故n - 1 ≤ j + n - k' - 1 ≤ 6 * (n - 1)，那么化简得到j - 5 * n + 5 ≤ k' ≤ j，只在该范围内考虑k'即可。最后要注意的是每次计算dp[j]，需要用一个temp，初值0，计算完成之后把temp赋值回dp[j]，不能直接在dp[j]上累加。
class Solution {
public:
vector<double> statisticsProbability(int num) {
vector<double> dp(6, 1 / 6.0);
for (int i = 2; i <= num; ++i) {
int total = 5 * i + 1;
// 每轮扩容
dp.resize(total);
for (int j = total - 1; j >= 0; --j) {
int kmax = min(j, 5);
double temp = 0;
for (int k = max(j - 5 * i + 5, 0); k <= kmax; ++k) {
temp += dp[j - k] / 6;
}
dp[j] = temp;
}
}
return dp;
}
};
LCR 186. 文物朝代判断
Note: 意义不明的题，数据就给那么一点点，直接哈希表加最大最小值卡窗口，在数据量很大的情况下（数组很大）肯定是比排序+遍历快多了，哈希表的主要意义是判重，一旦有重复数字出现就失败。（重要！）
class Solution {
public:
bool checkDynasty(vector<int>& places) {
bool exist[14]{};
int maxPlace = 0, minPlace = INT_MAX;
for (auto& place: places) {
if (place) {
if (exist[place]) return false;
exist[place] = true;
maxPlace = max(maxPlace, place);
minPlace = min(minPlace, place);
}
}
return maxPlace - minPlace <= places.size() - 1;
}
};
LCR 187. 破冰游戏
Note: 经典约瑟夫环问题，如果某一次报数有一个人编号为k，其在上一次报数中的编号一定是(k + target) % n（n为上一次报数时的人数），最后一个剩下的人在最后一次报数中的编号为0，不断向上递推即可。
LCR 189. 设计机械累加器
Note: 最傻逼的题目，没有之一。
LCR 190. 加密运算
Note: 位运算题目，分32位分别加或者并行运算均可。
class Solution {
public:
int encryptionCalculate(int dataA, int dataB) {
// 分32位运算
int ans = 0, carry = 0, bit = 1;
for (int i = 0; i <= 31; ++i) {
int Abit = dataA & bit, Bbit = dataB & bit;
ans |= (Abit ^ Bbit ^ carry);
carry = (Abit ^ Bbit) & carry | (Abit & Bbit);
carry <<= 1;
bit <<= 1;
}
return ans;
// 循环进位，dataB存放每次的进位，直到进位为0
while (dataB != 0) {
int carry = (dataA & dataB) << 1;
dataA ^= dataB;
dataB = carry;
}
return dataA;
}
};