LCR 004. 只出现一次的数字 II
Note: 从哈希表到按位计算，再到数字电路设计
LCR 005. 最大单词长度乘积
Note: 用单词掩码的比较来取代单词的直接比较，可以只记录0 1，不用记录次数（不同于字母异位词），并且可以对掩码相同的单词记录最长长度，来减少无用计算（比如掩码一样但长度更短的单词，就没有计算的必要了）。
LCR 008. 长度最小的子数组
Note: 典型的滑动窗口题
LCR 009. 乘积小于 K 的子数组
Note: 这题和上一题都使用滑动窗口，但是主要的区别是在于记录结果的时机，上一题是要求子数组和≥target，因此结果记录应该是在左指针右滑的过程中（滑动窗口都是外右内左），也就是内部循环中，而且左指针右移的开始时机是在条件满足时，因为这是正向条件（一开始是不满足的，需要右移右指针来满足），左指针右移的目的是为了使得条件不再满足，并在这个过程中记录结果（也就是所有满足条件的结果）；
而本题的条件是乘积<k，是反向条件（一开始是满足的，右移右指针来使得条件不满足），那么我们是在右指针右移的过程中去记录结果，直到条件不再满足，然后左指针右移的目的是让条件重新被满足，因此左指针左移的时机是条件不满足时。
LCR 010. 和为 K 的子数组
Note: 本题不能用滑动窗口解，因为子数组里有正数也有负数，k自己也可正可负，因此窗口没有明确的单调性（不像前两题有满足和不满足条件的线性过渡）。由于子数组nums[i:j]的和实际就是j的前缀和减去i - 1的前缀和，如果其等于k，那意味着pre[j] - pre[i - 1] = k，也就是pre[i - 1] = pre[j] - k，因此我们可以在遍历数组的过程中计算每个位置的前缀和pre，并将出现次数记录在哈希表里，同时检查哈希表里是否有pre - k这个前缀和键，如果有则将其出现次数加到答案中，因为其每出现一次，就意味着使当前位置j满足pre[i - 1] = pre[j] - k的i值出现一次，那么nums[i:j]就是一个满足题意的子数组（我们并不需要知道i是多少！），答案就应该+1。要注意的是0在哈希表中出现的次数应该初始化为1，因为如果第一个数就等于k的话，此时pre - k为0，nums[0:0]是一个满足题意的子数组，因此0对应的值应初始化为1。
LCR 011. 连续数组
Note: 和上题基本一致，如果我们将1视为+1，而将0视为-1，那么含相同数量的0和1的子数组就等价于和为0的子数组，这就和上题几乎没差异了，唯一有差异的点在于，上题是计算子数组的数量，因此哈希表存的是出现次数，本题求的是最长长度，那么因此哈希表存的应该是某个值（前缀和）首次出现的位置，在计算时用当前位置减去该位置即得到结果，因此一旦某个前缀和键出现在哈希表中，那么我们就不再更新其位置，防止覆盖。
LCR 013. 二维区域和检索 - 矩阵不可变
Note: 前缀和二维版
LCR 017. 最小覆盖子串
Note: 以上四题全是滑动窗口，不同之处在于14 15是固定窗口大小（当然也可以视为可变滑动窗口，长度达到固定值时才能记录结果），而本题，上一题和8 9都是可变窗口大小，写法上略有不同。固定窗口大小时，先将窗口扩展到最大，然后逐位置整体右移；可变窗口大小时，若未限制长度最大值，则外层循环是右指针右移，内层循环是左指针右移：
while (右指针 < 右边界) {
右指针位置进入窗口及相应操作;
// 条件为正向条件（一开始不满足，右指针右移导致满足）
while (正向条件满足) {
记录结果;
左指针位置离开窗口及相应操作;
++左指针（按需调整，不一定只+1，如16题）;
}
//
// 条件为反向条件（一开始满足，右指针右移导致不满足）
while (反向条件不满足) {
左指针位置离开窗口及相应操作;
++左指针（按需调整，不一定只+1，如16题）;
}
记录结果;
//
++右指针;
}
如果固定窗口大小（或者说可变窗口大小，但窗口达到一定大小才记录结果， 如LCR 015. 找到字符串中所有字母异位词）:
while (左指针 + 目标大小 ≤ 右边界) {
while (窗口大小 < 目标大小) {
获取右指针位置处内容;
if (某些条件不满足，如右指针处内容不在目标中，或窗口内内容超过目标所需) break;
右指针位置进入窗口及相应操作;
++右指针; ++窗口大小;
}
if (窗口 == 目标) 记录结果;
if (当前右指针处内容不在目标中（需要重置窗口到右指针右边）) {
++右指针;
左指针 = 右指针;
窗口大小 = 0;
窗口内容清空;
} else {
左指针位置离开窗口及相应操作;
++左指针;
--窗口大小;
}
}
LCR 021. 删除链表的倒数第 N 个结点
Note: 链表类题目加头结点dummy一般是为了避免对首个节点进行特判。
LCR 025. 两数相加 II
Note: 链表反转递归版：
ListNode* reverseList(ListNode* head) {
if (!head->next) return head;
ListNode* last = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return last;
}
LCR 027. 回文链表
Note: 相比于先找中点，然后翻转右边链表，再从两边向中间比较（实际时间O(3n)）。更快的方法是直接在找中点过程中翻转左边链表，然后从中间向两边比较。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
// 翻转左边，一边遍历一边翻转
ListNode* fast = head, * slow = head, * pre = nullptr, * next;
// pre指向左边链表翻转后开始节点
while (fast && fast->next) {
fast = fast->next->next;
next = slow->next;
slow->next = pre;
pre = slow;
slow = next;
}
// fast为真，链表节点数量为奇，比如5，则此时slow位置为3，
// 需要为4，因此则让slow指向下一位置，但为偶则不需要
// 比如4个节点，slow则指向3（右边链表开头位置应为ceil(n / 2) + 1）
if (fast) slow = slow->next;
// 此时slow为右边链表开头节点
while (pre && slow) {
if (pre->val != slow->val) return false;
pre = pre->next;
slow = slow->next;
}
return true;
}
};
LCR 030. O(1) 时间插入、删除和获取随机元素
Note: 第一眼以为本题是LRU，但其实并不是，首先它不需要考虑元素顺序，并且要求O(1)的随机访问，在LRU中，双向链表存储真实节点，哈希表存放元素值与链表节点的映射，如果要根据链表大小来随机访问的话，是做不到的。因此使用数组来存放真实数据，然后哈希表来记录元素值 -> 数组索引的映射，这样插入比较方便，删除时，可以先通过哈希表找到待删除数组项的下标delIdx，然后将其与数组末尾元素交换，最后删除数组末尾项，同时更改哈希表中原数组末尾元素的索引为delIdx，实现O(1)删除，这样做虽然会打乱元素插入顺序，但是本题也不要求顺序（随机访问要求每个位置访问机会相等，因此也无关顺序），所以就无所谓。
LCR 031. LRU 缓存
Note: 插入用头插似乎更快
LCR 033. 字母异位词分组
Note: 单词转化为哈希键（直接排序单词更方便）
LCR 035. 最小时间差
Note: 类似33题，时间字符串化为数字时间，由于范围有限可以基数排序。注意最后还要求一个头尾时间差（可以认为最后一个时间是最开始的时间+1440）。
LCR 040. 最大矩形
Note: 和上题其实类似，只不过要转换一下，计算矩阵中每个点为右下角的矩形的最大面积，首先遍历矩阵计算出每个位置(i, j)其左侧（包括自己）连续1的最大个数，作为矩形的高，那么矩形的每一列就被转化成39题中的柱状图，问题也就变为，对矩形每一列进行39题中的计算，求其最大矩形面积。然后取每一列（每个柱状图）中最大矩形面积作为答案。
class Solution {
public:
int maximalRectangle(vector<string>& matrix) {
int row = matrix.size();
if (row == 0) return 0;
int col = matrix[0].size();
vector<vector<int>> left(row, vector<int>(col, 0));
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (matrix[i][j] == '1') left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
}
}
vector<int> st;
int mid, ans = 0;
for (int j = 0; j < col; ++j) {
st.clear();
for (int i = 0; i <= row; ++i) {
while (!st.empty() && (i == row || left[i][j] < left[st.back()][j])) {
mid = st.back(); st.pop_back();
ans = max(ans, left[mid][j] * (i - (st.empty() ? -1 : st.back()) - 1));
}
st.emplace_back(i);
}
}
return ans;
}
};
LCR 043. 完全二叉树插入器
Note: 三种方法：直接用vector模拟CBT、用队列只存待插入节点、以及二进制移位方法（只存根节点，每次插入时花O(logn)时间去找插入位置）。
class CBTInserter {
public:
CBTInserter(TreeNode* root) {
// 二进制（只存根节点，时间换空间）
this->root= root;
queue<TreeNode* > que;
que.emplace(root);
TreeNode* cur;
while (!que.empty()) {
++cnt;
cur = que.front(); que.pop();
if (cur->left) que.emplace(cur->left);
if (cur->right) que.emplace(cur->right);
}
}
int insert(int v) {
++cnt;
int highbit = 31 - __builtin_clz(cnt);
TreeNode* node = root, * cur = new TreeNode(v);
for (int i = highbit - 1; i >= 1; --i) {
if (cnt & (1 << i)) node = node->right;
else node = node->left;
}
if (cnt & 1) node->right = cur;
else node->left = cur;
return node->val;
}
TreeNode* get_root() {
return this->root;
}
private:
TreeNode* root;
int cnt = 0;
};
LCR 045. 找树左下角的值
Note: 深度遍历与广度遍历均可，深度遍历在当前节点是叶子节点，且深度更新时对答案进行更新，因此需要保证最底层最先被访问的是最左的（叶子）节点，实际上前中后序均可。
LCR 046. 二叉树的右视图
Note: 和上题一样，深搜广搜均可，只不过深搜的话一定要中右左。保证每一层的最右侧节点在本层被最先访问（和上一题不一样的点主要就是这个，因为本题是要获取每一层最右侧节点，从而必须按层顺序访问最右侧节点，而上一题是获取最底层最左侧节点，只要保证最后一层（最大深度层）的最左侧节点在最后一层被最先访问到即可）
LCR 048. 二叉树的序列化与反序列化
Note: 深度遍历与广度遍历均可，但是广度快一些（因为深度遍历需要序列化最底层空节点，多了几乎一倍的时间，广度则不会）
LCR 050. 路径总和 III
Note: 本题是LCR 010. 和为 K 的子数组的二叉树版，把二叉树每条根到叶子的路径想象成一个数组，那么本题就是在每条路径对应的数组上寻找和为k的子数组。