力扣-Hot100 开冲！
大约 31 分钟
算法题对于面试的重要性不言而喻
但距离我上一次刷算法题已经要追溯到2023.11.28了
是时候一改颓废，重新开始我的算法练习了😤
准备以 力扣-Hot100 为题单
一边刷题，一边对算法进行学习
对于每道题，分为三种状态：
- 没看题解就拿下
- 看了题解后拿下
- 没拿下
由于是第一遍刷，暂不考虑更优解法
也就是说自己独立写出的题，就不会看题解了
第1题 删除链表的倒数第 N 个结点
状态：没看题解就拿下data：2024.01.06tag：链表
嗯。。。只遍历了链表一遍就完成了，做的不错
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 特判，链表中仅有1个结点时
if (head.next == null) {
return null;
}
// p指向要删除的结点的前一个结点，q负责遍历整个链表
ListNode p = head, q = head.next;
int count = 2; // count用于记录p是倒数第几个结点
// 必须是 q.next，如果是 q != null，那么p可能会走到最后一位，但需要保证p一直在q前面
while (q.next != null) {
q = q.next;
count++;
if (count > n + 1) {
p = p.next;
count--;
}
}
if (count >= n + 1) delete(p, p.next);
// 只能是 count < n + 1 的情况, 且此时p指针未移动过，即要删除的是第一个结点
else head = head.next;
return head;
}
// 删除p结点后的q结点
public void delete(ListNode p, ListNode q) {
p.next = q.next;
}
}
第2题 两数之和
状态：看了题解后拿下data：2024.01.13tag：哈希
暴力解法很好想
但自己没能考虑到哈希的解法，后通过官方题解拿下了这道题
IDEA 用多了，一些常用的数据类型和方法都有点记不住拼写😭
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashTable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
// 从哈希表中查找是否有目标值
if (hashTable.containsKey(target - nums[i])) {
return new int[]{i, hashTable.get(target - nums[i])};
}
// 注意映射关系，通过值映射下标，所以键是值
hashTable.put(nums[i], i);
}
return new int[0];
}
}
注意点：
1. Map集合的 containsKey方法，用于判断 Map集合中是否包含某个指定的 key，方法返回一个 boolean类型值
如果 Map 中包含指定的 key 则返回 true，否则返回 false
2. new int[]{} 的方式给数组初始化
例：
int arr[] = {1, 2, 3};
int arr[] = new int[]{1, 2, 3};
主要是用于 return 返回，不用申明变量
第3题 字母异位词分组
状态：看了题解后拿下data：2024.01.13tag：哈希
字符串不仅仅能被哈希为一个具体的值
也可以如同这道题一样通过排序的方式进行哈希
未能找到将字符串哈希的方式是我没能做出这道题的原因
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 储存返回结果
List<List<String>> ansList = new ArrayList<List<String>>();
// 哈希表：储存字符串哈希值与字符串间映射关系
Map<String, List<String>> hashTable = new HashMap<String,List<String>>();
// 遍历字符串数组
for (int i = 0; i < strs.length; i++) {
// 获取每个字符串的哈希
String temp = hash(strs[i]);
// 将字符串与其哈希值的关系添加到哈希表中
if (hashTable.containsKey(temp)) {
List<String> list = hashTable.get(temp);
list.add(strs[i]);
}
else {
List<String> list = new ArrayList<String>();
list.add(strs[i]);
hashTable.put(temp, list);
}
}
// 遍历哈希表，将值添加到返回结果中
Set keyset = hashTable.keySet();
for (Object key : keyset) {
List<String> list = hashTable.get(key);
ansList.add(list);
}
return ansList;
}
// 哈希函数：字符串排序后的结果作为哈希值
String hash(String s) {
char[] chArr = s.toCharArray();
Arrays.sort(chArr);
String str = new String(chArr);
return str;
}
}
注意点：
1. Map 的遍历方式
2. 字符串没有 [] 的用法
3. 要对字符串进行排序，可以先通过 toCharArray() 方法将字符串转为字符数组，再通过 Arrays.sort 进行排序
第4题 盛最多水的容器
状态：看了题解后拿下data：2024.01.14tag：双指针
左右指针同时指向左右边界，然后通过左右指针向中间移动遍历整个数组，算是双指针中比较常用的方法
这道题关键点在于我到底该移动左右指针中的哪一个
因为最后所围成面积的高是两指针指向的高的最小值，那我肯定只能移动两指针中指向高更小的那一个指针（感觉还蛮好想的，为啥我没看题解的时候没想到这一点呢）
移动到哪？肯定是比其现在所指向的高更高的地方
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int max = -1;
while (i < j) {
int s = getS(i, j, height);
if (s > max) max = s;
// 移动此时两指针中height较小的指针
if (height[i] <= height[j]) {
int temp = height[i];
// 移动指针到比其原本的height更大的地方
while(i < j) {
i++;
if (height[i] > temp) break;
}
}
else {
int temp = height[j];
while (j > i) {
j--;
if (height[j] > temp) break;
}
}
}
return max;
}
// 计算左右指针所围成的面积
int getS(int i, int j, int[] height) {
int w = j - i;
int h = min(height[i], height[j]);
return w * h;
}
int min(int a, int b) {
if (a <= b) return a;
return b;
}
}
第5题 三数之和
状态：看了题解后拿下data：2024.01.15tag：双指针
通过三重循环的方式可以保证三数下标不同
for i
for j = i + 1
for k = k + 1
那该如何去重呢？
先给数组排序，此时再进行三重循环，可以去重一部分
但仍有重复的可能，遇到 [0, 1, 2, 2, 2, 3] 这种数组中存在相同数的情况，就可能枚举到重复的三元组
所以在每次枚举时，需要枚举到与上一次枚举的数不同的数
三重循环时间复杂度太高，所以通过双指针的方式去掉一重循环，这里的思路类似于 盛最多水的容器 这道题，两个指针从两端向中间移动
将 O(n^2)的时间复杂度 优化为 O(n) 算是双指针常见的用法
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 先排序
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for (int i = 0; i < nums.length - 2; i++) {
int k = nums.length - 1;
// 指针新指向的数需不同于上一个数，用于去重
if (i == 0 || nums[i] != nums[i - 1]) {
for (int j = i + 1; j < nums.length - 1; j++) {
if (j == i + 1 || nums[j] != nums[j - 1]) {
// 需保证 k 指针在 j 指针右侧
while (nums[i] + nums[j] + nums[k] > 0 && j < k)
k--;
if (j == k)
break;
if (nums[i] + nums[j] + nums[k] == 0) {
ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
}
}
}
}
return ans;
}
}
第6题 买卖股票的最佳时机
状态：没看题解就拿下data：2024.01.16tag：贪心算法
思路较为简单 假设第 i 日要卖股票，记录下在 i 日前股票的最低价，在那一天买股票即可
class Solution {
public int maxProfit(int[] prices) {
int buy = -1, max = 0;
for (int i = 0; i < prices.length; i++) {
if (i != 0 && prices[i] - buy > max) max = prices[i] - buy;
if (buy == -1 || prices[i] < buy) buy = prices[i];
}
return max;
}
}
第7题 相交链表
状态：没看题解就拿下data：2024.01.17tag：链表
做点简单题，找找自信
先遍历 a 链表，使用 set 记录每个结点
再遍历 b 链表，通过 set 查询当前结点 a 链表中是否出现
若出现，则代表 a ，b 相连接
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
Set<ListNode> set = new HashSet<ListNode>();
ListNode ans = null;
while (a != null) {
set.add(a);
a = a.next;
}
while (b != null) {
if (set.contains(b)) {
ans = b;
break;
}
b = b.next;
}
return ans;
}
}
第8题 回文链表
状态：没看题解就拿下data：2024.01.18tag：链表
利用 List 集合储存链表中的值，然后使用双指针进行回文的判断
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<Integer>();
ListNode p = head;
while (p != null) {
list.add(p.val);
p = p.next;
}
boolean ans = true;
for (int i = 0, j = list.size() - 1; i < j; i++, j--) {
if (list.get(i) != list.get(j)) {
ans = false;
break;
}
}
return ans;
}
}
第9题 环形链表
状态：没看题解就拿下data：2024.01.19tag：链表
我的思路和相交链表那道题可以说是一模一样，就不赘述了
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<ListNode>();
ListNode p = head;
boolean ans = false;
while (p != null) {
if (set.contains(p)) {
ans = true;
break;
}
set.add(p);
p = p.next;
}
return ans;
}
}
第10题 无重复字符的最长子串
状态：没看题解就拿下data：2024.01.21tag：滑动窗口
窗口内的子串保证不重复，双指针维护下标，用于判断子串长度
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
int max = 1;
Set<Character> set = new HashSet<Character>();
for (int i = 0, j = 0; j < s.length(); j++) {
char ch = s.charAt(j);
if (set.contains(ch)) {
while (s.charAt(i) != ch && i < j) {
set.remove(s.charAt(i));
i++;
}
i++;
}
else {
set.add(s.charAt(j));
if (j - i + 1 > max) max = j - i + 1;
}
}
return max;
}
}
第11题 找到字符串中所有字母异位词
状态：看了题解后拿下data：2024.01.21tag：滑动窗口
对于 p 串，利用数组记录其有哪些字母
对于 s 串，通过滑动窗口进行遍历，通过数组记录下窗口中有哪些字母
两数组相同时，则存在一个字母异位词
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<Integer>();
int sLen = s.length();
int pLen = p.length();
// s串长度小于p串则不可能存在字母异位词
if (sLen < pLen) return ans;
// sCount用于维护s串的窗口，pCount记录p串有哪些字母
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < pLen; i++) {
pCount[p.charAt(i) - 'a']++;
sCount[s.charAt(i) - 'a']++;
}
for (int i = 0, j = pLen - 1; j < sLen; j++, i++) {
if (i != 0) sCount[s.charAt(j) - 'a']++;
if (Arrays.equals(sCount, pCount)) ans.add(i);
sCount[s.charAt(i) - 'a']--;
}
return ans;
}
}
注意点：
可通过 Arrays.equals 判断两数组是否相等
第12题 最长连续序列
状态：看了题解后拿下data：2024.01.22tag：哈希
虽然官方给的 tag 是哈希，但个人感觉这道题和哈希没什么关系，因为不存在映射
整体思路是遍历数组，假设以当前遍历到的数为起点，看看能形成怎样的连续序列
利用 Set 进行了查找的优化，且假设当前数为 x ，若数组中存在 x-1 ，则该数必然不是最长连续序列的起点
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Set<Integer> set = new HashSet<Integer>();
for (int num : nums) set.add(num);
int ans = 1;
for (int num : set) {
// 大多时候会直接 continue，即O(1)
if (set.contains(num - 1)) continue;
int count = 1;
int i = num + 1;
// while仍是O(1)复杂度，最坏情况下会经历一次O(n)，但整体仍是O(1)
while (set.contains(i)) {
count++;
i++;
}
if (count > ans) ans = count;
}
return ans;
}
}
注意点：
数组也可使用增强 for 循环
第13题 和为 K 的子数组
状态：没看题解就拿下data：2024.01.24tag：子串
纯暴力解法
class Solution {
public int subarraySum(int[] nums, int k) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
int sum = nums[i];
if (sum == k) ans++;
for (int j = i + 1; j < nums.length; j++) {
sum += nums[j];
if (sum == k) ans++;
}
}
return ans;
}
}
第14题 最大子数组和
状态：没看题解就拿下data：2024.01.29tag：普通数组
遍历数组，count 维护当前子数组和，如果 count 为负数，则丢弃维护的子数组，因为维护的子数组已经无用了
class Solution {
public int maxSubArray(int[] nums) {
int count = 0;
int ans = nums[0];
for (int i = 0; i < nums.length; i++) {
count += nums[i];
if (count > ans) ans = count;
if (count < 0) count = 0;
}
return ans;
}
}
第15题 合并区间
状态：看了题解后拿下data：2024.01.30tag：普通数组
区间合并的思路很简单
但自己对于Java中的一些常用方法还不够熟练，比如sort方法中使用比较器
class Solution {
public int[][] merge(int[][] intervals) {
// 先根据区间的左端点进行升序排序
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
// 使用List集合储存合并后的区间
List<int[]> list = new ArrayList<int[]>();
// st与ed为自身维护区间
int st = intervals[0][0], ed = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
// 若区间与自身维护区间没有交集
if (intervals[i][0] > ed) {
list.add(new int[]{st, ed}); // 将自身维护区间加入到合并后区间中
st = intervals[i][0];
ed = intervals[i][1];
} else {
if (ed < intervals[i][1]) ed = intervals[i][1]; // 有交集则直接更新自身维护区间
}
}
list.add(new int[]{st, ed}); // 最后将自身维护的区间加入到合并区间中
return list.toArray(new int[list.size()][2]);
}
}
注意点：
1. sort 方法中如何使用比较器
2. 匿名内部类复习
3. list 集合通过 toArray 方法转为数组，需要预先声明数组类型及其大小
第16题 除自身以外数组的乘积
状态：看了题解后拿下data：2024.01.30tag：普通数组
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
// l[i]代表[0, i-1]的前缀乘积
int l[] = new int[length];
l[0] = 1;
// r[i]代表[i+1, length-1]的后缀乘积
int r[] = new int[length];
r[length - 1] = 1;
for (int i = 1; i < length; i++) {
l[i] = l[i - 1] * nums[i - 1];
}
for (int i = length - 2; i >= 0; i--) {
r[i] = r[i + 1] * nums[i + 1];
}
int ans[] = new int[length];
for (int i = 0; i < length; i++) ans[i] = l[i] * r[i];
return ans;
}
}
第17题 矩阵置零
状态：没看题解就拿下data：2024.01.31tag：矩阵
class Solution {
public void setZeroes(int[][] matrix) {
// 使用set记录0出现的位置，mSet记录二维数组中的第一个[]，nSet记录第二个[]
Set<Integer> mSet = new HashSet<Integer>();
Set<Integer> nSet = new HashSet<Integer>();
int n = matrix[0].length;
int m = matrix.length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
mSet.add(i);
nSet.add(j);
}
}
}
// 遍历set，为相对应位置的元素置0
for (int i : mSet) {
for (int j = 0; j < n; j++) matrix[i][j] = 0;
}
for (int j : nSet) {
for (int i = 0; i < m; i++) matrix[i][j] = 0;
}
}
}
第18题 螺旋矩阵
状态：没看题解就拿下data：2024.01.31tag：矩阵
经典🐍矩阵，上一次做这类题还是在大一，没想到现在都还记得
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int size = m * n;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int step = 0;
int x = 0, y = 0;
// 用于判断矩阵中某点是否被走过
boolean flag[][] = new boolean[m][n];
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
ans.add(matrix[x][y]);
if (i == size - 1) break;
flag[x][y] = true;
// tx，ty记录下一步移动到的坐标
int tx = x + dx[step], ty = y + dy[step];
// 若坐标合法则直接移动
if (tx >= 0 && tx < m && ty >= 0 && ty < n && !flag[tx][ty]) {
x = tx;
y = ty;
} else { // 坐标不合法则更改移动方向后再移动
step = (step + 1) % 4;
x = x + dx[step];
y = y + dy[step];
}
}
return ans;
}
}
第19题 旋转图像
状态：看了题解后拿下data：2024.02.01tag：矩阵
很无语的一道题，想用上一道🐍矩阵的方法来做
弄了半个小时没写出来
一看官方题解是用找规律的方法。。。
本来不应该用辅助矩阵的，但不想再在这道题浪费时间了，等二刷再考虑更优解吧
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int temp[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
temp[j][n - i - 1] = matrix[i][j];
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) matrix[i][j] = temp[i][j];
}
}
第20题 有效的括号
状态：看了题解后拿下data：2024.02.04tag：栈
从左向右遍历字符串，使用右括号进行匹配，可以发现越靠左的左括号越后匹配上，基于这一特性，将左括号用栈进行储存
右括号匹配时与栈顶的左括号进行匹配
class Solution {
public boolean isValid(String s) {
int length = s.length();
if (length % 2 != 0) return false;
Deque<Character> stack = new ArrayDeque<Character>();
HashMap<Character, Character> hashtable = new HashMap<Character, Character>();
// 通过哈希表快速判断当前是不是右括号，以及栈中是否有与之匹配的左括号
hashtable.put(')', '(');
hashtable.put(']', '[');
hashtable.put('}', '{');
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (hashtable.containsKey(ch)) {
// 若是右括号则与栈顶进行判断
if (stack.size() == 0 || hashtable.get(ch) != stack.pop())
return false;
} else {
stack.push(ch); // 若是左括号，则加入栈中
}
}
// 最后栈不空，则代表未完成匹配
if (stack.size() != 0) return false;
return true;
}
}
注意点：
Java 中使用栈的方式：
Deque stack = new ArrayDeque();
stack.push();
stack.pop();
stack.peek();
第21题 最小栈
状态：没看题解就拿下data：2024.02.05tag：栈
class MinStack {
Deque<Integer> stack;
Integer min;
public MinStack() {
stack = new ArrayDeque<Integer>();
}
public void push(int val) {
if (stack.size() == 0 || val < min) min = val;
stack.push(val);
}
public void pop() {
int num = stack.pop();
if (num == min) {
min = stack.peek();
for (int i : stack) {
if (i < min) min = i;
}
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
第22题 字符串解码
状态：没拿下data：2024.02.08tag：栈
这道题能恶心死我，思路倒是挺好想的，但一直有 Bug，花了一个多小时，还是没改出来，留到以后写吧
第23题 每日温度
状态：没看题解就拿下data：2024.02.08tag：栈
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length];
ans[length - 1] = 0;
for (int i = length - 2; i >= 0; i--) {
int j = i + 1;
while (j < length) {
if (temperatures[j] > temperatures[i]) {
ans[i] = j - i;
break;
}
if (ans[j] != 0) j = ans[j] + j;
else j++;
}
}
return ans;
}
}
第24题 数组中的第k个最大元素
状态：没看题解就拿下data：2024.02.09tag：堆
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
第25题 前k个高频元素
状态：看了题解后拿下data：2024.02.09tag：堆
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 使用Map映射
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// int[0]num，int[1]频率，小顶堆
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
// 遍历Map
Set<Integer> keySet = map.keySet();
for (Integer key : keySet) {
Integer val = map.get(key);
// 这段注释的是我的写法，感觉思路和题解是一样的，但过不了检测
// if (queue.size() < k) {
// queue.offer(new int[]{key, val});
// }
// if (queue.size() == k) {
// if (val > queue.peek()[1]) {
// queue.poll();
// queue.offer(new int[]{key, val});
// }
// }
// 堆已满k个元素，则将当前遍历到的元素的频率与堆顶元素频率进行比较
if (queue.size() == k) {
if (queue.peek()[1] < val) { // 如果大于，则弹出堆顶，将当前元素入堆
queue.poll();
queue.offer(new int[]{key, val});
}
} else {
queue.offer(new int[]{key, val});
}
}
// 返回答案
int[] ans = new int[k];
for (int i = 0; i < k; ++i) {
ans[i] = queue.poll()[0];
}
return ans;
}
}
注意点：
Java 中使用堆的方式
PriorityQueue queue = new PriorityQueue();
可传入比较器，用于指定大顶堆还是小顶堆
poll() 弹出堆顶
offer() 将元素加入堆
第26题 二叉树的中序遍历
状态：没看题解就拿下data：2024.02.11tag：二叉树
今天进入二叉树的练习
class Solution {
private List<Integer> ans;
public List<Integer> inorderTraversal(TreeNode root) {
ans = new ArrayList<Integer>();
inOrder(root);
return ans;
}
void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
ans.add(node.val);
inOrder(node.right);
}
}
第27题 二叉树的最大深度
状态：没看题解就拿下data：2024.02.11tag：二叉树
class Solution {
int maxDeep = 1;
public int maxDepth(TreeNode root) {
if (root == null) return 0;
preOrder(root, 1);
return maxDeep;
}
// 遍历二叉树的时候维护以下深度即可
void preOrder(TreeNode node, int deep) {
if (node == null) return;
if (deep > maxDeep) maxDeep = deep;
preOrder(node.left, deep + 1);
preOrder(node.right, deep + 1);
}
}
第28题 翻转二叉树
状态：没看题解就拿下data：2024.02.11tag：二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
PostOrder(root);
return root;
}
void PostOrder(TreeNode node) {
if (node == null) return;
PostOrder(node.left);
PostOrder(node.right);
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
}
第29题 对称二叉树
状态：看了题解后拿下data：2024.02.11tag：二叉树
可以将该问题理解为判断对称位置上的子树是否是镜像的
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root.left, root.right);
}
boolean check(TreeNode left, TreeNode right) {
// 对称位置都为空，满足对称
if (left == null && right == null) return true;
// 对称位置一边为空，不对称
if (left == null || right == null) return false;
// 对称位置都不为空
// 则判断当前位置的值是否相等，并通过递归对相应对称位置进行判断
return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
}
}
第30题 二叉树的直径
状态：看了题解后拿下data：2024.02.11tag：二叉树
class Solution {
int maxLength;
public int diameterOfBinaryTree(TreeNode root) {
maxLength = 0;
getMaxDeep(root);
return maxLength;
}
// 返回以node为根结点的树的深度
int getMaxDeep(TreeNode node) {
if (node == null) return 0;
// 左子树的深度
int L = getMaxDeep(node.left);
// 右子树的深度
int R = getMaxDeep(node.right);
// 左右子树的深度加起来就是以node为根结点的树的直径
if (L + R > maxLength) maxLength = L + R;
// 当前树的深度为左右子树的较大深度加上1
return Math.max(L, R) + 1;
}
}
注意点：
对递归使用的一点理解：
1. 明确递归函数是要解决一个什么样的问题，例如该题：返回以 node 为根结点的树的深度。
2. 递归函数要解决该问题，需要解决一些子问题，要解决的子问题仍满足递归函数要解决的问题，所以可以通过调用递归函数来解决，以此来实现递归。
例如该题：需要求得左右子树的深度，而左右子树的深度仍可通过递归函数来解决。
3. 上述两点可以简单理解为：将大问题不断地划分为小问题。
划分到足够小时，小问题可不通过递归函数即可解决，例如该题：node 为 null 时直接返回0。
第31题 二叉树的层序遍历
状态：看了题解后拿下data：2024.02.13tag：二叉树
该题需要根据层数返回遍历结果，关键点就在于确定队列中的元素处于那一层
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
// 先将根节点加入队列
queue.offer(root);
// 每一次循环取出队列中所有元素
while (!queue.isEmpty()) {
int length = queue.size();
// 用于储存当前层的元素
List<Integer> level = new ArrayList<Integer>();
// 进入循环前队列里的所有元素就是某层的所有元素
for (int i = 0; i < length; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
ret.add(level);
}
return ret;
}
}
第32题 将有序数组转换为二叉搜索树
状态：看了题解后拿下data：2024.02.13tag：二叉树
题目给定数组为升序排序，可以理解为二叉搜索树的中序遍历
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
TreeNode helper(int[] nums, int L, int R) {
if (L > R) return null;
// 选择中间结点或是中间两个结点中偏左的作为根结点
int mid = (L + R) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, L, mid - 1);
root.right = helper(nums, mid + 1, R);
return root;
}
}
第33题 验证二叉搜索树
状态：看了题解后拿下data：2024.02.16tag：二叉树
题解这种根据区间比较值的方法真是妙啊。
class Solution {
boolean helper(TreeNode node, Long low, Long up) {
if (node == null) return true;
if (node.val <= low || node.val >= up) return false;
return helper(node.left, low, Long.valueOf(node.val)) && helper(node.right, Long.valueOf(node.val), up);
}
public boolean isValidBST(TreeNode root) {
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
第34题 二叉搜索树中第k小的元素
状态：没看题解就拿下data：2024.02.16tag：二叉树
class Solution {
List<Integer> list;
void helper(TreeNode node) {
if (node == null) return;
helper(node.left);
list.add(node.val);
helper(node.right);
}
public int kthSmallest(TreeNode root, int k) {
list = new ArrayList<Integer>();
helper(root);
return list.get(k - 1);
}
}
第35题 二叉树的右视图
状态：看了题解后拿下data：2024.02.16tag：二叉树
通过 dfs 遍历二叉树，越靠右的结点，越晚被遍历到，本题就是基于此来做。
class Solution {
private List<Integer> ret;
private void dfs(TreeNode node, int deep) {
if (node == null) return;
if (deep > ret.size()) ret.add(node.val);
else ret.set(deep - 1, node.val);
dfs(node.left, deep + 1);
dfs(node.right, deep + 1);
}
public List<Integer> rightSideView(TreeNode root) {
ret = new ArrayList<Integer>();
if (root == null) return ret;
dfs(root, 1);
return ret;
}
}
第36题 二叉树展开为链表
状态：看了题解后拿下data：2024.02.17tag：二叉树
class Solution {
public void flatten(TreeNode root) {
while (root != null) {
// 1.先找到当前树的左子树的最右边结点
// 左子树不存在，直接进入下一次循环
if (root.left == null) {
root = root.right;
continue;
} else {
// 记录左子树的最右结点
TreeNode pre = root.left;
while (pre.right != null) pre = pre.right;
// 2.将当前树的右子树拼接到左子树最右结点的右边
pre.right = root.right;
// 3.将当前树左子树转为当前树的右子树
root.right = root.left;
// 4.将当前树的左子树置为空
root.left = null;
root = root.right;
}
}
}
}
第37题 从前序与中序遍历序列构造二叉树
状态：看了题解后拿下data：2024.02.17tag：二叉树
class Solution {
Map<Integer, Integer> map = new HashMap<>();
private TreeNode helper(int[] preorder, int[] inorder, int preSt, int preEd, int inSt, int inEd) {
if (preSt > preEd) return null;
// 1.前序遍历的第一个结点为根结点，先建立根结点
TreeNode root = new TreeNode(preorder[preSt]);
// 2.找到中序遍历中根结点的位置
int val = map.get(preorder[preSt]);
// 3.递归得到左子树
root.left = helper(preorder, inorder, preSt + 1, val - inSt + preSt, inSt, val - 1);
// 4.递归得到右子树
root.right = helper(preorder, inorder, val - inSt + preSt + 1, preEd, val + 1, inEd);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
int length = inorder.length;
for (int i = 0; i < length; i++) map.put(inorder[i], i);
return helper(preorder, inorder, 0, length - 1, 0, length - 1);
}
}
第38题 路径总和 III
状态：没看题解就拿下data：2024.02.19tag：二叉树
class Solution {
private int ret = 0;
// int会爆，使用long
private void helper(TreeNode node, int targetSum, long sum) {
if (node == null) return;
sum += node.val;
if (sum == targetSum) ret++;
// 即便找到了一条路径，也要继续往下找
helper(node.left, targetSum, sum);
helper(node.right, targetSum, sum);
}
private void preOrder(TreeNode node, int targetSum) {
if (node == null) return;
helper(node, targetSum, 0);
preOrder(node.left, targetSum);
preOrder(node.right, targetSum);
}
public int pathSum(TreeNode root, int targetSum) {
preOrder(root, targetSum);
return ret;
}
}
注意点
看到给的数据最大值为 10^9 的时候，就要考虑使用 long 了。
因为 int 储存的最大值 2147483647，加两次就爆掉了。
第39题 二叉树的最近公共祖先
状态：看了题解后拿下data：2024.02.19tag：二叉树
最近公共祖先分为两种情况：
1. 最近公共祖先为 p 或 q 本身
2. 最近公共祖先不为 p 或 q，则 p 或 q 位于最近公共祖先的两侧
class Solution {
// 探寻公共祖先所在的子树
private TreeNode helper(TreeNode node, TreeNode p, TreeNode q) {
// node为空直接返回，用于回溯
// node为p或q，也直接返回，公共祖先必在p或q所在的子树上
if (node == null || node == p || node == q) return node;
// 从左子树搜索
TreeNode left = helper(node.left, p, q);
// 从右子树搜索
TreeNode right = helper(node.right, p, q);
// 灵魂之处，左子树搜索后，未遇到p或q结点，一直搜索到了叶子结点，则公共祖先必在右子树
if (left == null) return right;
if (right == null) return left; // 同理
return node;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return helper(root, p, q);
}
}
第40题 搜索二维矩阵
状态：没看题解就拿下data：2024.02.20tag：二分
class Solution {
private boolean helper(int[] nums, int target) {
int L = -1, R = nums.length;
while (L + 1 < R) {
int M = (L + R) / 2;
if (nums[M] < target) L = M;
else R = M;
}
if (R == nums.length || nums[R] != target) return false;
return true;
}
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
if (i > 0 && matrix[i][0] > target) return helper(matrix[i - 1], target);
}
return helper(matrix[matrix.length - 1], target);
}
}
第41题 搜索选择排序数组
状态：没看题解就拿下data：2024.02.20tag：二分
class Solution {
private int helper(int[] nums, int target, int st, int ed) {
int L = st - 1;
int R = ed + 1;
while (L + 1 < R) {
int M = (L + R) / 2;
if (nums[M] < target) L = M;
else R = M;
}
if (R == ed + 1 || nums[R] != target) return -1;
return R;
}
public int search(int[] nums, int target) {
int temp = -1;
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] < nums[i - 1]) {
temp = helper(nums, target, 0, i - 1);
if (temp != -1) return temp;
temp = helper(nums, target, i, nums.length - 1);
break;
}
// 旋转后，数组仍保持升序
if (i == nums.length - 1) temp = helper(nums, target, 0, nums.length - 1);
}
return temp;
}
}
第42题 寻找旋转排序数组中的最小值
状态：看了题解后拿下data：2024.02.20tag：二分
class Solution {
public int findMin(int[] nums) {
int length = nums.length;
int L = -1, R = length;
int temp = nums[length - 1];
while (L + 1 < R) {
int M = (L + R) / 2;
if (nums[M] > temp) L = M;
else R = M;
}
if (R == length) return nums[0];
return nums[R];
}
}
第43题 随机链表的复制
状态：看了题解后拿下data：2024.02.21tag：链表
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node, Node> hashTable = new HashMap<>();
// 1.首先深拷贝所有结点的值，并利用哈希表进行记录
Node cur = head;
while (cur != null) {
hashTable.put(cur, new Node(cur.val));
cur = cur.next;
}
// 2.给每个结点的next与random赋值
cur = head;
while (cur != null) {
Node node = hashTable.get(cur);
node.next = hashTable.get(cur.next);
node.random = hashTable.get(cur.random);
cur = cur.next;
}
return hashTable.get(head);
}
}
第44题 LRU 缓存
状态：看了题解后拿下data：2024.02.21tag：链表
头都写大了
class LRUCache {
// 手写双向链表，头部储存最近用过的关键字，尾部储存最近未使用的
class DlinkedNode {
public int key;
public int val;
public DlinkedNode next;
public DlinkedNode pre;
public DlinkedNode() {}
public DlinkedNode(int key, int val) {
this.key = key;
this.val = val;
}
}
private int capacity;
private int size;
private DlinkedNode head;
private DlinkedNode tail;
private Map<Integer, DlinkedNode> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
size = 0;
// 建立虚拟头尾结点，这样在进行头尾结点操作时不必判断头尾结点是否存在
head = new DlinkedNode();
tail = new DlinkedNode();
head.next = tail;
tail.pre = head;
cache = new HashMap<>();
}
public int get(int key) {
DlinkedNode node = cache.get(key);
if (node == null) return -1;
// 移动至头部
moveToHead(node);
return node.val;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
DlinkedNode node = cache.get(key);
node.val = value;
moveToHead(node);
} else {
DlinkedNode node = new DlinkedNode(key, value);
// 添加至头部
addToHead(node);
cache.put(key, node);
// 数量加1
size++;
}
if (size > capacity) {
// 删除尾结点
DlinkedNode node = removeTail();
cache.remove(node.key);
size--;
}
}
private void addToHead(DlinkedNode node) {
node.next = head.next;
head.next.pre = node;
head.next = node;
node.pre = head;
}
private void removeNode(DlinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void moveToHead(DlinkedNode node) {
removeNode(node);
addToHead(node);
}
private DlinkedNode removeTail() {
DlinkedNode node = tail.pre;
removeNode(node);
return node;
}
}
第45题 两数相加
状态：看了题解后拿下data：2024.02.21tag：链表
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
// 长度小的一个链表，将其后续位数看作0
while (l1 != null || l2 != null) {
int a = l1 == null ? 0 : l1.val;
int b = l2 == null ? 0 : l2.val;
int sum = a + b + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
}
第46题 子集
状态：看了题解后拿下data：2024.02.22tag：回溯
class Solution {
private List<Integer> t;
private List<List<Integer>> ans;
public List<List<Integer>> subsets(int[] nums) {
t = new ArrayList<>();
ans = new ArrayList<>();
dfs(0, nums);
return ans;
}
private void dfs(int cur, int[] nums) {
if (cur == nums.length) {
ans.add(new ArrayList<Integer>(t));
return;
}
// 选择当前位置
t.add(nums[cur]);
dfs(cur + 1, nums);
// 不选择当前位置
t.remove(t.size() - 1);
dfs(cur + 1, nums);
}
}
第47题 电话号码的字母组合
状态：没看题解就拿下data：2024.02.22tag：回溯
久违的靠自己 AC 了
class Solution {
private StringBuilder t = new StringBuilder();
private Map<Integer, String> map = new HashMap<>();
private List<String> ans = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return ans;
map.put(2, "abc");
map.put(3, "def");
map.put(4, "ghi");
map.put(5, "jkl");
map.put(6, "mno");
map.put(7, "pqrs");
map.put(8, "tuv");
map.put(9, "wxyz");
dfs(0, digits);
return ans;
}
private void dfs(int cur, String digits) {
if (cur == digits.length()) {
ans.add(t.toString());
return;
}
String str = map.get(digits.charAt(cur) - '0');
for (int i = 0; i < str.length(); i++) {
t.append(str.charAt(i));
dfs(cur + 1, digits);
t.delete(cur, cur + 1);
}
}
}
第48题 杨辉三角
状态：没看题解就拿下data：2024.02.25tag：动态规划
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();
ans.add(new ArrayList<Integer>(Arrays.asList(1)));
if (numRows == 1) return ans;
ans.add(new ArrayList<Integer>(Arrays.asList(1, 1)));
for (int i = 2; i < numRows; i++) {
List<Integer> t = new ArrayList<>();
List<Integer> preList = ans.get(i - 1);
for (int j = 0; j <= i; j++) {
int temp = 0;
if (j > 0) temp += preList.get(j - 1);
if (j < i) temp += preList.get(j);
t.add(temp);
}
ans.add(t);
}
return ans;
}
}
第49题 多数元素
状态：看了题解后拿下data：2024.02.25tag：技巧
数组任意两个不同的数进行抵消后，新数组中众数仍然不变
class Solution {
public int majorityElement(int[] nums) {
int count = 0, ans = nums[0];
for (int num : nums) {
if (count == 0) ans = num;
count += (ans == num ? 1 : -1);
}
return ans;
}
}
第50题 岛屿数量
状态：看了题解后拿下data：2024.03.02tag：图论
class Solution {
private int[] dx = {0, 1, 0, -1};
private int[] dy = {1, 0, -1 ,0};
int n;
int m;
public int numIslands(char[][] grid) {
n = grid.length;
m = grid[0].length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '0' || grid[i][j] == '2') continue;
dfs(grid, i, j);
count++;
}
}
return count;
}
private void dfs(char[][] grid, int x, int y) {
if (x >= n || x < 0 || y >= m || y < 0) return;
if (grid[x][y] == '0' || grid[x][y] == '2') return;
// 将已遍历过的陆地的值设为2
grid[x][y] = '2';
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
dfs(grid, xx, yy);
}
}
}
第51题 腐烂的橘子
状态：看了题解后拿下data：2024.03.06tag：图论
class Solution {
public int orangesRotting(int[][] grid) {
int n = grid.length, m = grid[0].length;
int count = 0, time = 0;
Queue<int[]> queue = new LinkedList<>();
// 1.找出最初腐烂的橘子加入队列
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 2) queue.offer(new int[]{i, j});
// 记录下新鲜橘子数
if (grid[i][j] == 1) count++;
}
}
// 2.利用 bfs 遍历
while (count > 0 && !queue.isEmpty()) {
time++;
// 一次取出一层
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] org = queue.poll();
int x = org[0], y = org[1];
// 传染新鲜橘子
// 右
if (y + 1 < m && grid[x][y + 1] == 1) {
grid[x][y + 1] = 2;
count--;
queue.offer(new int[]{x, y + 1});
}
// 下
if (x + 1 < n && grid[x + 1][y] == 1) {
grid[x + 1][y] = 2;
count--;
queue.offer(new int[]{x + 1, y});
}
// 左
if (y - 1 >= 0 && grid[x][y - 1] == 1) {
grid[x][y - 1] = 2;
count--;
queue.offer(new int[]{x, y - 1});
}
// 上
if (x - 1 >= 0 && grid[x - 1][y] == 1) {
grid[x - 1][y] = 2;
count--;
queue.offer(new int[]{x - 1, y});
}
}
}
if (count == 0) return time;
return -1;
}
}
第52题 课程表
状态：看了题解后拿下data：2024.03.06tag：图论
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 记录每门课程的入度
int[] inDegree = new int[numCourses];
// key 记录前置课，value 记录依赖于该前置课的课程
Map<Integer, List<Integer>> hashTable = new HashMap<>();
Queue<Integer> queue = new LinkedList<>();
// 初始化
for (int i = 0; i < prerequisites.length; i++) {
int a = prerequisites[i][0], b = prerequisites[i][1];
inDegree[a]++;
if (hashTable.containsKey(b)) {
List<Integer> list = hashTable.get(b);
list.add(a);
} else {
List<Integer> list = new ArrayList<>(Arrays.asList(a));
hashTable.put(b, list);
}
}
// 入度为0的结点入队
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
int count = numCourses;
// bfs 遍历
while (!queue.isEmpty()) {
int course = queue.poll();
count--;
if (!hashTable.containsKey(course)) continue;
// 减少后置结点的入度
List<Integer> list = hashTable.get(course);
int n = list.size();
for (int i = 0; i < n; i++) {
int temp = list.get(i);
inDegree[temp]--;
if (inDegree[temp] == 0) {
// 入度减为0则入队
queue.offer(temp);
}
}
}
if (count == 0) return true;
return false;
}
}
第53题 实现前缀树
状态：看了题解后拿下data：2024.03.08tag：图论
class Trie {
private Trie[] next;
private boolean isEnd;
public Trie() {
next = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for(int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (node.next[ch - 'a'] == null) node.next[ch - 'a'] = new Trie();
node = node.next[ch - 'a'];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = this;
for(int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (node.next[ch - 'a'] == null) return false;
node = node.next[ch - 'a'];
}
if (node.isEnd == true) return true;
return false;
}
public boolean startsWith(String prefix) {
Trie node = this;
for(int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
if (node.next[ch - 'a'] == null) return false;
node = node.next[ch - 'a'];
}
return true;
}
}