一、哈希图
HASH（key）= key MOD p；
解决哈希冲突的方法有：线性探测、拉链法等。
第一题（1 两数之和）
- unordered_map<int, int>，定义哈希图
- nums.size()，计算 vector 长度
- hashtable.find() 搜索，hashtable.end() 搜索不到的返回；it 承担迭代结果
- hashtable[nums[i]] = i，哈希表赋值
第二题（49 字母异位词分组）
- .emplace_back(str) 等价于 mp[key].push_back(str);但 emplace_back 更高效（原地构造）。
- 现代 C++ 的理念就是：只要类型太复杂，就用 auto。让编译器推导。
- string key = str;用 key 来代替 str 否则原字符串会被改变
- 在迭代器里推荐 ++it
sort(key.begin(), key.end());可用于对字符串的排序，复杂度为 O(n log n)，这是升序排序，此外还有：sort(v.begin(), v.end(), greater());降序排序；自定义比较器（return 后的内容可根据实际情况替换）。
第三题（128 最长连续序列）
- unordered_set st(nums.begin(), nums.end());构建了一个哈希集合，且自动去重
- const string& s，可用来避免昂贵的拷贝
一些哈希相关的函数：①count(x)，判断元素是否存在（速度比.contains() 快得多）②find(x)，同上，但可取得迭代器
③size() 大小 ④empty() 判断空 ⑤insert() 插入
二、双指针
第四题（238 移动零）
- vector 的长度：nums.size()
- swap(nums[left], nums[right]);交换数组的两个元素
第五题（11 盛最多水的容器）
- r = height.size()- 1；
- --r;右指针是递减的
- 为何用题解方法消耗内存较大？
思路关键：每次移动对应高度较小的那一个指针
第六题（15 三数之和）
- 不重复意味着要排序
- ans.push_back({nums[first], nums[second], nums[third]}); {a, b, c} 是一个 initializer_list，它会自动构造成一个 vector, 然后传给 ans.push_back
- 主要思路就是，首先排序，然后固定 first，second 和 third 的变动是并列的
从下面开始用 Java 写了
第七题（42 接雨水）
- 思路：计算每一个 i 对应的 leftMax 和 rightMax，这决定了该位置能积攒多少水，动态规划
- for (int i = n-2; i >= 0; i--)rightMax 应该从右往左遍历 2，即递减
- leftMax[i] = Math.max(leftMax[i-1], height[i]);最大值比较包含 i 位置自身
- int[] a = new int[n];记得限定长度
- 数组 n.length
三、滑动窗口
第八题（3 无重复字符的最长子串）
- Set occ = new HashSet();定义哈希表
- 初始化 rk = -1，且在滑动过程中是一个单增的量，因为右指针扫过的地方已经确定无重复，只需向后扩张
- 字符串 s.length()；s.charAt(i)
- occ.remove(s.charAt(i-1)); occ.add(s.charAt(rk + 1)); occ.contains(s.charAt(rk + 1))几个相关的哈希表的函数
- rk - i +1 这样比 occ.size() 效率高
新增使用 HashMap 的方法（上面是使用集合的做法）。
第九题（438 找到字符串中所有字母异位词）
- 题解是利用 i 的循环代替了显式的 l 或 r 指针
- return new ArrayList();返回列表为空的情况，方便调用方再使用.size()、.add() 等函数
- 第 0 遍循环也要记录 s 的字母数量：++sCount[s.charAt(i) - 'a'];
另外，List 是接口，ArrayList 是实现类，该接口被限制只暴露 add、get、size、remove，而不暴露内部实现或 ArrayList 的私有函数。
四、子串
第十题（560 和为 K 的子数组）
- mp.getOrDefault(pre, 0) + 1：用这个函数的原因：如果 pre 没有出现果，mp.get(pre) 会返回 null，null+1 会崩溃
此题的关键思路是：
首先记录一下，这个题目看完思路以后自己手搓，除了定义 HashMap 和 containsKey 函数名写错了，其他全写对了。
第十一题（239 滑动窗口最大值）
- 我学习的是单调队列的思路，相关函数有：① deque.isEmpty()；② deque.peekLast()；③ deque.pollLast()；④ deque.offerLast(i)；⑤ deque.peekFirst()；⑥ deque.pollFirst();
- 注意：int[] ans = new int[n - k + 1];不要忘记 new
Java 是面向实现的编程：
第十二题（76 最小覆盖子串）
- 首先需要注意，该题目包含大小写字母；其次，思路为：右指针不断右移先找到涵盖了 t 字符串的位置，然后左指针左移，缩小窗口范围找到最短字符串
- s.substring(ansLeft, ansRight + 1)：加一的原因是，Java 的该函数为左闭右开区间
遍历一个 String 的各个字符串：
五、普通数组
第十三题（53 最大子数组和）
- 动态规划法：pre = Math.max(pre + x, x);这样才能以 x 为新的字符串起点（而不是 pre = Math.max(pre + x, pre);）
- Math.max() 函数的利用
- 分治法？线段树的概念
第十四题（56 合并区间）
- merged.add(new int[]{L, R});后面是数组的初始化列表
- return merged.toArray(new int[merged.size()][]);最后的返回值应该转换成题目要求的数据类型
思路关键：排序（可行性由反证法证明），然后遍历区间，根据已有的最末端点与当前区间的起点比较，判断是否合并，积累 comparator 函数的写法（Comparator 函数是写在 Arrays.sort 的括号里的）。
第十五题（189 轮转数组）
- 选择的是数组翻转的方法
- nums 需要通过参数传给 reverse 函数，且在 Java 中传入后进行 reverse 是可以改变原数组的，传入的是引用
第十六题（238 除自身以外数组的乘积）
- 思路：分别后向、前向计算得到前缀乘积和后缀乘积 L、R 数组，再分别相乘得 ans
- 若想要空间复杂度为 O(1)，则用 answer 数组代替 L 数组，同时取消 R 数组，用 R 来记录即可
第十七题（41 缺失的第一个正数）
- 注意这里的实现：我们给数组中的第 |x|−1 个位置的数添加一个负号，注意如果它已经有负号，不需要重复添加。nums[num - 1] = -Math.abs(nums[num - 1]);
- 思路二置换法：将 nums[i] 换到下标为 nums[i]-1 的位置，最多替换 N 次；注意 nums[i] =x=nums[x−1] 的死循环
思路一直接上图：
六、矩阵
第十八题（73 矩阵置零）
- 似懂非懂：为什么使用一个标记变量需要倒序，而使用两个标记变量的方法不用考虑这一点呢？
第十九题（54 螺旋矩阵）
按层模拟法：
这个方法注意：在每层向左和向上遍历时，要把 for 循环放入 if (left < right && top < bottom) 条件判断中，不是为了越界判断，而是为了防止重复输出。
另外，此题注意最初的矩阵判空。
模拟法可借鉴之处：int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
以及对方向的判断。
第二十题（48 旋转图像）
法二：用翻转代替旋转
因为这样的操作可以得到关键等式
法一：原地旋转法
处于循环中的四项：
偶数时枚举 n2/4=(n/2)×(n/2) 个位置；
奇数时枚举 (n2−1)/4=((n−1)/2)×((n+1)/2) 个位置；
最后两种情况在代码中可以统一为：
第二十一题（240 搜索二维矩阵Ⅱ）
- 法二：'Z'字形查找，从右上角为起点（此时它是这一行最大的，这一列最小的）
法一：逐行进行二分查找
这里积累向其他函数传递一行数据的简洁写法：
七、链表
第二十二题（160 相交链表）
- 法一：将链表 A 存入名为 visited 的哈希表中，逐个判断链表 B 的各个节点是否在哈希表中：visited.contains(temp)；注意：temp 为 ListNode 类型，比较的是是否为同一个节点而不仅仅是 val 是否相同
法二：双指针的方法，过于巧妙：
第二十三题（206 反转链表）
- 迭代法，注意：要用 next = cur.next 将下一个节点存储下来
- 递归法，结束条件判断为 if (head == null || head.next == null)
递归找到新的头，然后 head.next.next = head;
第二十四题（234 回文链表）
- 快慢指针，最后还原链表
第二十五题（141 环形链表）
- 快慢指针，根据结果来看，把两个指针最初都放在 head 再移动和比较效率会更高
第二十六题（142 环形链表Ⅱ）
- 快慢指针
关键公式：含义是从相遇点，再走几圈和 c 步，和从 head 出发的节点会在环的入口相遇
第二十七题（21 合并两个有序链表）
- 递归法：关键语句：l1.next = mergeTwoLists(l1.next, l2);
- 迭代法：使用一个 prev（初始化语句：ListNode prehead = new ListNode(-1);）来记录头节点，最终返回 return prehead.next;
合并后至多有一个不为空 prev.next = l1 == null ? l2 : l1;
第二十八题（2 两数相加）
- 若一个数（链表）长度较短，则相当于后面有好多 0
- 最后如果 carry>0，则需要多加一位
- l1 进行.next 操作时需要判断是否为空，因为为空时也在循环里，当成 0 处理了
第二十九题（2 两数相加）
- 栈的方法：加入 dummy（用的是哑节点的方法）的目的是统一删除头节点和后续节点的操作。定义额外的哑节点的方法（ListNode dummy = new ListNode(0, head);）
栈保存的是对节点的引用（其地址，相当于这个节点多了一条被指向的线）
- 双指针的方法：加入哑节点后，先让 first 指针走 n 下，然后让 first 和 second 一起走，直到 second 走到要删除的前一个节点的位置
第三十题（24 两两交换链表中的节点）
- 加入哑节点后，在 temp.next != null && temp.next.next != null 的条件下进行交换即可
第三十一题（25K 个一组翻转链表）
思路不难，就是代码复杂，这里的翻转链表和前面的思路一样吗？
第三十二题（138 随机链表的复制）
这里直接放了哈希表法的代码，因为对这个题的理解还不是很深
第三十三题（148 排序链表）
- 快慢指针找中点
- 左右子链表分别递归调用 sortList()
- 最后记得加上剩余的长度 h.next = left == null ? right : left;
第三十四题（23 合并 K 个升序链表）
- 顺序合并、分治合并
- 使用优先队列合并：定义一个类来存储状态用以比较节点值的大小，使用接口 class Status implements Comparable，并在后面定义比较函数：public int compareTo(Status status2)；
for (ListNode node: lists) 取出每个链表的第一个节点，然后从最小堆中取出堆顶 queue.poll()；然后放入最小值节点的下一个 queue.offer(new Status(f.ptr.next.val, f.ptr.next))
- 复杂度的分析没明白……
第三十五题（146LRU 缓存）
- 这道题目代码写起来不难，就是思路很新之前没有学过，然后会有很多小细节
唯一一个私有函数有返回值类型的，因为要将其用在删除 cache 对应的一对映射中
将新节点插入链表的同时要更新哈希表，删除同理（cache.remove()）
初始化头尾哑节点要记得把他们连起来（后两句）
无参构造函数和带参构造函数 （注意：构造函数无返回值类型）
八、二叉树
第三十六题（94 二叉树的中序遍历）
- 递归代码很简单，这里用的是迭代的方法'颜色标记法'
- 一些语法知识：
①Deque stack = new LinkedList<>();既可以当作栈（stack.push(x);stack.pop()）也可以当作队列（deque.offer(x);deque.poll()），关键是看使用了什么方法
②构造函数前是否加 public 根据需求
关键代码：
第三十七题（104 二叉树的最大深度）
- 深度优先遍历：利用递归
- 广度优先遍历：利用队列，逐层加入所有节点，统一弹出上层所有节点
- Queue 与 Deque 的区别：
①Queue 是单向队列，方法：offer(x); poll(); peek()。使用场景：二叉树层次遍历、拓扑遍历
②Deque 是两头都能进出的双端队列，方法：addFirst(e) / addLast(e) / pollFirst() / pollLast()；以及栈语义：push(e) / pop()。使用场景：当栈用、双端操作（滑动窗口、单调队列）
第三十八题（226 翻转二叉树）
- 深度和广度两种方法
第三十九题（101 对称二叉树）
迭代法：如果比较的两个位置都为空，应该 continue；而不是返回 true
关键语句：
递归法：关键语句
第四十题（543 二叉树的直径）
- 递归计算每一个节点的 L+R
第四十一题（102 二叉树的层序遍历）
- 广度优先遍历即可
- List ans = new ArrayList();这种定义方式只关心<>中是'List< Integer >'，而不是实现类
第四十二题（108 将有序数组转换为二叉搜索树 BST）
- 递归为 root 的 val、left、right 赋值
第四十三题（98 验证二叉搜索树）
- Long.MIN_VALUE 与 Long.MAX_VALUE：定义为 long 类型的数
- 递归法：为每一个 node 的验证限制范围：min 和 max，在递归调用中改变上下限
- 中序遍历法，先访问到最左节点，再逐层向上向右访问
第四十四题（230 二叉搜索树中第 K 小的元素）
- 思路同上中序遍历法，循环条件 while (root != null || !stack.isEmpty()) 表示此节点还没有遍历完（还在往下走）或栈内不为空（还有之前的祖先节点没处理）
第四十九题（236 二叉树的最近公共祖先）
- 深度优先遍历：当左子树或右子树中有 p/q 或此时正在遍历的节点即为 p 或 q 时，dfs 函数可以返回 true；
- 当满足 if (lson && rson || (root.val == p.val || root.val == q.val) && (lson || rson)) 条件时，即为找到了最近公共祖先
九、图论
第五十一题（200 岛屿数量）
- 深度优先方法：依次遍历矩阵中的各个元素，并将与该元素能构成岛屿的节点的值设置为'0'（注意这里是字符），对于每个节点上下左右依次进行判断是否要进行深度遍历
时间复杂度：O(MN) 每个格子最多处理一次，邻居最多检查 4MN，≤5MN
第五十二题（994 腐烂的橘子）
- 多源广度优先遍历：使用队列存储腐烂的橘子，然后从每一个节点向四个方向延申，同时更新腐烂时间记录数组的值，这些操作使得每个节点最多被遍历一次
- 本题目使用 C++ 编程练习，注意的语句：memset(dis, -1,sizeof(dis)); Q.emplace(i, j); Q.empty(); ~dis[tx][ty] (只有 -1 按位取反后的值为 0)
第五十三题（207 课程表）
- 思路转化：检查改题目的场景对应的图是否存在拓扑排序
- BFS 方法：使用队列来保存入度初始为 0 或减至 0 的节点，每取出一个节点，就将以其为起点的边的另一头节点的入度减一，减至 0 时加入队列，每取出一个节点并访问其相邻节点时，将答案数量增加一
- 本题目使用 Java 编程，注意的语句：queue.offer(i); queue.poll(); edges.add(new ArrayList());
第五十四题（208 实现 Trie (前缀树)）
十、回溯
第五十五题（46 全排列）
- 设置 output 的目的是：亦可用标记数组来表示哪些数已经放入结果数组中，若不使用，那么可以通过划分左右两侧的数据来实现，左侧为已经放入结果数组的，右侧为还没有的
- 如果 first 等于 n，也就是 n 及以后的数还没有放入结果数组，即等价于所有数字已经全部放入结果数组，那么将该排列加入结果数组中
- 恢复现场的操作
第五十六题（78 子集）
- 每个元素要么加入（1），要么不加入（0）集合，因此可以使用与其对应的（1 << n）个二进制数来表示集合中的存在情况
- 关键判断语句：if ((mask & (1<<i)) != 0)：哪一位是 1，则将其加入集合
- 最后一句为 ans.add(new ArrayList(t));，而不能是 ans.add(t);？否则 ans 所有值都指向同一块 t 的内存地址，会存储最后一个子集的内容，即各个相同
第五十七题（17 电话号码的字母组合）
- 建立按键字母 Map 后，回溯，直至每种情况下达到字母的最大长度
- 需要注意的语法：backtrack() 函数中的 new StringBuffer()：支持 append 和 delete，适合回溯，不同于 String（字符串不可变）；字符串取出某一个字母：digits.charAt(index)
第五十八题（39 组合总和）
- 要想剪枝，需要排序：Arrays.sort(candidates);
第五十九题（22 括号生成）
- 思路（合法的情况）：当 open 括号个数比 n 小时，仍然可以加入 open 括号（即前括号），当 close 括号个数比 open 括号个数小时，可以加入 close 括号（即后括号）
- ans.add(cur.toString());（其中 cur 为 StringBuilder 类型），这里不需要在 add() 方法中 new，因为 toString() 方法就创建了一个新的 String 对象，不变地存储字符数组的内容
第六十题（79 单词搜索）
- 各个数值作为第一个字符逐次遍历，而后对每一个的上下左右进行遍历，访问过的字符标记为'\0'，最后再赋值 words[k] 恢复现场（因为能执行到这里说明该元素值与 work[k] 是一致的）
- 将 String 转换为字符数组：char[] words = word.toCharArray();
第六十一题（131 分割回文串）
第六十二题（51 N 皇后）
十一、二分查找
第六十三题（35 搜索插入位置）
- 找到序列中第一个≥target 的值对应的位置
第六十四题（74 搜索二维矩阵）
- 法一：两次二分查找；第一次首列上的二分查找，使用 while(left < right) 作为循环条件找到范围，第二次那一行上的二分查找，使用 while(left <= right) 作为循环条件找到是否有符合的值。
- 法二：一次二分查找，假想把各个行拼成一个序列，使用 matrix[mid/n][mid%n] 定位元素数值
第六十五题（34 在排序数组中查找元素的第一个和最后一个位置）
- 需要使用一个 lower 变量，选择在寻找不小于还是大于的元素位置：if (nums[mid] > target || (lower && nums[mid] >= target))
- while (left <= right) 与 right = mid - 1、left = mid + 1 通常一起出现
判断条件的必要性：
第六十六题（33 搜索旋转排序数组）
- if (nums[l] <= nums[mid]) 来判断左边的半个区间是否有序
- if (nums[l] <= target && target < nums[mid]) 来判断 target 是否在有序的那一侧范围内，如果不在则考虑另一侧
第六十七题（153 寻找旋转排序数组中的最小值）
- 判断条件 while (l < r) 与 r = mid; 和 l = mid +1; 配对出现
如图，以 high（最右侧的点的值）为基准，min 至 (high-1) 的值都小于 high 的值，0 至 (min-1) 的值都大于 high 的值
第六十八题（4 寻找两个正序数组的中位数）
十二、栈
第六十九题（20 有效的括号）
if (pairs.containsKey(chars[i])) 将括号映射为下面的哈希表，该语句用来判断目前是否正在处理后括号
第七十题（155 最小栈）
使用一个辅助栈，用来记录每一次压入一个数据时当前的最小值是多少（因为后面元素的进出栈不影响前面的最小值）
第七十一题（394 字符串解码）
- 这个题目思路比较清晰，但是编写起来需要注意的细节非常多，涉及到的数据类型很多
- 本题目中定义栈一定要使用 LinkedList sub = new LinkedList();因为 Collections.reverse 接收的是 List 类型的参数，不能声明为 Deque
- 进而，这里要用 addLast、removeLast()、peekLast() 方法，
- 如果我把代码中的 addLast()、removeLast()、peekLast() 都换成 push()、pop()、peek()，本应该输出 aaabcbc 的就会输出 cbcbaaa，为什么呢？
两种转型语法
第七十二题（739 每日温度）
- 使用单调栈，依次存入当前温度最高的那一天的下标（因为要计算的是 i - prevIndex）；若新来的温度比栈顶下标对应的温度高，则弹出栈顶，因为距离它最近的比它温度高的那一天已经找到
第七十三题（84 柱状图中最大的矩形）
十三、堆
第七十四题（215 数组中的第 K 个最大元素）
- 堆排序方法：在一次 heapify 调用中，一个节点最多下沉：树的高度 次，也就是 O(log n)
- 快速排序方法：挖坑法，随机选取一个数字，让其左边都比他小，右边都比他大，这个题目只需要不断递归寻找 k 所在的那一侧
第七十五题（347 前 K 个高频元素）
- 使用最小堆，维持个数为 k，利用记录的每个数字的频率，仅当遍历到的（数字，频率）对的频率大于堆顶时，弹出堆顶并压入；最终堆中保留的 k 个（数字，频率）对几位前 K 个高频元素
- for (Map.Entry<Integer, Integer> entry : occs.entrySet())，这是 Java 的增强 for 循环（for-each），类似使用方法：for (int num: nums)；因此可以理解 Map.Entry<Integer, Integer>在这里表示一种数据类型
- 语法积累：queue.offer(new int[]{num, count});
第七十六题（295 数据流的中位数）
十四、贪心算法
第七十七题（121 买卖股票的最佳时机）
使用一个变量记录最小值，遍历一遍即可得到答案
第七十八题（55 跳跃游戏）
- 使用 rightmost 变量在遍历过程中保存可到达的最右端位置
第七十九题（45 跳跃游戏Ⅱ）
在每一个 [0……end] 范围中，遍历各个数字，得到下一步可到达的最远位置
第八十题（763 划分字母区间）
记录每个字母出现的最后位置，然后在遍历过程中不断更新这个范围的 end 值，直到遍历变量 i 走到 end 的位置（说明该字母区间无需再延长）
