寒假刷题Day20

一、80. 删除有序数组中的重复项 II

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
       int n = nums.size();
       int stackSize = 2;
       for(int i = 2; i < n; i++){
            if(nums[i] != nums[stackSize - 2]){
                nums[stackSize++] = nums[i];
            }
        }
        return min(stackSize, n);
    }
};

巧妙之处在于和栈顶下方的数比较，保证数字出现次数最多是两次

二、905. 按奇偶排序数组

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right){
            if(nums[left] % 2 == 0 ){
                left++;
            }else if(nums[right] % 2 == 1){
                right--;
            }else{
                swap(nums[left], nums[right]);
                left++;
                right--;
            }
        }
        return nums;
    }
};

一开始我在中间用的while结构，这样还要判断指针是否出界

整个算法的目标是通过双指针在一次遍历中将偶数和奇数分别定位到数组的前后。每一次循环迭代，都需要根据当前指针位置的数值属性作出决策：

• 若左侧数字已符合偶数要求，则左指针直接右移；
• 若右侧数字符合奇数要求，则右指针直接左移；
• 只有当左侧数字不符合（即为奇数）且右侧数字也不符合（即为偶数）时，才需要交换两者，并同时更新指针。

使用 if-else 结构正好映射了这三种互斥的情形

三、922. 按奇偶排序数组 II

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int one = 1, tow = 0;
        for(tow; tow < nums.size(); tow += 2){
            if(nums[tow] % 2 == 1){
                while(nums[one] % 2 != 0) one += 2;
                swap(nums[one], nums[tow]);
            }
        }
        return nums;
    }
};

把数组看作两个数组（下标为奇 偶），找到不属于自己数组的元素与对方交换