[C++知识库]【c++复健】双指针应用

【c++复健】双指针-leetcode应用题

继续撸c++和算法。
双指针数组操作。
第一个题目是给一组递增排列的数组（有负数和正数），然后要你把每个元素平方后的结果重新按照升序排列。

解题思路是，在一个for循环里面，设置两个指针，一个指向顺序脚标，一个指向逆序脚标，然后设置一个变量来代表新数组里面的脚标。

直接上代码：

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

第二题是旋转数组，要求用尽量简单的方法，做到把一个数组【环】中的数组向后挪n位。
我的思路是先用数组的length对n位取模。
然后算出在数组末尾的多少个数据将要被挪到新数组的前排。
这样同时操作，前排数组挪到后排，和后排数组挪到前排，两个挪动。
最大挪动次数为前排数据的个数或者后排数据的个数（取max）。

直接上代码：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        int realMove = k % len;
        int preStart = 0;
        vector<int> ans(len);
        for(int i = preStart, j = len - realMove;i<len-realMove || j < len;){
            if(i<len - realMove){
                ans[i + realMove] = nums[i];
            }
            
            if(i<realMove){
                ans[i] = nums[j];
                ++j;
            }
            i++;
            
        }
        for(int i = 0;i<len;i++){
            nums[i]  = ans[i];
        }
    }
};

这个方法时间复杂度尚可，但是貌似空间复杂度不行，在提交之后在耗时上比较优秀，但是内存占用比人家多很多，我在整其他的办法（人菜是这样的，菜了好几年了）。

第三题，一道很简单的移动0。（力扣双指针283）
题目要求是把数组中的0移到数组后排去，其他数组元素按照原来顺序排。
我本来想的是换位置然后重新排列。
想复杂了，其实直接遇到0是每个数往前挪动一位就行；
用的是双循环嵌套，所以时间用了很多（大概是n2），但是空间复杂度排名还可以。

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

但是这个方法并不标准，也不能很好的体现双指针的思想。
下面提供一种“标准化的快慢指针”：
快指针，遍历数组，找到不为0的元素，赋值给慢指针指向的位置。
慢指针，每次被赋值一次，才++；
这空间复杂度就小很多了，是n
直接上代码（这个格式牢记！）

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