刷题笔记：day 1

力扣  283 移动零

解法一：双指针

定义一个指针  cur  去遍历数组 ； 定义一个指针 dest 去指向已处理区间中，非零的最后一个位置。

然后让 指针 cur 遇到 0 ，就往后走 ； 遇到的数不是 0 ，就与 dest指针的下一个数交换位置，直至将数组遍历结束为止。

cur 指向不是0 的位置

让dest+1位置的数与cur 位置的数交换，swap(nums[cur], nums[dest+1)

 

 两个指针的向前走一步。

代码实现：

class Solution {
public:void moveZeroes(vector<int>& nums) {int dest = -1;int cur = 0;while(cur < nums.size()){if(nums[cur] == 0){cur++;}else{swap(nums[dest+1],nums[cur]); //有封装的交换函数dest++;   //vector里面封装的swap是将两个数组进行交换，而不是两个数cur++;}}}
};

 解法二：

同样使用双指针，i 和 j ，不过不是使用交换，而是将后面的非零元素覆盖前面的0元素。

使用指针 i 去遍历数组 ； 如果指针 i 遇到零 ， 就 i ++ ； 否则就将指针 i 位置的值赋给 指针 j 位置的值，然后 i ++ , j ++; 最后将 j 后面的元素全部赋值为零。

class Solution {
public:void moveZeroes(vector<int>& nums) {int i = 0, j = 0;while(i<nums.size()){if(nums[i] ==0){i++;}else{nums[j] = nums[i];j++;i++;}}//将 j 后面的元素赋值为0 while(j<nums.size()){nums[j] = 0;++j;}}
};

解法三：

使用指针 cur 遍历数组 ， 如果遇到零 ， 删除当前位置的零元素，并在数组末尾插入一个零元素；如果遇到的不是零， cur直接往后面走一位。

class Solution {
public:void moveZeroes(vector<int>& nums) {int len = nums.size();  // 用len来限制循环次数int cur = 0 ;while(len > 0){if(nums[cur] ==0){nums.erase(nums.begin()+cur);nums.push_back(0);}else{++cur;}--len;}}
};

解法四：

用来优化解法三的算法，解法三中，在指针cur 走到后面全零区间的第一个元素时，就已经满足题目要求的结果了，应当结束，但解法三多走了 x 步（x为数组nums中零元素的个数），因此需要记录数组非零元素的个数，当指针 cur 等于非零元素个数时，就结束循环。

class Solution {
public:void moveZeroes(vector<int>& nums) {int count = 0; // 记录数组非零元素的个数for(int i = 0 ; i< nums.size();++i){if(nums[i] !=0){++count;}}int cur = 0 ;while(cur < nums.size()){if(nums[cur] ==0){if(cur == count){break;}nums.erase(nums.begin()+cur);nums.push_back(0);}else{++cur;}}}
};