Leetcode|Array Problem Sets

快慢指针

删除有序数组中的重复项

基础思路

首先一个很暴力的思路就是把所有不重复的元素都找到，然后 copy 到一个新的数组里，这种做法最暴力，同时空间利用率也是最低的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int removeDuplicatesViolet(int[] nums) {
	if (nums.length == 0) {
		return 0;
	}
	//开一个新数组来存取元素
	int[] res = new int[nums.length];
	//记录上一个被标记的重复的元素
	int prev = nums[0];
	res[0] = prev;
	//记录新数组存取的索引idx
	int idx = 0;
	//遍历原始数组如果发现有之前不一样的，就存储到新的数组里
	for (int i = 1; i < nums.length; i++) {
		if (nums[i] != prev) {
			res[++idx] = nums[i];
			prev = nums[i];
		}
	}
	//因为会检查原有数组的元素，因此需要把新数组的元素重新复制进去一遍
	for (int i = 0; i < idx; i++) {
		nums[i] = res[i];
	}
	return idx + 1;
}

双指针的快慢指针进行优化

上述的操作完全可以优化，通过对数组进行原地修改数据就可以实现，省去了额外的O(n)空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int removeDuplicates(int[] nums) {
	if (nums.length == 0) {
		return 0;
	}
	//快慢指针
	int slow = 0, fast = 0;
	//快指针在前面探路
	while (fast < nums.length) {
		//只要发现不重复的元素，就更新 slow 并且存储
		if (nums[slow] != nums[fast]) {
                   //慢指针充当了暴力方法中的 被标记的重复的元素
			nums[++slow] = nums[fast];
		}
		fast++;
	}
	return slow + 1;
}

总结

这道题的一个核心思想其实就是 记录上一个标记的重复的元素，遇到新的元素存取下来

通过快慢指针优化了多的空间

移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int removeElement(int[] nums, int val) {
	if (nums.length == 0) {
		return 0;
	}
	//双指针的快慢指针思想
	int slow = 0, fast = 0;
	while (fast < nums.length) {
		//只要不是要被删除的元素，就原地赋值到慢的那个指针的位置
		if (nums[fast] != val) {
			nums[slow++] = nums[fast];
		}
		fast++;
	}
	return slow;
}

还是经典的快慢指针思想

其实和上面的本质思想是差不多的

采取快慢指针的做法，快指针扫描数组，只要是不是被删除的元素，就更新到慢指针上

移动零

快慢指针思想适用于原地删除和移动数据的操作

在这一题中，看似是移动所有的0

实际上我们可以把移动的过程等价转化为：先删除，之后再进行一轮赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void moveZeroes(int[] nums) {
	if (nums.length == 0) {
		return;
	}
	int slow = 0, fast = 0;
	//先把所有非零的数据移动到前面，相当于删除所有0
	while (fast < nums.length) {
		if (nums[fast] != 0) {
			nums[slow++] = nums[fast];
		}
		fast++;
	}
	//之后把所有的0补上
	//非0数据的长度是slow，下标到slow-1，因此从slow下标开始全部置0
	for (int i = slow; i < nums.length; i++) {
		nums[i] = 0;
	}
}

左右指针

最经典的二分搜索

太经典了所以直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int binarySearch(int[] nums, int tar) {
	int left = 0, right = nums.length - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (nums[mid] == tar) {
			return mid;
		}
		else if (nums[mid] > tar) {
			right = mid - 1;
		}
		else if (nums[mid] < tar) {
			left = mid + 1;
		}
	}
	//没找到
	return -1;
}

两数之和 II - 输入有序数组

题目信息

思路分析

首先看到题目的数组有序，我们就应该想到使用二分，或者是类似二分的左右指针思想

这题也是给一个target数，其实很符合二分的应用场景

我们可以类似的使用二分的思想，左右指针分别指向两个数据，每一次循环都不断调整左右指针和的范围，如果左右指针和比target大了，说明要往小的找，也就是左移right；如果左右指针和比target小了，说明要往大的找，也就是右移left。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] twoSum(int[] numbers, int target) {
	int left = 0, right = numbers.length - 1;
	//题目要求是不能返回重复的元素，因此left和right指针不能重合
	while (left < right) {
		//类比二分计算mid的操作，这里借用的是二分的思想
		int sum = numbers[left] + numbers[right];
		if (sum == target) {
			return new int[] {left + 1, right + 1};
		}
		else if (sum > target) {//左右指针的数据和比target大了，说明要变小，right指针左移
			right--;
		}
		else {
			left++;
		}
	}
	return new int[] {-1, -1};
}

反转数组

思路分析

有了之前的左右指针技巧积累，这题基本就是秒杀的了

代码实现

1
2
3
4
5
6
7
8
9
10
public void reverseString(char[] s) {
	int l = 0, r = s.length - 1;
	while (l < r) {
		char temp = s[l];
		s[l] = s[r];
		s[r] = temp;
		l++;
		r--;
	}
}

最长回文子串

暴力思路

首先这题可以通过暴力的方式来处理，枚举所有的子串，然后判断所有子串是否为回文串，如果是回文，维护一个最长回文子串的变量用于记录结果

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
public String longestPalindrome(String s) {
       if (s.length()==1){
		return s;
	}
	String  res = "";
	for (int i = 0; i < s.length(); i++) {
		for (int j = i+1; j <=s.length(); j++) {
                   //data就是所有的子串
			String data = s.substring(i, j);
                   //判断子串是否是回文
			if (checkPalindrome(data)) {
                        //如果是更新记录
				if (res.length()<data.length()){
					res=data;
				}
			}
		}
	}
	return  res;
}
   private boolean checkPalindrome(String s){
       int l =0,r=s.length()-1;
       while(l<r){
           if(s.charAt(l)!=s.charAt(r)){
               return false;
           }
           l++;
           r--;
       }
       return true;
   }

TLE了，悲

从中心扩散的双指针

由于是回文串，最简单的回文串可以通过左右双指针来进行判断

但是这里是要求出所有的回文串同时还要是子串，子串连续的位置可以任意定，因此左右指针相向行驶的情况就不能覆盖到所有的子串

针对这一个限制我们可以尝试从中心往外扩散的双指针技巧

对于任意的回文串，长度可能是奇数或者是偶数，但是从回文串的中心（长度为偶数就认为有两个中心，其实都是相等的字符）出发一定都保证扩散的过程中是回文的。

因此我们可以枚举所有的中心点，在每一个中心点都找最长的奇数长度回文子串和偶数长度回文子串，不断更新记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String longestPalindrome(String s) {
	String  res = "";
	for (int i = 0; i < s.length(); i++) {
		String s1 = findPalindromeFromCenter(s, i, i + 1);
		String s2 = findPalindromeFromCenter(s, i, i);
		s1=s1.length()>s2.length()?s1:s2;
		res=res.length()>s1.length()?res:s1;
	}
	return  res;
}

/**
 * 在s中寻找以l和r为中心的最长回文串
 */
private String findPalindromeFromCenter(String s, int l, int r) {
	while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
		//双指针向两边展开
		l--;
		r++;
	}
	//此时l和r内部的串就是最长回文串（l和r端点不包含在内，因此是subString(l+1,r)）
	return s.substring(l+1,r);
}

前缀和

应用场景

如果说二分的应用场景适用于有序数组，看到有序数组就要想到二分。

那么前缀和这一个算法技巧则是适用于频繁出现 计算某个区间内元素的和 的情况

先用一个简单题来感受一下

区域和检索，数组不可变

303. 区域和检索 - 数组不可变 - 力扣（LeetCode）

最暴力的做法，可能会TLE

最暴力的做法就是不用前缀和数组，每一次sumRange的时候都通过一轮遍历计算sum，之后相减得到结果，这种做法很明显是要O(n)的时间的

前缀和数组做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class NumArray {
	//前缀和数组
	int[] preSum = null;

	public NumArray(int[] nums) {
		//初始化前缀和数组
		preSum = new int[nums.length+1];
		for (int i = 1; i < preSum.length; i++) {
			preSum[i] = nums[i-1]+preSum[i - 1];
		}
	}

	public int sumRange(int left, int right) {
          //O(1)的查询处理
		return preSum[right+1] - preSum[left];
	}
}

需要注意几个关键点：

  • 前缀和数组的长度要比原始数组长度多1个单位，我们约定，preSum[i]记录的是从nums[0]-nums[i-1]的所有元素之和

前缀和数组举例

  • 在最终返回结果的时候，需要注意索引关系
    • 以left=2,right=4为例，实际上计算的是nums[2]~nums[4]之间所有的元素之和
    • 对应的preSum[5]=nums[0]~nums[4]
    • 而preSum[2]=nums[0]~nums[1]
    • preSum[5]-preSum[2]就是我们想要的结果，nums[2]~nums[4]
    • 因此最终结果通过找出规律应当是preSum[right+1]-preSum[left]
CS_Basic
#Algorithm #Leetcode #Labuladong
Leetcode|Array Problem Sets
http://example.com/2023/05/20/Leetcode-Array-Problem-Sets/
作者
Noctis64
发布于
2023年5月20日
许可协议