一、哈希图
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 的位置(说明该字母区间无需再延长)