📝前言說明：

• 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：1，本人解法 + 本人屎山代碼；2，優質解法 + 優質代碼；3，精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

293. 移動零

---

個人解

思路：
用時：15:16，（真是沒救了，寫成這樣）
屎山代碼：通過

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

時間復雜度：O(n)
空間復雜度：O(1)

---

優質解

思路：整個數組可以劃分成：已排序區[0, slow] + 零區[ slow + 1, fast ) + 待排序區[fast, n-1]
我屎山代碼的問題：我的slow和fast是分別移動的，后續還需要自己維護fast > slow
優質解法：

• slow指針始終指向已排序區的最后一個元素，slow不主動移動，只在交換時移動，這樣就可以始終用來標識已排序區的位置。
• 用fast指針遍歷數組，當fast != 0時，和slow + 1位置的0交換。

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

時間復雜度：O(n)
空間復雜度：O(1)

---

1089. 復寫零

個人解

思路：一個指針在前，一個指針在后，前指針遇到0要復寫的時候，通過后指針，把復寫位置后的元素都往后移動一位，騰出空間。

用時：17：21，
屎山代碼：通過

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();int slow = 0, fast = n - 1;while(slow < n - 1){if(arr[slow]){slow++;}else{slow++;for(fast = n - 1; slow < fast; fast--){arr[fast] = arr[fast - 1];}arr[slow] = 0;slow++;}}}
};

時間復雜度：O($n^2$)
空間復雜度：O(1)

---

優質解：

首先，我們先思考，如果不是就地操作的解法：
創建一個新的數組，然后一個指針cur指向原數組，一個指針dest指向新數組，dest根據cur的值不斷進行復寫操作。

那換成就地操作呢？
如果直接這么操作，那dest復寫兩次的時候就會覆蓋還沒有復寫的值。

那能不能從后往前進行復寫操作？
答案是可以的，問題是要先找到最后一個復寫的數。

最后一個復寫的數由什么決定？
如果我們看題不仔細，不認真思考的話就會簡單認為：0的個數直接決定后面幾個數會被移出數組外，如：若有3個0，那么倒數第4個數就是最后一個復寫的數。（因為后3個數的位置 → 被前面復寫的0個替代了）
但其實不然，因為：0有可能被移動出去

所以，重點又變成了，如何找最后一個要復寫的數的位置。
方法：我們先模擬一遍復寫的過程但是不復寫，就可以讓cur定位到最后一個要復寫的元素，dest指向從后往前復寫的第一個要復寫的開始位置。
步驟：

1. cur指向當前要復寫的元素，遍歷數組，dest指向已經復寫完的位置（的最后一個）
2. 當arr[cur] == 0，dest移動兩步，否則為一步
3. 判斷dest是否到達結束位置，達到了就提前退出循環。
   注意點1：在本次循環中的cur不能移動，因為cur指向的是要復寫的，如果移動了就到了下一個沒有復寫的位置。
   注意點2：會有在數組外復寫的情況：這種情況是在dest == n-1的時候還要復寫兩個0，解決方法：只需要讓arr[n-1] = 0，dest -= 2，cur -= 1就行，因為這種情況下已確定最后一位寫的是0

文字敘述晦澀難懂，建議畫圖

代碼：

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1, n = arr.size(); // dest指向復寫完的最后一個位置while(cur < n) {if(arr[cur]) dest++; else dest += 2;if(dest >= n-1) break; // dest = n-1 代表已經寫完最后一個位置了cur++; // cur指向的元素代表要復寫的元素}if(dest == n) // 代表在數組外面寫了{arr[n-1] = 0;dest -= 2;cur -= 1;}while(cur >= 0){if(arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

時間復雜度：O(n)
空間復雜度：O(1)

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！