摘要
简单记录力扣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 left = 0, max = 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 + 1 - left) > max) {
max = right + 1 - left;
}
}
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
26
27
28
| public List<Integer> findAnagrams(String s, String p) {
if (p.length() > s.length()) {
return new ArrayList<>();
}
//创建两个容器，用来存放各字母出现的频次
List<Integer> list = new ArrayList<>();
int[] pa = new int[26];
int[] sa = new int[26];
//初始化字符串p的字母频次，以及字符串s的初始滑动窗口的字母频次
for (int i = 0; i < p.length(); i++) {
pa[p.charAt(i) - 'a']++;
sa[s.charAt(i) - 'a']++;
}
//移动滑动窗口，滑动窗口移动的次数为s.length-p.length+1
for (int left = 0; left <= s.length() - p.length(); left++) {
//a b c d e
//移除滑动窗口第一个值，也就是下标为left-1。引入滑动后的下一个值，也就是下标为left-1+p.length。初始的滑动窗口不需要再次赋值了
if (left != 0) {
sa[s.charAt(left - 1) - 'a']--;
sa[s.charAt(left - 1 + p.length()) - 'a']++;
}
//若两个数组相等，则记录起始索引
if (Arrays.equals(pa, sa)) {
list.add(left);
}
}
return list;
}
|
四、子串
核心思路：
- 暴力解法，T=O(n²)。每个元素依次和后面的元素累加，记录和为k的次数。时间复杂度为
- 前缀和解法，T=O(n)。可以通过计算前缀和来解决该问题，有两种情况均满足条件，如下
- 两个位置的前缀和的差为k
- 某个位置的前缀和为k
前缀和的原理其实我还没弄明白，不知道为啥要这样写，虽然答案是对的。
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(n²)：超时
- 优先队列解法，T=O(nlogn)：比暴力解法略优。优先队列支持通过自定义排序的方式，
int compare(Integer o1, Integer o2)前-后=从小到大，后-前=从大到小。 - 双向队列解法：本质思路与优先队列类似，只是借用了双向队列存储依次存储值下标，并保证在队列中的值都是随着下标增大单调递减的，这样取最大值只需要取第一个即可。
优先队列解法
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
| public int[] maxSlidingWindow(int[] nums, int k) {
if (k > nums.length) {
return new int[0];
}
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((o1, o2) -> {
//使用优先队列存储。数组下标0存储值，数组下标1存储值对应的下标
//若值相等，就按照索引由小到大排序。若值不等，就按照值从大到小排序
return o2[0] != o1[0] ? o2[0] - o1[0] : o1[1] - o2[1];
});
//首先计算出滑动窗口需要移动的次数, 即nums.length-k+1
int[] ints = new int[nums.length - k + 1];
//先将第一组放入，并获取第一组的最大值
for (int i = 0; i < k; i++) {
priorityQueue.add(new int[]{nums[i], i});
}
ints[0] = priorityQueue.peek()[0];
//从第二组开始计算
for (int left = 1; left < ints.length; left++) {
//将滑窗右侧的值加入
priorityQueue.add(new int[]{nums[left + k - 1], left + k - 1});
//若最大值的索引在左窗索引的左边，就进行移除
while (priorityQueue.peek()[1] < left) {
priorityQueue.poll();
}
ints[left] = priorityQueue.peek()[0];
}
return ints;
}
|
单调队列解法：
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
| public int[] maxSlidingWindow(int[] nums, int k) {
if (k > nums.length) {
return new int[0];
}
//首先计算出滑动窗口需要移动的次数, 即nums.length-k+1
int[] ints = new int[nums.length - k + 1];
//使用双向队列来记录数组下标
Deque<Integer> deque = new LinkedList<>();
//先计算第一组的最大值
for (int i = 0; i < k; i++) {
//该操作是为了保证单调递减的值才会存入到队列中，所以只要取第一个即可获取到最大值
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.addLast(i);
}
ints[0] = nums[deque.peekFirst()];
//由第二组开始
for (int left = 1; left < ints.length; left++) {
//该操作是为了保证单调递减的值才会存入到队列中，所以只要取第一个即可获取到最大值
while (!deque.isEmpty() && nums[left + k - 1] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.addLast(left + k - 1);
//判断最大值的坐标是否在滑窗左边界以左，若是则移除
while (deque.peekFirst() < left) {
deque.pollFirst();
}
ints[left] = nums[deque.peekFirst()];
}
return ints;
}
|
五、普通数组
六、矩阵
七、链表
八、二叉树
九、图论
十、回溯
十一、二分查找
十二、栈
十三、堆
