2022-11-06 16:33:36
最近在复盘前面学的东西，然后顺便刷刷题，总之不能闲着…
想读书，想学嵌入式，想一个人出去旅行，想一个人去看电影，想做的事情都好多，可时间真的好少，而且放在当下时间节点的优先级也不算高
2024-11-3 14:21:15
历史竟是惊人的相似，而且时间段也很接近，最近有点想跳槽，没想到两年前我已经写过这篇文章了，那么继续更新吧。
仔细一看，之前的题解还是太稚嫩了，顺带手重构一遍吧
嵌入式已经学了一点点了哦 现在是想专心跳槽
哈希
两数之和
暴力枚举
- 思路：两层循环，找出相加之和为target的两个下标
- 复杂度分析：时间复杂度O(n^2)，空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
int x = nums[i];
int y = nums[j];
if (x + y == target) {
return new int[]{i, j};
}
}
}
}
return new int[]{};
}
}
|
哈希表
- 分析一下这个问题，目的是找出
x + y = target，那么 x = target - y，那么问题就转化为在数组中找出 target - y，如果存在，则返回，否则返回空数组。
- 那么我们可以先对数字建一个哈希表，随后对于每一个数字x，我们在哈希表中寻找
target - x，如果存在，则返回，否则返回空数组。
- 需要注意的一点是，两个数字的下标不能一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int y = target - nums[i];
if (map.get(y) != null && i != map.get(y)) {
return new int[]{i, map.get(y)};
}
}
return new int[]{};
}
}
|
字母异位词分组
排序
- 对于每一个str，我们对其排序，如果是异位词，那么排序后的结果理应也是一样的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<Integer>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
String str = strs[i];
char[] chars = str.toCharArray();
Arrays.sort(chars);
String sortedStr = Arrays.toString(chars);
if (map.get(sortedStr) != null) {
List<Integer> indexList = map.get(sortedStr);
indexList.add(i);
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
map.put(sortedStr, list);
}
}
ArrayList<List<String>> res = new ArrayList<>();
for (Map.Entry<String, List<Integer>> entry : map.entrySet()) {
ArrayList<String> list = new ArrayList<>();
entry.getValue().forEach(idx -> list.add(strs[idx]));
res.add(list);
}
return res;
}
}
|
- 上述代码仍存在优化空间，map的value其实可以直接存储字符串，不必存索引，再取出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String key = new String(charArray);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(str);
map.put(key, list);
}
return new ArrayList<>(map.values());
}
}
|
最长连续序列
- 我寻思这题双指针做，不是超级简单吗？为什么会出现在哈希里呢？只可惜排序是时间复杂度O(nlogn)的。
双指针
- 第一遍敲的代码，有个测试用例没过，
[0, 1, 1, 2]，这种东西里的0 1 2是连续的，但是排序后会多个1，那岂不是left++就好了吗
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.util.Arrays;
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int left = 0;
int right = 1;
int maxLen = 0;
while (right < nums.length) {
if (nums[right] - nums[right - 1] == 1) {
right++;
} else {
maxLen = Math.max(maxLen, right - left);
left = Math.max(++right - 1, 0);
}
}
return Math.max(maxLen, right - left);
}
public static void main(String[] args) {
int[] nums = {1,2,0,1};
Solution solution = new Solution();
System.out.println(solution.longestConsecutive(nums));
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int left = 0;
int right = 1;
int maxLen = 0;
while (right < nums.length) {
if (nums[right] - nums[right - 1] == 1) {
right++;
}
else if (nums[right] - nums[right - 1] == 0) {
right++;
left++;
}
else {
maxLen = Math.max(maxLen, right - left);
left = Math.max(++right - 1, 0);
}
}
return Math.max(maxLen, right - left);
}
}
|
哈希表
- 对于任意一个数字
num，我们判断num-1是否在哈希表里，如果在，那么说明num和num - 1是连续的，继续判断num - 1 - 1是否还在哈希表里，最终不满足条件退出循环。但下面这个超时了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| import java.util.HashSet;
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (Integer num : set) {
int curLen = 1;
while (set.contains(--num)) {
curLen++;
}
maxLen = Math.max(maxLen, curLen);
}
return maxLen;
}
}
|
- 我们把刚刚的逻辑反过来，对于一个
num，我们判断如果set集合中不存在num - 1，那么num是这个连续序列的起点，我们判断num++是否在集合中就好了，这个可以通过测试用例，但是仅击败87.42%，没有我的双指针快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (Integer num : set) {
if (!set.contains(num - 1)) {
int curLen = 1;
while (set.contains(++num)) {
curLen++;
}
maxLen = Math.max(maxLen, curLen);
}
}
return maxLen;
}
}
|
-
接下来我们来分析一下为什么方法一会超时，而方法二不会超时。
-
在方法一中，我们是将每一个数都当做是可能的连续序列的终点，随后向前遍历。
-
在方法二中，我们是将每一个数都当做是可能的连续序列的起点，随后向后遍历。
-
这里简单举一个例子：[1, 2, 3, 4, 5]
-
在这个例子中，如果使用方法一：
- 遍历到1的时候，会计算
1 - 1是否在集合中。
- 遍历到2的时候，会就按
2 - 1, 2 - 2是否在结合中、。
- …
-
如果使用方法二：
- 遍历到1的时候，
1 - 1不在集合中，那么1是最长连续序列的起点。我们自增判断接下来的每一个元素是否在集合中
- 遍历到2的时候，
2 - 1在集合中，跳过。
-
复杂度分析
- 方法一：由于可能在一个序列内重复访问数字，最坏情况下的时间复杂度接近 O(n^2)。
- 方法二：这种方法在每个数字上只做常数次的查找，整体时间复杂度为 O(n)。
双指针
移动零
双指针
- 一开始没注意到要保持非零元素的相对顺序，这个代码双指针是一前一后，向中心靠拢，但是这样的话，非零元素的相对顺序会变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
if (nums[right] == 0) {
right--;
}
int num = nums[left];
if (num == 0) {
swap(left, right, nums);
}
left++;
}
}
public void swap(int left, int right, int[] nums) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
|
- 那我们让两个指针都从最左边开始走就好了，但是这个代码也有一个问题，遇到两个连续的0，二者交换没有意义，同时left还在自增，所以会有问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right = 0;
while (++right < nums.length) {
if (nums[left] != 0) {
left++;
}
if (nums[left] == 0) {
swap(left++, right, nums);
}
}
}
public void swap(int left, int right, int[] nums) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right = 0;
while (++right < nums.length) {
if (nums[left] != 0) {
left++;
}
if (nums[left] == 0 && nums[right] != 0) {
swap(left++, right, nums);
}
}
}
public void swap(int left, int right, int[] nums) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
|
盛最多水的容器
暴力
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
for (int i = 0; i < height.length - 1; i++) {
for (int j = i + 1; j < height.length; j++) {
maxArea = Math.max(maxArea, Math.min(height[i], height[j]) * (j - i));
}
}
return maxArea;
}
}
|
双指针
- 现在分析一下这个问题，如何才能让装的水最多呢？那当然是两边足够高，并且离得远，那么
height x width的面积就是最大的。
- 那我们用双指针，一个从左边开始遍历，一个从右边开始遍历，遍历的时候需要单调递增，即高变长了，但是宽变窄了，那么最终的面积可能才会变大。
- 单调递增意味着，我们需要每次移动短的那条边，才可能找到一条更长的边。
- 那我们按照自己的思路来试一试到底可不可行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
int h = Math.min(height[left], height[right]);
maxArea = Math.max(h * (right - left), maxArea);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
|
三数之和
暴力
接雨水
滑动窗口
无重复字符的最长子串
滑动窗口
-
首先，为了简化后续处理，我们可以排除字符串长度小于等于1的特殊情况。此时，无重复字符的子串长度等于字符串本身的长度。
-
然后，定义一个Set用于存储当前无重复字符的窗口。在扩展右边界时，首先检查右边界字符是否已经存在于Set中。如果已存在，说明出现了重复字符，我们需要逐步移除左边界的字符，直到不再有重复。每次将新的右边界字符加入Set后，我们更新最大子串长度。
-
这个算法的核心就在于，每次移动右边界时，确保以当前右边界字符结尾的子串都是无重复的最大长度子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
import java.util.HashSet;
import java.util.Set;
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] charArray = s.toCharArray();
if (charArray.length <= 1) {
return charArray.length;
}
int maxLen = 0;
int left = 0, right = 0;
Set<Character> set = new HashSet<>();
while (right < charArray.length) {
while (set.contains(charArray[right])) {
set.remove(charArray[left]);
left++;
}
set.add(charArray[right]);
right++;
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
}
|
找到字符串中所有字母异位词
子串
和为 K 的子数组
前缀和 + 哈希
- 首先我们来了解一下前缀和的概念：
- 对于数组中的任意位置
i，前缀和pre[i]表示数组中的第1个元素到第i个元素的总和。
- 前缀和
pre[j]表示数组中的第1个元素到第j个元素的总和。
- 假定
j > i，那么pre[j] - pre[i]就是第i+1个元素到第j个元素的总和。
- 那么对于这个问题，我们可以转化为：求解两个前缀和之差等于k的情况。
- 通过遍历数组，计算每个位置的前缀和，同时使用一个哈希表来存储每个前缀和出现的次数，同时在遍历数组的过程中，我们判断哈希表中是否存在
prefix[j] - k的前缀和，并累加其出现次数，即为结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0;
int prefixSum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int num : nums) {
prefixSum = prefixSum + num;
if (map.containsKey(prefixSum - k)) {
res += map.get(prefixSum - k);
}
map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
}
return res;
}
}
|
滑动窗口最大值
双端队列
- 我们可以使用双端队列（Deque）来解决这个问题。
- 维护双端队列：
- 用Deque存放元素的索引。在任何时刻，Deque的头部总是滑动窗口中的最大值的索引。那么当窗口滑动时，我们只取Deque的头部即可获取最大值。
- 滑动窗口滑动：
移除窗口最左侧的元素：如果Deque头部元素的索引已经超出当前窗口的范围（即j - k + 1之前的元素），那么从头部移除该元素。维护单调递减性：将当前元素和Deque尾部元素比较，如果当前元素比尾部元素大，那么尾部元素不可能是当前滑动窗口的最大值，那我们移除尾部元素。重复此操作，直至Deque中的所有元素都大于当前元素，即可保持单调递减。添加当前元素：将当前元素的索引加入Deque。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
LinkedList<Integer> deque = new LinkedList<>();
for (int j = 0; j < nums.length; j++) {
if (!deque.isEmpty() && deque.getFirst() < j - k + 1) {
deque.removeFirst();
}
while (!deque.isEmpty() && nums[deque.getLast()] < nums[j]) {
deque.removeLast();
}
deque.addLast(j);
if (j >= k - 1) {
res[j - k + 1] = nums[deque.getFirst()];
}
}
return res;
}
}
|
最小覆盖子串
滑动窗口+双指针
- 需求计数：对于字符串t，我们建立一个targetMap，存储每个字母出现的次数。便于我们判断子串s中是否包含t中所有字母。
- 滑动窗口：我们使用双指针表示滑动窗口的左右边界，通过调整right扩大窗口直至满足条件为止，随后通过移动left指针缩小窗口范围，找到最小的满足条件的子串。
- 计数匹配：使用一个windowMap来存储窗口内所有字符出现的次数，当windowMap中的每个字符数都满足targrtMap时，窗口就满足条件。
- 记录最小窗口：在满足条件时，记录最小窗口大小和对应的起始索引。如果找到更小的窗口则更新记录。
- 返回结果：循环结束后，返回记录的最小窗口字符串，如果没有符合条件的子串则返回空字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return "";
}
HashMap<Character, Integer> targetMap = new HashMap<>();
for (char c : t.toCharArray()) {
targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0, matchCount = 0, startIndex = 0;
int minLength = Integer.MAX_VALUE;
HashMap<Character, Integer> windowMap = new HashMap<>();
while (right < s.length()) {
char c = s.charAt(right);
if (targetMap.containsKey(c)) {
windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
if (windowMap.get(c).intValue() == targetMap.get(c).intValue()) {
matchCount++;
}
}
right++;
while (matchCount == targetMap.size()) {
if (right - left < minLength) {
minLength = right - left;
startIndex = left;
}
char d = s.charAt(left);
if (targetMap.containsKey(d)) {
if (windowMap.get(d).intValue() == targetMap.get(d).intValue()) {
matchCount--;
}
windowMap.put(d, windowMap.get(d) - 1);
}
left++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(startIndex, startIndex + minLength);
}
}
|
普通数组
最大子数组和
动态规划
- 经典的动态规划问题，状态转移方程：
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
}
Arrays.sort(dp);
return dp[dp.length-1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int curMaxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
curMaxSum = Math.max(curMaxSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, curMaxSum);
}
return maxSum;
}
}
|
合并区间
排序+遍历合并
- 排序：首先将区间按照起始位置
start升序排序。这样可以保证当遍历到某个区间时，之前区间的起始位置都小于等于当前区间的起始位置。
- 遍历合并：
- 用一个
merged列表来保存合并后的区间。
- 对于当前区间
intervals[i]
- 如果
merged为空，或者当前区间起始位置大于megerd中的最后一个区间的结束位置，说明它们之间没有重叠，可以直接将当前区间添加到merged中。
- 否则，他们重叠，我们将
merged中的最后一个区间的结束为止更新为当前区间的结束位置。
- 返回结果：
merged列表中即为合并后的区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
LinkedList<int[]> merged = new LinkedList<>();
for (int[] interval : intervals) {
if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
merged.add(interval);
} else {
merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}
}
|
轮转数组
除自身以外数组的乘积
难绷
- 感觉这道题出的几乎没有什么意义，没营养。
- 除自身以外数组的乘积，如果用除法，那么计算所有数的乘积，再除以当前数，那么就是结果。
- 但是题目要求不能使用除法，那么只能用乘法。但乘法也一样啊，只不过不用乘以当前数了，计算一个前缀积和后缀积，二者相乘即为结果。本质上就是除法把分子和分母约了，想不出这题有什么意义。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
int[] prefixArray = new int[nums.length + 1];
prefixArray[0] = 1;
int[] suffixArray = new int[nums.length + 1];
suffixArray[nums.length] = 1;
for (int i = 1; i < nums.length + 1; i++) {
prefixArray[i] = nums[i - 1] * prefixArray[i - 1];
}
for (int i = nums.length - 1; i >= 0; i--) {
suffixArray[i] = nums[i] * suffixArray[i + 1];
}
for (int i = 0; i < nums.length; i++) {
res[i] = prefixArray[i] * suffixArray[i + 1];
}
return res;
}
}
|
1
2
3
4
5
6
| class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
}
}
|
缺失的第一个正数
矩阵
矩阵置零
螺旋矩阵
旋转图像
搜索二维矩阵 II
链表
相交链表
反转链表
回文链表
环形链表
环形链表 II
合并两个有序链表
两数相加
删除链表的倒数第 N 个结点
两两交换链表中的节点
K 个一组翻转链表
随机链表的复制
排序链表
合并 K 个升序链表
LRU 缓存
二叉树
二叉树的中序遍历
二叉树的最大深度
翻转二叉树
对称二叉树
二叉树的直径
二叉树的层序遍历
将有序数组转换为二叉搜索树
验证二叉搜索树
二叉搜索树中第 K 小的元素
二叉树的右视图
二叉树展开为链表
从前序与中序遍历序列构造二叉树
路径总和 III
二叉树的最近公共祖先
二叉树中的最大路径和
图论
岛屿数量
腐烂的橘子
课程表
实现 Trie (前缀树)
回溯
全排列
子集
电话号码的字母组合
组合总和
括号生成
单词搜索
分割回文串
N 皇后
二分查找
搜索插入位置
搜索二维矩阵
在排序数组中查找元素的第一个和最后一个位置
搜索旋转排序数组
寻找旋转排序数组中的最小值
寻找两个正序数组的中位数
栈
有效的括号
最小栈
字符串解码
每日温度
柱状图中最大的矩形
堆
数组中的第K个最大元素
前 K 个高频元素
数据流的中位数
贪心算法
买卖股票的最佳时机
跳跃游戏
跳跃游戏 II
划分字母区间
动态规划
爬楼梯
杨辉三角
打家劫舍
完全平方数
零钱兑换
单词拆分
最长递增子序列
乘积最大子数组
分割等和子集
最长有效括号
多维动态规划
不同路径
最小路径和
最长回文子串
最长公共子序列
编辑距离
技巧
只出现一次的数字
多数元素
颜色分类
下一个排列
寻找重复数
