双指针

🍬刷题前必看

前往原文查看

🍹开始刷题 - 力扣（LeetCode）

26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

【示例 1】

1 2	输入：nums = [1,1,2] 输出：2, nums = [1,2,_]

解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

【示例 2】

1 2	输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4]

解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

C++完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==1) return 1;
        
        int slow = 0, fast=1;  // 快慢指针法
        for(; fast<nums.size(); fast++){
            if(nums[slow]!=nums[fast]) nums[++slow]=nums[fast];
        }

        return slow+1;
    }
};

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1 2	输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

1 2	输入: nums = [0] 输出: [0]

分析：

1. 使用快慢指针，从前往后遍历

2. 初始时慢指针slow最开始指向最左边第一个0的位置，快指针fast处于slow+1位置

3. 当快指针fast遇到非0值时，交换slow和fast两个位置的值，并让slow++

   由于fast是从前往后遍历的，fast指向非0元素时才交换，而且slow每次都指向0，且每次交换值后均+1，所以不会导致原本非0元素相对顺序发生改变。（但0之间的相对位置发生改变，只不过都是0，改不改变都一样）

C++完整代码：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.size()==1) return;
        int slow = 0, fast = 1;
        while(slow<nums.size() && nums[slow]!=0) slow++;// 初始时让slow指向第一个0
        fast = slow+1;
        for(; fast<nums.size(); fast++){
            if(nums[fast]!=0) swap(nums[slow], nums[fast]), slow++;
        }
    }
};

注意：另外一种遍历方法是从后往前遍历，slow指向最右边第一个【非0元素】，fast从右往左遍历，只要遇到0就与slow位置的值交换，这样会导致非0元素之间的相对顺序发生改变，而0元素之间的相对位置没变

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

1 2 3

输入：s = "ab#c", t = "ad#c" 输出：true 解释：s 和 t 都会变成 "ac"。

示例 2：

1 2 3

输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 ""。

示例 3：

1 2 3

输入：s = "a#c", t = "b" 输出：false 解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

分析：原文查看@demigodliu

准备两个指针 i, j 分别指向 S，T 的末位字符，再准备两个变量 skipS，skipT 来分别存放 S，T 字符串中的 # 数量。
从后往前遍历 S，所遇情况有三，如下所示：

1. 若当前字符是 #，则 skipS++；

2. 若当前字符不是 #，且 skipS 不为 0，则 skipS–；

3. 若当前字符不是 #，且 skipS 为 0，则代表当前字符不会被消除，我们可以用来和 T 中的当前字符作比较：

   • 若对比过程出现 S, T 当前字符不匹配，则遍历结束，返回 false

   • 若 S，T 都遍历结束，且都能一一匹配，则返回 true。

C++完整代码

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:
    bool backspaceCompare(string s, string t) {
        
        int i=s.size()-1, j=t.size()-1;
        int skipS = 0, skipT = 0;  // skip表示待删除字符数量
        while(i>=0 || j>=0){
            while(i>=0){
                if(s[i]=='#') i--, skipS++;  //当前字符是 #
                else if(skipS>0) i--, skipS--;
                else break;
            }
            while(j>=0){
                if(t[j]=='#') j--, skipT++;
                else if(skipT>0) j--, skipT--;
                else break;
            }
            if(i>=0 && j>=0 && s[i]!='#' && t[j] != '#'){
                if(s[i]!=t[j]) return false;
                else i--, j--;
            }  else {
                return i==j;  // 如果i，j某一个<0，则判断它们是否相等，如果同时都是-1，那就是说之前的比较都正确，如果一个指向0，一个指向-1，那就是某个串还没完，另一个已经比较完了
            }
        }
        return true;
    }
};