AlgorithmClassification2

算法分类2

双指针

160. 相交链表

还有检查链表的环

3. 无重复字符的最长子串

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
// 滑动窗口
// 使用set判断无重复
public int lengthOfLongestSubstring(String s) {
int ans = 0;
Set<Character> set = new HashSet<Character>();

int left = 0;

for (int right=0; right<s.length(); right++) {
while (left <= right && set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
ans = Math.max(right - left + 1, ans);
}

return ans;
}
}

11. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
// 使用双指针,每一次移动height较小的那个指针
// 因为如果移动大的,高度变小,长度也变小,肯定不会有更大的出现
public int maxArea(int[] height) {
int left = 0, right = height.length-1;
int ans = 0;

while (left < right) {
ans = Math.max(Math.min(height[left], height[right]) * (right - left), ans);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}

return ans;
}
}

15. 三数之和

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 {
// 确定一个数的情况下,另外两个可以用双指针
// 一个从i+1,一个从n-1开始,根据三数之和判断谁移动
// 由于不能重复,所以需要判断第一个和第二个的重复性
// 保证第一第二,就能保证第三个不重复
public List<List<Integer>> threeSum(int[] nums) {
// 先需要给数组排序
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();

for (int i=0; i<nums.length; i++) {
if (i > 0 && nums[i] == nums[i-1]) { continue; } // 重复跳过
int j = i+1, k = nums.length - 1;

while(j < k) {
// 注意,每个元素自己不能重复,两个-1这样是可以的
while (j > i+1 && j < k && nums[j] == nums[j-1]) { j++; } // j重复的也跳过
if (j >= k) { break; }
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
list.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}

return list;
}
}

16. 最接近的三数之和

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 threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = nums[0] + nums[1] + nums[2];

for (int i=0; i<nums.length; i++) {
int j = i + 1, k = nums.length - 1;

while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
ans = Math.abs(target - ans) > Math.abs(target - sum) ? sum : ans;

if (sum == target) {
return ans;
} else if (sum < target) {
j++;
} else {
k--;
}
}
}

return ans;
}
}

二分

主要的特点是

  • 升序排列,不论是一个数组还是两个数组。
  • 时间复杂度O(log(m)), O(log(m+n))之类的

二分需要注意很多等号,左右边,等等的细节

33. 搜索旋转排序数组

由于中位数是(n+m)/2或者(n+m)/2和(n+m)/2+1的均值,所以,可以将此题目,看作是第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
35
36
37
/**
* O(logn),二分查找
* 此处数组不是完全有序的
* 但是,两段分别有序,而且有一个关键点,后面一段有序的,全部小于等于nums[0]
* 第一段有序的,也都是大于等于nums[0]
*/
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;

// 后面有很多nums[0]跟别的的判断,所以此处先是直接判断nums[0]是否等于target
if (nums[0] == target) { return 0; }

while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
} else {
if (nums[0] > nums[mid]) { // nums[mid]在后面一段
if (nums[mid] < target && target <= nums[nums.length - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else { // mid在前面一段
if (nums[0] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
}

return -1;
}
}

81. 搜索旋转排序数组 II

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
/**
* O(logn),二分查找
* 此处数组不是完全有序的
* 但是,两段分别有序,而且有一个关键点,后面一段有序的,全部小于等于nums[0]
* 第一段有序的,也都是大于等于nums[0]
*/
class Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;

// 后面有很多nums[0]跟别的的判断,所以此处先是直接判断nums[0]是否等于target
if (nums[0] == target) { return true; }

while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return true;
}

// 此处与前面那个的区别是,若left和mid和right都相等,那么判断不了是在哪个区见
// 所以,将left和right各自缩短,然后用新的区间去判断,所以nums[0]都要编程nums[lefts]
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
} else if (nums[left] > nums[mid]) { // nums[mid]在后面一段
if (nums[mid] < target && target <= nums[nums.length - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else { // mid在前面一段
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}

return false;
}
}

153. 寻找旋转排序数组中的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int findMin(int[] nums) {
// 看最后一个,如果mid大于最后,那么那么是第一段有序的,需要到右边去
int left = 0, right = nums.length - 1, len = nums.length;

while (left <= right) {
int mid = left + ((right - left) >> 1);

// 等号,就是判断了,数组只有一个的情况
if (nums[mid] <= nums[len - 1]) {
right = mid - 1;
} else {
left = mid + 1;
}
}

// 使用这个,注意left是会有等于nums.length的边界问题的
return nums[left];
}
}

154. 寻找旋转排序数组中的最小值 II

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
class Solution {
// 包含重复元素
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1, len = nums.length - 1;

while (left <= right) {
int mid = left + ((right - left) >> 1);

// 注意此处只要每次是与numsright比就好了
// 注意此处比较的时候出来的问题, 每次跟最后那个len比,最后那个是需要变化的
if (nums[mid] == nums[len]) {
right -= 1; // 如果相等,那么把最后的一位移到前面即可
len = right;
} else if (nums[mid] > nums[len]) {
left = mid + 1;
} else {
right = mid - 1;
len = mid;
}
}

// 注意,每次用left和right的时候都要考虑下出界问题
return nums[left];
}
}

34. 在排序数组中查找元素的第一个和最后一个位置

请非常关注里面的细节

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
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) { return new int[]{-1, -1}; }
int[] ans = new int[2];
int left = 0, right = nums.length - 1;

while (left <= right) {
int mid = left + ((right - left) >> 1);
// 如果相等的话,需要right往左走
// 所以此处再加上nums[mid] >= target
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}

// 非常注意,像上面有等号的,最终都会left+right,所以left可能为最大长度出界,而right可能为-1出界
if (left == nums.length || nums[left] != target) {
return new int[]{-1, -1};
}
ans[0] = left;


left = 0;
right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

if (right == -1 || nums[right] != target) {
return new int[]{-1, -1};
}
ans[1] = right;

return ans;
}
}

1818. 绝对差值和

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 int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
// 每一次,都需要找到离nums2[i]最近的nums1中的数
// 如何找,使用二分

long sum = 0;
// sum直接每一次的绝对值差相加,所以此处要找到多减去的最多的
long duoJianQuMax = 0;
int[] sortedNums1 = nums1.clone();
Arrays.sort(sortedNums1);

for (int i=0; i< sortedNums1.length; i++) {
int a = nums1[i], b = nums2[i]; // 注意此处还是nums1
if (a == b) { // 注意相等
continue;
}
int x = Math.abs(a - b);
sum += x;

int left = 0, right = sortedNums1.length - 1;
while (left <= right) {
int mid = (left + ((right - left) >> 1));
if (sortedNums1[mid] <= b) {
left = mid + 1;
} else {
right = mid - 1;
}
}

int c = Integer.MAX_VALUE; // 注意取最小值
if (left != sortedNums1.length) {
c = Math.abs(b - sortedNums1[left]);
}
if (right != -1) {
c = Math.min(Math.abs(b - sortedNums1[right]), c);
}

if (c < x) {
duoJianQuMax = Math.max(duoJianQuMax, x - c);
}
}

return (int)((sum - duoJianQuMax) % (1e9+7));
}
}

35. 搜索插入位置

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
46
47
48
49
50
// 注意,记忆这一个,简单一点
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length-1;

// 返回第一个>=target的
while(left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
left = mid; // 因为最终left是结果,所以直接这样了,当然此处return mid也是可以的
break;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}

// 因为while中使用的是<=,所以在不是等于的情况下,最终形态left = right + 1
// 即,nums[right] < target < nums[left],所以要插入的位置就是在left处
// 因为left初始化是0,所以插入0的位置也是可以的(right=-1);插入nums.length也是可以的,right没动过的情况下。
return left;
}
}

// 同样的代码
// 只不过可能不同的理解而已
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;

// 返回将会被插入的位置
// 此处没有重复元素,当然有重复元素也能做,看34.
while (left <= right) {
int mid = left + ((right - left) >> 1);

if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}

// left最后得到的范围是0~nums.length
// 所以说,最小的话,正好插在最开始,最大的话,正好加载最末尾
return left;
}
}

74. 搜索二维矩阵

240. 搜索二维矩阵 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean searchMatrix(int[][] matrix, int target) {
// 根据该特性,可以使用二分,看作二叉搜索树实现
int row = 0, col = matrix[0].length - 1;

while (true) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col -= 1;
if (col < 0) {
break;
}
} else {
row += 1;
if (row >= matrix.length) {
break;
}
}
}

return false;
}

滑动窗口

连续子数组

  1. 如果子数组的函数计算,是要小于(等于)某个东西,没有重复等等,那么可以使用经典滑动窗口,每一次移动一次right,然后left的移动看是否满足条件就可以。

  2. 而如果像LeetCode 395,子数组所有的字符出现次数大于等于(不少于k次)。也就是说,一开始最小的数组是不满足的,就不像我上面的每次right移动一次,left看条件。

    所以,但是好像也不能每次动left,然后把right移动到满足条件那样,因为不知道何时是头,一旦满足,但是后面还有满足的呢?

    那么,可以尝试加一些限制条件,变成经典滑动窗口。比如:①395,加字符种类限制;②先把一些加上,然后变成0;③然后比如,题目说去除某个子数组之后,是否满足xxx,那么可以反过来看这个子数组自身的情况。

也可以看看宫水三叶说的,二段性质两个指针,一个左移的时候往一个方向变,右移的时候往另一个方向变,应该就能用。那这样的话,我上面说的第二点,可能遇到二段性质的也能用?

ZLYpN8hUb7FRaTy

713. 乘积小于 K 的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
// 滑动窗口
// 每一次枚举右端点,然后看左端点啥时候不满足
int mul = 1, ans = 0;
int n = nums.length, left = 0;

for (int right=0; right<n; right++) {
mul *= nums[right]; // 每一次枚举一下右端点

while (left <= right && mul >= k) { // 右端点加1之后,如果有超过,那么左边+1,直到满足条件
mul /= nums[left];
left++;
}

ans += right - left + 1; // left和right都算在内
}

return ans;
}
}

395. 至少有 K 个重复字符的最长子串

dwSMovplrn4Vc8m

wIPN8D41frX5nTE

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 int longestSubstring(String s, int k) {
// 滑动窗口,但是该滑动窗口不满足二段性质,因为次数都要大于等于
// 所以增加性质,1~26个字符的限制,那么每一次都是要小于等于该字符种类,满足
char[] chars = s.toCharArray();
int n = chars.length;
int ans = 0;

// 对每一次的种类个数,进行滑动窗口
for (int p = 1; p <= 26; p++) {

int left = 0;
int zhonglei = 0; // 目前字符种类个数
int kZhonglei = 0; // 目前达到k次的字符种类个数
int[] nums = new int[26]; // 26个字符的个数统计

for (int right = 0; right < n; right++) {
int index = chars[right] - 'a';
nums[index] += 1;
if (nums[index] == 1) { zhonglei += 1; } // 多一个种类
if (nums[index] == k) { kZhonglei += 1; }

while (left < right && zhonglei > p) {
int tempIndex = chars[left] - 'a';
nums[tempIndex] -= 1;
if (nums[tempIndex] == 0) {
zhonglei -= 1;
}
if (nums[tempIndex] == k - 1) {
kZhonglei -= 1;
}
left += 1;
}

// 上面弄下来,会满足zhobnglei这个变量是在p个数内的
// 然后我下面只要判断里面的所有种类都是出现了至少k次的就行了
if (kZhonglei == zhonglei) {
ans = Math.max(ans, right - left + 1);
}
}
}

return ans;
}
}

1178. 猜字谜

【宫水三叶】详解「朴素位运算」& 「哈希表位运算」,以完整的优化分析思路

1208. 尽可能使字符串相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int n = Math.min(s.length(), t.length()), left = 0;
int ans = 0, cost = 0;

// 枚举right,找到最先满足的最小left
for (int right = 0; right < n; right++) {
cost += Math.abs(s.charAt(right) - t.charAt(right));
while (left <= right && cost > maxCost) {
cost -= Math.abs(s.charAt(left) - t.charAt(left));
left++;
}

ans = Math.max(ans, right - left + 1);
}

return ans;
}
}

1423. 可获得的最大点数

2024. 考试的最大困扰度

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
class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
int n = answerKey.length();

int left = 0, changeNum = 0, ans = 0;

// 'T'变'F'
for (int right = 0; right < n; right++) { // right变后可能不满足
if (answerKey.charAt(right) == 'T') {
changeNum++;
}

while (left <= right && changeNum > k) { // 找到满足的最小left
if (answerKey.charAt(left) == 'T') {
changeNum--;
}
left++;
}

ans = Math.max(ans, right - left + 1);
}

changeNum = 0; left = 0;
// 'F'变'T'
for (int right = 0; right < n; right++) { // right变后可能不满足
if (answerKey.charAt(right) == 'F') {
changeNum++;
}

while (left <= right && changeNum > k) { // 找到满足的最小left
if (answerKey.charAt(left) == 'F') {
changeNum--;
}
left++;
}

ans = Math.max(ans, right - left + 1);
}

return ans;
}
}

1423. 可获得的最大点数

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
// 注意两点,left和right都是算在内的
// 一开始while的时候,left<=right,然后先判断,再对left+1,因为一开始的left是算在内的
class Solution {
public int characterReplacement(String s, int k) {
int ans = 0;

for (int m = 0; m<26; m++) {
int left = 0;
int changeCount = 0;

for (int right = 0; right < s.length(); right++) {
if (s.charAt(right) != m + 'A') {
changeCount++;
}
while (left <= right && changeCount > k) { // 找到能满足的最小的left,
if (s.charAt(left) != m + 'A') {
changeCount--;
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
}

return ans;
}
}

1052. 爱生气的书店老板

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
class Solution {
// 先把所有没生气的顾客都加上,然后对应的customers[i]都变为0
// 然后滑动窗口为minute的,看哪一个最大,这个就不用延伸minute两边了
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int ans = 0;
for (int i=0; i<customers.length; i++) {
if (grumpy[i] == 0) {
ans += customers[i];
customers[i] = 0;
}
}

int sum = 0, nextAns = 0, left = 0;
for (int right = 0; right < customers.length; right++) {
sum += customers[right];

while (right - left > minutes-1) {
sum -= customers[left];
left += 1;
}
nextAns = Math.max(sum, nextAns);
}

return ans + nextAns;
}
}

480. 滑动窗口中位数

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
46
47
48
49
50
51
52
53
54
55
56
class Solution {
/**
使用滑动窗口 + 优先队列
优先队列的话,由于中位数,k是偶数的时候可能需要两个,所以使用两个优先队列
一个存在小的一半,一份存放大的一半
由于可能k为基数,所以可以让left多一个,然后每次都跟left这个队列比较
*/
public double[] medianSlidingWindow(int[] nums, int k) {
Queue<Integer> left = new PriorityQueue<Integer>((x, y) -> (Integer.compare(x, y)));
Queue<Integer> right = new PriorityQueue<Integer>((x, y) -> (Integer.compare(y, x)));

// right是从大到小的,left是从小到大的
for (int i=0; i<k; i++) {
left.offer(nums[i]);
}
for (int i=0; i<k/2; i++) { // right可能比left少1,所以后面每次跟left比较
right.offer(left.poll());
}

double[] ans = new double[nums.length - k + 1];
ans[0] = getMid(k, left, right);
// left存放的是大的那一半,从小到大
// right存放的是小的那一半,从大到小
for (int i=k; i<nums.length; i++) { // 滑动窗口开始滑动
int add = nums[i], del = nums[i-k];
if (add >= left.peek()) {
left.offer(add);
} else {
right.offer(add);
}
if (del >= left.peek()) {
left.remove(del); // 注意这个删除是O(n)级别的
} else {
right.remove(del);
}

adjust(left, right);
ans[i - k + 1] = getMid(k, left, right);
}

return ans;
}

public void adjust(Queue<Integer> left, Queue<Integer> right) { // 每次调整两个队列的个数
while (right.size() > left.size()) { left.offer(right.poll()); }
while (left.size() - 1 > right.size()) { right.offer(left.poll()); }
}

public double getMid(int k, Queue<Integer> left, Queue<Integer> right) {
if (k % 2 == 0) {
return left.peek() * 1.0 / 2 + right.peek() * 1.0 / 2; // 防止溢出
} else {
return left.peek() * 1.0;
}
}
}

剑指 Offer II 016. 不含重复字符的最长子字符串

注意

这个set不能重复,那么可以用map的值来记录个数,这个思想要记住。

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 lengthOfLongestSubstring(String s) {
// 滑动窗口,此处用set好像不太行啊,只能用hashmap记录个数了
int ans = 0;
int left = 0;
// Set<Character> set = new HashSet<>();
Map<Character, Integer> map = new HashMap<>();

for (int right = 0; right<s.length(); right++) {
char c = s.charAt(right);
map.put(c, map.getOrDefault(c, 0) + 1);

while (left <= right && map.get(c) > 1) {
char temp = s.charAt(left);
map.put(temp, map.getOrDefault(temp, 0) - 1);
left += 1;
}

ans = Math.max(right - left + 1, ans);
}

return ans;
}
}

图论

【拓扑排序】图论拓扑排序入门

拓扑排序,有向图的安全节点,环,或者看到每一次都有两两比较的结果的。

在图论中,一个有向无环图,必然存在至少一个拓扑序与之对应,反之亦然。

能得到 某个有向无环图的拓扑序 前提是 必然能找到(至少)一个入度为0的点,使用BFS,在起始时将其入队。

851. 喧闹和富有

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
46
47
48
/**
* 此处考虑使用拓扑排序
* 有钱的指向钱少的,然后每一次更新被指向的那个节点的ans,更新的是和指向的节点的ans比小的
* 因为指向的的人前比那个人多,所以被指向的ans要么自己和所有邻居的ans中的最小的
* 当然也可以使用dfs(没钱指向有钱),递归更新ans
*/
class Solution {
public int[] loudAndRich(int[][] richer, int[] quiet) {
// 使用邻接表
List<Integer>[] list = new List[quiet.length];
int[] inDe = new int[quiet.length];

for (int i = 0; i < quiet.length; i++) {
list[i] = new ArrayList<>();
}

for (int i = 0; i < richer.length; i++) {
list[richer[i][0]].add(richer[i][1]);
inDe[richer[i][1]] += 1;
}

Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < inDe.length; i++) {
if (inDe[i] == 0) {
queue.offerLast(i);
}
}

int[] ans = new int[quiet.length];
for (int i = 0; i < quiet.length; i++) {
ans[i] = i; // 初始化每一个person的答案是自己,最大的那个(没有等号),答案肯定是自己吧?
}

while (!queue.isEmpty()) {
int x = queue.pollFirst();
for (Integer y : list[x]) { // 此处x比y有钱,所以更新y的quiet
if (quiet[ans[y]] > quiet[ans[x]]) {
ans[y] = ans[x];
}
if (--inDe[y] == 0) {
queue.offerLast(y);
}
}
}

return ans;
}
}

链表

链表模版

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
/**
* 两数相加
*
* @author jcwang
*/
public class TemplateLianbiao{
public static void main(String[] args) {
Solution solution = new TemplateLianbiao().new Solution();
}

public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public ListNode solve(ListNode l) {
return new ListNode();
}
}
//leetcode submit region end(Prohibit modification and deletion)
}

2. 两数相加

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
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = l1, pre = null;

int carry = 0;
int value1 = 0;
while (l1 != null && l2 != null) {
value1 = l1.val + l2.val + carry;
l1.val = value1 % 10;
carry = value1 / 10;
pre = l1;
l1 = l1.next;
l2 = l2.next;
}

if (l2 != null) {
pre.next = l2;

while (l2 != null) {
value1 = l2.val + carry;
l2.val = value1 % 10;
carry = value1 / 10;
pre = l2;
l2 = l2.next;
}
} else if (l1 != null) {
while (l1 != null) {
value1 = l1.val + carry;
l1.val = value1 % 10;
carry = value1 / 10;
pre = l1;
l1 = l1.next;
}
}
// 两个都没有了
if (carry == 1) {
pre.next = new ListNode(1);
}

return head;
}
}

19. 删除链表的倒数第 N 个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 使用哑节点
ListNode dummy = new ListNode(0, head);
ListNode right = head, left = dummy;

for (int i=0; i<n; i++) {
// 链表长度小于n
if (right == null) {
return head;
}
right = right.next;
}

while (right != null) {
right = right.next;
left = left.next;
}
left.next = left.next.next;

return dummy.next;
}
}

23. 合并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
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode();
ListNode pre = dummy;

// 每一次选择最k个链表中最小的一个进行穿针,使用priorityqueue实现
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((t1, t2) -> (t1.val - t2.val));
for (ListNode node: lists) {
if (node != null) {
queue.offer(node);
}
}

while (!queue.isEmpty()) {
ListNode node = queue.poll();
pre.next = node;
if (node.next != null) {
queue.offer(node.next);
}
pre = pre.next;
}

return dummy.next;
}
}

24. 两两交换链表中的节点

206. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public ListNode reverseList(ListNode head) {
// 注意此处的prev不要指向head,会出先环的,直接为null就好
ListNode prev = null;
ListNode cur = head;

while(cur != null) {
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}

return prev;
}
}

61. 旋转链表

先将链表闭合上,然后找到其中的点给他断开,然后考虑特殊情况。

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 ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {
return head;
}
int n = 1;
ListNode iter = head;
while (iter.next != null) {
iter = iter.next;
n++;
}
int add = n - k % n;
if (add == n) {
return head;
}
iter.next = head;
while (add-- > 0) {
iter = iter.next;
}
ListNode ret = iter.next;
iter.next = null;
return ret;
}
}

或者跟之前一样先找到最后第k个,然后进行操作。

83. 删除排序链表中的重复元素

注意一下,删除的算法中,基本上都是,else的时候pre才会往后面移动的。

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 ListNode deleteDuplicates(ListNode head) {
// 不需要用到前一个节点的索引,直接用head.next.next
// ListNode prev = head;
// 注意head可能本身为null的情况
if (head == null) return null;

ListNode start = head;

// 此处是head与head.next比较,所以要判断head.next是否非空
while(head.next != null) {
if (head.val == head.next.val) {
head.next = head.next.next;
} else {
head = head.next;
}
}

return start;
}
}

82. 删除排序链表中的重复元素 II

注意一下,删除的算法中,基本上都是,else的时候pre才会往后面移动的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// 由于第一个节点可能会被删除,所以需要用一个哑节点
ListNode dummyNode = new ListNode(-1, head);

ListNode node = dummyNode;
while (node.next != null && node.next.next != null) {
if (node.next.val == node.next.next.val) {
int x = node.next.val; // 用x暂时记录相等的值
while (node.next != null && node.next.val == x) {
node.next = node.next.next;
}
} else {
node = node.next;
}
}

return dummyNode.next;
}
}

92. 反转链表 II

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
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == right) return head;

ListNode preLeftNode = null, preRight = null, cur = head;
for (int i=0; i<left-2; i++) {
cur = cur.next;
}
preLeftNode = left == 1 ? null : cur; // left左边一个

cur = left == 1 ? cur : cur.next; // 第left个
ListNode leftNode = cur;
ListNode tempNext = cur.next;

for (int i=left; i<right; i++) {
ListNode temp = tempNext.next;
tempNext.next = cur;
cur = tempNext;
tempNext = temp;
}

// tempNext是right后面的一个节点
if (preLeftNode == null) head = cur;
else preLeftNode.next = cur;
leftNode.next = tempNext;

return head;
}
}

138. 复制带随机指针的链表

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public Node copyRandomList(Node head) {
// 先全部复制一遍,放在每个节点的后面,再将random节点指上去,然后拆开
if (head == null) { return null; }

Node start = head;

// 复制
while (head != null) {
Node node = new Node(head.val);
node.next = head.next;
head.next = node;

head = head.next.next;
}

// 复制随机指针
head = start;
while (head != null) {
if (head.random != null) {
head.next.random = head.random.next;
}

head = head.next.next;
}

// 拆开
head = start;
Node ans = head.next;
while (head != null) {
Node temp = head.next;

head.next = head.next.next;
if (head.next != null) {
temp.next = head.next.next;
}

head = head.next;
}

return ans;
}
}
// 第二个方法有点秀的
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
Node cur = head;
HashMap<Node,Node> map = new HashMap<>();
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur=head;
while(cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}

160. 相交链表

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
// 使用双指针,pa和pb,若pa遍历完则指向headB开头,pb同。如果两个指针同时只想一个节点或者同时指向null。

public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}

ListNode ptr1 = headA, ptr2 = headB;

// 同时指向同一个节点,或者同时为空
// 注意,null也是一种状态的,不能马上跳过,只不过null的下一个是什么,就自己判断一下
while (ptr1 != ptr2) {
if (ptr1 == null) {
ptr1 = headB;
} else {
ptr1 = ptr1.next;
}
if (ptr2 == null) {
ptr2 = headA;
} else {
ptr2 = ptr2.next;
}
}

return ptr1;
}
}

203. 移除链表元素

注意一下,删除的算法中,基本上都是,else的时候pre才会往后面移动的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;

while (pre.next != null) {
if (pre.next.val == val) {
pre.next = pre.next.next;
} else {
pre = pre.next;
}
}

return dummy.next;
}
}

725. 分隔链表

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 ListNode[] splitListToParts(ListNode head, int k) {
ListNode[] ans = new ListNode[k];

ListNode start = head;
int length = 0;
while (start != null) {
start = start.next;
length += 1;
}

int num = length / k;
int yu = length % k;


for (int i=0; i<k; i++) {
ans[i] = head;
for (int j=0; j<num+(i>yu-1?0:1) - 1; j++) {
if (head != null) {
head = head.next;
} else {
break;
}
}
if (head != null) {
ListNode temp = head;
head = head.next;
temp.next = null;
}
}

return ans;
}
}

Author: Jcwang

Permalink: http://example.com/2022/06/13/AlgorithmClassification2/