移动零

这道题我觉得真的很叼，评论区的思路让我豁然开朗，原来还可以这样写

题目

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

我的题解

我最开始就是普通的双指针思维，fast先移动，如果nums[fast]不是0，则让Nums[slow]也等于该数，然后slow移动，统计一下有多少个0的数，最后把数组结尾这几个数赋0。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        int count = 0;
        int n=nums.size();
        for(int fast = 0;fast<nums.size();fast++)
        {
            if(nums[fast] != 0)
            {
                nums[slow]=nums[fast];
                slow++;
            }
            else
                count ++;
        }
        for(int i =0;i<count;i++)
        {
            nums[n-i-1]=0;
        }
    }
};

高端题解

这个版本的题解属实有点牛逼，相当于双指针，但是如果nums[fast]不是0的话，直接交换nums[slow]和nums[fast]，fast和slow同步移动；如果nums[fast]为0，则fast继续前进，slow站住0坑，到下一个nums[fast]不为0的时候继续两者交换，这样的话可以保证排序的同时完成0的移位。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                // 每次保证是0和非0的交换
                swap(nums[slow++], nums[i]);
            }
        }
    }
};

比较含退格的字符串

题目描述

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

解题思路

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int skipnum=0;
        int tipnum=0;
        int i= s.size() -1;
        int j= t.size() -1;
        while(1)
        {
            while(i>=0)
            {
                if(s[i]=='#')
                    skipnum++;
                else
                {
                    if(skipnum>0)
                        skipnum--;
                    else
                        break;
                }
                i--;
            }

            while(j>=0)
            {
                if(t[j]=='#')
                    tipnum++;
                else
                {
                    if(tipnum>0)
                        tipnum--;
                    else
                        break;
                }
                j--;
            }
            if(i<0 || j<0)
                break;
            if(s[i]!=t[j])
                return false;
            i--;
            j--;
        }
        if (i==-1 && j==-1)
            return true;
        return false;
    }
};

有序数组的平方

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