力扣hot100——子串、普通数组、矩阵
第二次刷题不在idea写代码，而是直接在leetcode网站上写，“逼”自己掌握常用的函数。
| 标志 | 掌握程度 | 解释 | 办法 |
|---|---|---|---|
| ⭐ | Fully 完全掌握 | 看到题目就有思路，编程也很流利 | |
| ⭐⭐ | Basically 基本掌握 | 需要稍作思考，或者看到提示方法后能解答 | |
| ⭐⭐⭐ | Slightly 稍微掌握 | 需要看之前写过的代码才能想起怎么做 | 多做 |
| ⭐⭐⭐⭐ | absolutely no 完全没有掌握 | 需要看题解才知道怎么做 | 背 |
| ⭐⭐⭐⭐⭐ | 有难度的高频题 | 需要看题解才知道怎么做，而且过几天就忘了这道题怎么做了 | 背背 |
| 10 | ⭐⭐⭐ | Medium | 子串 | 560/和为K的子数组 | 前缀和法 定义 s[i+1] = nums[0] + nums[1] + … + nums[i]; 下标从 i 到 j - 1 的非空连续子数组的元素和等于 k, 则 s[j] - s[i] = k ==> s[i] = s[j] - k 哈希表键值分别保存s[j]的值及其出现的次数，要注意加这句话初始化map.put(0, 1); 遍历数组，每次遍历都查找哈希表中是否包含s[j] - k | |
|---|---|---|---|---|---|---|
| 11 | ★★★★ | Hard | 子串 | 239/滑动窗口最大值 | 维护一个单调递减队列，注意队列中保存的值并不是元素的值，而是元素的数组下标，保持队头的元素是最大的。 遍历数组 如果当前遍历元素大于等于队尾元素，则将队尾元素移除，直到当前遍历元素小于队尾元素，则将当前遍历元素存入队尾 如果队头元素不在当前窗口则移除，每遍历完k个元素，将左边界元素移除 | 实现Deque接口的有两个类，一个是LinkedList类，另一个是ArrayDeque类。 但是在实现类的选择上，一般都是选择ArrayDeque类。 总结：在需要List的时候，用ArrayList实现；在需要Stack、Queue、Deque时，用ArrayDeque实现。 |
| 12 | ★★★★ | Hard | 子串 | 76/最小覆盖字串 | 使用两个大小为128的数组来保存目标字符串 和 当前遍历子串中的字符数 初始化最短左右边界为 -1 和 n 定义左右指针来遍历数组 将右指针的字符更新到数组中，调用函数检查 两个数组 是否覆盖 如果没有覆盖，右指针右移 如果覆盖了（注意这里是while循环），则更新最短的左右边界。如果左指针小于右指针的情况下（这里是if条件），左指针右移 最后返回最短左右边界的子串，注意这里要判断最短左右边界是不是最开始的那个 | s.substring(ansLeft, ansRight + 1) |
| 13 | ★★ | Medium | 普通数组 | 53/最大子数组和 | 遍历数组 当前和 加上 当前遍历数，并更新答案（取较大） 如果当前和 小于等于 0，说明对后面的和只会产生负面影响，所以将当前和更新为0，重新计和 | |
| 14 | ⭐⭐⭐ | Medium | 普通数组 | 56/合并区间 | 先将数组按照每个区间的左边界进行排序，然后遍历数组 用left 和 right保存当前左右边界 如果当前遍历区间的左边界小于当前右边界，则将右边界更新为 当前遍历区间的右边界 和 当前右边界的较大值 否则将当前的左右边界存入答案，并更新左右边界为当前遍历区间的左右边界 | Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); ans.add(new int[]{left, right}); ans.toArray(new int[ans.size()][]); |
| 15 | ⭐⭐⭐ | Medium | 普通数组 | 189/轮转数组 | 需要翻转三次数组， 第一次翻转整个数组， 第二次、第三次分别反转 k % n 之前的数组 和 k % n 之后的数组 | nums = “----->–>”; k =3 result = “–>----->”; reverse “----->–>” we can get “<–<-----” reverse “<–” we can get “–><-----” reverse “<-----” we can get “–>----->” |
| 16 | ★ | Medium | 普通数组 | 238/除自身以外数组的乘积 | O(N)时间复杂度，O(1)空间复杂度 遍历数组，建立一个ans[i]数组来保存，nums[i]之前的数乘积和 再次从后往前遍历数组，用一个变量来保存后缀和，每次遍历用 ans[i] * r 即为答案 | |
| 17 | ★★★★ | Hard | 普通数组 | 41/缺失的第一个正数 | 要求O(1)空间复杂度，将原数组nums构造成一个哈希表（重点是怎么构造这个哈希表） 映射规则，把 值为1 的元素 映射到 位置为0，把 值为2 的元素 映射到 位置为1 遍历数组，在[1,n]范围内的值 如果它不在对应的位置 就将它和正确位置上的元素交换位置 重点：不是 nums[i] - 1 != i, 而是nums[nums[i] - 1] != nums[i]，因为nums[nums[i] - 1] == nums[i]时，不需要交换，否则就进入死循环了 再次遍历数组，遇到的第一个 值 和 位置不匹配的元素即为答案 | |
| 18 | ⭐⭐⭐ | Medium | 矩阵 | 73/矩阵置零 | 要求O(1)空间复杂度 ，使用两个额外变量记录第一行第一列出现0的情况，其他行列出现0的情况记录在原数组的第一行第一列。 这道题有易错点，在填0的时候，索引 I 和 j 一定从 1 开始，而不是从 0 开始 | |
| 19 | ⭐⭐⭐ | Medium | 矩阵 | 54/螺旋矩阵 | 这道题很容易出错 遍历元素次数times从0开始一直到 < m*n，易错点：注意每次循环要加上 times < m * n的条件 从左到右循环遍历 从上到下循环遍历 从右到左循环遍历 从下到上循环遍历 每次循环的同时times++，循环完成后更新边界 | |
| 20 | ⭐⭐⭐ | Medium | 矩阵 | 48/旋转图像 | 要求O(1)空间复杂度，先转置（注意只要遍历右上角或者左上角即可），再翻转每一行的元素（注意遍历每行的一半即可） | |
| 21 | ⭐ | Medium | 矩阵 | 240/搜索二维矩阵II | 从右上角开始遍历矩阵 如果大于 target 就 向左寻找 如果小于 target 就 向下寻找 |
图片版：