【leetcode题解C++】26.删除有序数组中的重复项 and 844.比较含退格的字符串

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

给你一个?非严格递增排列?的数组?nums?，请你?原地?删除重复出现的元素，使每个元素?只出现一次?，返回删除后数组的新长度。元素的?相对顺序?应该保持?一致?。然后返回?nums?中唯一元素的个数。

考虑?nums?的唯一元素的数量为?k?，你需要做以下事情确保你的题解可以被通过：

• 更改数组?nums?，使?nums?的前?k?个元素包含唯一元素，并按照它们最初在?nums?中出现的顺序排列。nums?的其余元素与?nums?的大小不重要。
• 返回?k?。

示例 1：

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

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
不需要考虑数组中超出新长度后面的元素。

思路1：很明显会使用到双指针的思路，即用快指针遍历旧数组，用慢指针指向需要更新的元素（也可以把慢指针抽象成一个新的数组的首指针，用于向新数组中添加不重复的元素）

代码实现1：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int fast = 0;
        int slow = 0;
        for (; slow < nums.size(); slow++) {
            for (; fast < nums.size(); fast++) {
                if (nums[slow] != nums[fast]) {
                    nums[slow + 1] = nums[fast];
                    break;
                }
            }
            if (fast > nums.size() - 1)
                break; // fast走到最后一个
        }
        return slow + 1;
    }
};

思路2：哈希表，利用unorder_set中元素不能重复出现的特性，有则改之（删原来数组中的），无则加“里面”。

代码实现2：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        unordered_set<int> hashSet;
        for(int i=0;i<nums.size();i++){
            if(hashSet.find(nums[i])==nullptr){
                hashSet.insert(nums[i]);
            }
            else{
                nums.erase(nums.begin()+i);
                i--;//删除之后记得遍历的是原来的位置
            }
        }
        return nums.size();
    }
};

844.比较含退格的字符串

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

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

示例 1：

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

示例 2：

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

示例 3：

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

思路：两个字符串（数组）都用双指针，遇到"#"就退格（代码中else的部分），值得注意的是，退格不能退成负数。

（如果不太好理解，可以把声明的两个指针当作新创建的数组，把不是"#"的添加进去，遇到"#"就删除一个元素。）

代码实现：

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int sp = 0, tp = 0;
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] != '#') s[sp++] = s[i];
            else sp = sp-1 > 0 ? sp-1 : 0;
        }
        for(int j = 0; j < t.size(); ++j) {
            if(t[j] != '#') t[tp++] = t[j];
            else tp = tp-1 > 0 ? tp-1 : 0;
        }
        if(sp != tp) return 0;
        for(int n = 0; n < sp; ++n) {
            if(s[n] != t[n]) return 0;
        }
        return 1;
    }
};