摘要
简单记录力扣100题解题思路
正文
LeetCode 热题 100 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
一、哈希
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new LinkedHashMap<>();
for (int i = 0; i < nums.length; i++) {
int value = target - nums[i];
if (map.containsKey(value)) {
return new int[]{
map.get(value),
i
};
} else {
map.put(nums[i], i);
}
}
return new int[0];
}
|
核心做法：将字符串转为char数组然后排序，再将排序后char数组转为字符串。通过哈希判断即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = Arrays.toString(chars);
if (map.containsKey(key)) {
map.get(key).add(str);
} else {
List<String> temp = new ArrayList<>();
temp.add(str);
map.put(key, temp);
}
}
return new ArrayList<>(map.values());
}
|
这个其实没有用到哈希相关的知识，直接暴力for就是最好的解法！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int longestConsecutive(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
Arrays.sort(nums);
int max = 1, sum = 1;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
continue;
}
if (nums[i + 1] - nums[i] == 1) {
if (++sum > max) {
max = sum;
}
} else {
sum = 1;
}
}
return max;
}
|
二、指针
核心思路：设置index指针，将非0值与index值进行交换，之后index++。这里面有个妙处，就是值全不为0时。
1
2
3
4
5
6
7
8
9
10
| public void moveZeroes(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int num = nums[index];
nums[index++] = nums[i];
nums[i] = num;
}
}
}
|
核心思路：
若向内 移动短板 ，水槽的短板可能变大，因此下个水槽的面积 可能增大 。
若向内 移动长板 ，水槽的短板不变或变小，因此下个水槽的面积 一定变小 。
故应向内移动短板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int maxArea(int[] height) {
int leftIndex = 0, rightIndex = height.length - 1, max = 0;
for (int i = 0; i < height.length; i++) {
int area = Math.min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex);
if (area > max) {
max = area;
}
if (height[leftIndex] > height[rightIndex]) {
rightIndex--;
} else {
leftIndex++;
}
}
return max;
}
|
要点：
- nums[i]+nums[j]+nums[k]==0
- i!=j!=k
- 三元组的顺序不重要，但三元组结果集中数据不可重复
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
| public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = -nums[i];
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重复元素
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (target > sum) {
left++;
} else {
right--;
}
}
}
return list;
}
|
核心思路：计算每个单位积水值，然后求和。在获取每个单位积水值的时候，需要知道该单位左侧和右侧的最大值，方能知道能否积水。
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
| public int trap(int[] height) {
int sum = 0;
// 获取每个下标的左侧最大值
int[] leftMax = new int[height.length];
for (int i = 0; i < height.length; i++) {
if (i == 0) {
leftMax[i] = 0;
} else {
leftMax[i] = Math.max(height[i - 1], leftMax[i - 1]);
}
}
// 获取每个下标的右侧最大值
int[] rightMax = new int[height.length];
for (int i = height.length - 1; i >= 0; i--) {
if (i == height.length - 1) {
rightMax[i] = 0;
} else {
rightMax[i] = Math.max(height[i + 1], rightMax[i + 1]);
}
}
// 依次计算每个小标的积水，并求总和
for (int i = 0; i < height.length; i++) {
int area = Math.min(leftMax[i], rightMax[i]) - height[i];
if (area > 0) {
sum += area;
}
}
return sum;
}
|
三、滑动窗口
核心思路：设置一个容器，将所有不重复的字符存入。当发现新来的字符重复时，就把第一个该字符及其前面字符移除掉。最蠢的办法，就是设置一个List，然后对List进行截取。但该容器的本质是需要维护一个左右可滑动窗口，所以List只是容器的很麻烦的一种实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) {
return s.length();
}
int max = 0, left = 0;
char[] chars = s.toCharArray();
for (int right = 1; right < chars.length; right++) {
// 维护一个滑动窗口，右侧新来的值，依次跟滑动窗口中的值进行比较
int index = left;
while (index < right) {
if (chars[index] == chars[right]) {
left = index + 1;
}
++index;
}
if ((right - left + 1) > max) {
max = right - left + 1;
}
}
return max;
}
|
核心思路：控制一个长度固定的滑动窗口，依次向前滑动，并将值排序后与排序后的 p 进行比较。这算是最简单直观的暴力解法了。排序在数据量大时，性能会特别低，其实也不需要关心 p 串中的字符顺序，只关心其中各字母出现的频次，频次一样就是字母异位词
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
| public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
if (s.length() < p.length()) {
return list;
}
// 最多只有26个字母，用数组来表示滑动窗口
int[] sa = new int[26];
int[] pa = new int[26];
for (int i = 0; i < p.length(); i++) {
pa[p.charAt(i) - 'a']++;
sa[s.charAt(i) - 'a']++;
}
// 定长滑动窗口，每次左侧指针移动一次，若不匹配，则将数组的最左侧移除
for (int left = 0; left <= s.length() - p.length(); left++) {
if (left != 0) {
sa[s.charAt(left + p.length() - 1) - 'a']++;
}
if (Arrays.equals(pa, sa)) {
list.add(left);
}
sa[s.charAt(left) - 'a']--;
}
return list;
}
|
四、子串
核心思路：
- 暴力解法，T=O(n²)。每个元素依次和后面的元素累加，记录和为k的次数。
- 前缀和解法，T=O(n)。可以通过计算前缀和来解决该问题
- 前缀和定义：
prefixSum[i] = nums[0] + nums[1] + ... + nums[i] - 任意子数组
[j+1 ... i] 的和：sum(j, i) = prefixSum[i] - prefixSum[j]
暴力解法
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static int subarraySum(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
int total = 0, index = i;
while (index < nums.length) {
total += nums[index++];
if (total == k) {
sum++;
}
}
}
return sum;
}
|
前缀和解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int subarraySum(int[] nums, int k) {
int sum = 0, prefixSum = 0;
//前缀和:该和出现的次数
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
prefixSum += nums[i];
if (prefixSum == k) {
sum++;
}
sum += map.getOrDefault(prefixSum - k, 0);
map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
}
return sum;
}
|
核心思路
- 暴力解法，T=O(nk)：超时
- 优先队列解法，T=O(nlogn)：比暴力解法略优。优先队列支持通过自定义排序的方式，
int compare(Integer o1, Integer o2)前-后=从小到大，后-前=从大到小。 - 双端队列解法，T=O(n)：双端队列，新增元素时，依次对比队列尾部，若原尾部小，就踢掉。如此就能实现队首始终最大值
优先队列解法
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
| public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length < k) {
return new int[0];
}
int[] arr = new int[nums.length - k + 1];
// 使用一个自排序的优先队列。队列存储数组 int[]{值, 下标}
// 值相同，按下标升序；否则，按值降序
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
});
for (int i = 0; i < nums.length - k + 1; i++) {
if (i != 0) {
pq.add(new int[]{nums[i + k - 1], i + k - 1});
// 保证队首的元素在滑动窗口内
while (pq.peek()[1] < i) {
pq.poll();
}
} else {
for (int j = 0; j < k; j++) {
pq.add(new int[]{nums[j], j});
}
}
arr[i] = pq.peek()[0];
}
return arr;
}
|
单调队列解法：
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
| public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length < k) {
return new int[0];
}
int[] arr = new int[nums.length - k + 1];
// 双端队列，新增元素时，依次对比队列尾部，若原尾部小，就踢掉
// 如此就能实现队首始终最大值
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length - k + 1; i++) {
if (i == 0) {
for (int j = 0; j < k; j++) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[j]) {
deque.pollLast();
}
deque.offerLast(j);
}
} else {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i + k - 1]) {
deque.pollLast();
}
deque.offerLast(i + k - 1);
}
while (!deque.isEmpty() && deque.peekFirst() < i) {
deque.pollFirst();
}
arr[i] = nums[deque.peekFirst()];
}
return arr;
}
|
双指针，右边一直扩，直到满足条件，左边开始缩，缩到刚好不满足，再继续右扩
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
| public String minWindow(String s, String t) {
// 没有明确说明只有小写或者大写，所以字符范围直接 ASCII 字符（大小写字母、数字、符号），也就是128
int[] sa = new int[128];
int[] ta = new int[128];
for (char c : t.toCharArray()) {
ta[c]++;
}
// 右边一直扩 → 直到满足条件 → 左边开始缩 → 缩到刚好不满足 → 再继续右扩
int left = 0, right = 0, required = t.length();
int minLenStart = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
char rc = s.charAt(right);
if (ta[rc] > 0) {
sa[rc]++;
if (sa[rc] <= ta[rc]) {
required--;
}
}
while (required == 0) {
if (minLen > right - left + 1) {
// 匹配到当前的最小值了，记录下来
minLen = right - left + 1;
minLenStart = left;
}
char lc = s.charAt(left);
if (ta[lc] > 0) {
sa[lc]--;
if (sa[lc] < ta[lc]) {
required++;
}
}
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLenStart, minLenStart + minLen);
}
|
五、普通数组
