【面试算法笔记】0102-数组-双指针1
个人主页：https://github.com/zbhgis
前言
本系列主要记录自己学习算法的过程中的感悟。
力扣27.移除元素
链接：https://leetcode.cn/problems/remove-element/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.当快指针移动至需要保留元素的位置，就将nums[slow]赋值为nums[fast]，同时slow跟着fast继续前进。这样子就能保证slow操作之后，能保留需要的元素。
3.当快指针移动至需要移除元素的位置，就直接跳过进入下一次循环，此时slow还是停留原地，这样子就等于移除了元素。
4.总的来说就是分为保留元素和移除元素这两步，之后如果题目变成了保留元素，那么其实解法就类似
代码
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
for(int fast = 0; fast < nums.length; fast ++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow ++;
}
}
return slow;
}
}时空复杂度分析
fast指针得遍历完整个数组，所以时间复杂度为O(n)
直接在原始数组上修改，空间复杂度为O(1)
力扣26. 删除有序数组中的重复项
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.与上一题类似，不过这一次需要判断是否与前面的元素重复，如果不重复就移动slow，并赋值nums[slow]为nums[fast]，最后返回
3.而且这个最后返回的slow需要加1，因为最终的slow是停止在倒数第二个。
代码
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast ++) {
if (nums[fast] != nums[slow]) {
slow ++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
}时空复杂度分析
同上
洛谷P1059 [NOIP 2006 普及组] 明明的随机数
链接：https://www.luogu.com.cn/problem/P1059#ide
注意点
同上
代码
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i ++) {
nums[i] = sc.nextInt();
}
Arrays.sort(nums);
int slow = 0;
for (int fast = 0; fast < n; fast ++) {
if (nums[fast] != nums[slow]) {
slow ++;
nums[slow] = nums[fast];
}
}
System.out.println(slow + 1);
for (int i = 0; i <= slow; i ++) {
System.out.print(nums[i] + " ");
}
}
}时空复杂度分析
同上
力扣283. 移动零
链接：https://leetcode.cn/problems/move-zeroes/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.与上一题类似，不过这一次需要判断是否为零，不为零的话，就交换nums[fast]和nums[slow]，相当于把零一直往后边送。
代码
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast ++) {
if (nums[fast] != 0) {
int tmp = nums[fast];
nums[fast] = nums[slow];
nums[slow] = tmp;
slow ++;
}
}
}
}时空复杂度分析
同上
力扣844. 比较含退格的字符串
链接：https://leetcode.cn/problems/backspace-string-compare/description/
注意点
快慢指针做法。
这道题的题目关键在于如何原地操作数组。
1.设计两个指针，一快一慢。
2.在操作之前，先将字符串转为字符数组才能遍历。
3.与上一题类似，不过这一次fast没碰到退格字符的时候，需要将chars[fast]赋值给chars[slow]，slow一起跟着fast移动。如果碰到退格字符，说明这个字符需要保留，就需要将slow回退一个，相当于删除了一个字符的操作。所以循环结束之后区间[0,slow]相当于实际的数组。
4.将slow回退的时候，还需要注意slow是否等于0，等于0就不用回退了。
代码
class Solution {
public boolean backspaceCompare(String s, String t) {
return process(t).equals(process(s));
}
private static String process(String s) {
char[] chars = s.toCharArray();
int slow = 0;
for (int fast = 0; fast < chars.length; fast ++) {
if (chars[fast] != '#') {
chars[slow] = chars[fast];
slow ++;
} else {
if (slow > 0) slow --;
}
}
return new String(chars, 0, slow);
}
}时空复杂度分析
同上
参考
https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html