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

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

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

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

思路

快指针用来扫描，找到非重复元素；慢指针用于找到可覆盖位置。

三种情况：数组长度为0；数组无重复元素；数组有重复元素。

class Solution 
{
public:
    int removeDuplicates(vector<int>& nums) 
    {
        if(nums.size()==0) return 0;
        int i =1;
        for(int j=1;j<nums.size();j++)
        {
            if(nums[j] != nums[i-1])
            {
                nums[i]=nums[j];
                i++;
            }
        }
        return i;
    }
};

283. 移动零

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

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

class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        int slow=0;
        for(int fast=0;fast<nums.size();fast++)
        {
            if(nums[fast]!=0)
            {
                swap(nums[fast],nums[slow]);
                slow++;
            }
        }
    }
};

844. 比较含退格的字符串

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

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

class Solution {
public:
    bool backspaceCompare(string S, string T) 
    {
        int sSkipNum = 0; // 记录S的#数量
        int tSkipNum = 0; // 记录T的#数量
        int i = S.size() - 1;
        int j = T.size() - 1;
        while (1) 
        {
            while (i >= 0) 
            { // 从后向前，消除S的#
                if (S[i] == '#') sSkipNum++;
                else 
                {
                    if (sSkipNum > 0) 
                        sSkipNum--;
                    else 
                        break;
                }
                i--;
            }
            while (j >= 0) 
            { // 从后向前，消除T的#
                if (T[j] == '#') tSkipNum++;
                else 
                {
                    if (tSkipNum > 0) 
                        tSkipNum--;
                    else 
                        break;
                }
                j--;
            }
            // 后半部分#消除完了，接下来比较S[i] != T[j]
            if (i < 0 || j < 0) break; // S 或者T 遍历到头了
            if (S[i] != T[j]) return false;
            i--;j--;
        }
        // 说明S和T同时遍历完毕
        if (i == -1 && j == -1) return true;
        return false;
    }
};

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路1

显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。

看示例 1，把 [−4,−1,0,3,10] 分成负数和非负数两部分：

负数：[−4,−1]，计算平方得 [16,1]，反过来看就是 [1,16]。
非负数：[0,3,10]，计算平方得 [0,9,100]。
仿照 88. 合并两个有序数组 的 思路，把上述两个有序数组合并，得到答案 [0,1,9,16,100]。

与其从中间开始向两边合并，不如从两边开始向中间合并，这样无需计算从中间的哪个位置开始。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int i = 0, j = n - 1;
        for (int p = n - 1; p >= 0; p--) {
            int x = nums[i] * nums[i];
            int y = nums[j] * nums[j];
            if (x > y) {
                ans[p] = x;
                i++;
            } else {
                ans[p] = y;
                j--;
            }
        }
        return ans;
    }
};

思路2

双指针法

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0); //创建一个名为 result 的整数类型的 vector，其大小与另一个 vector（或容器）A 相同，并且所有元素初始化为 0。
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};