【算法挨揍日记】day01——双指针算法_移动零、复写零

Love The Way You Lie 2024-03-23 21:34 7阅读 0赞

### ![54014841d127486389b3b9e18484aad0.png][] ###

### 283.移动零 ###

[283. 移动零![icon-default.png?t=N6B9][icon-default.png_t_N6B9]https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/593fd43fee364ff48a4a3e6db9a7883e.png][283. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_move-zeroes]

#### 题目： ####

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

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

![cc192a66d20f493c859cee4e68767783.png][]

#### 解题思路： ####

> 我们可以利用两个指针（dest和cur）的方法，将这个数组分为三个区域
> 
> 我们可以将dest初始化为-1，cur初始化为0
> 
> ![d0a1825e9ed54273983b4e1d13ca06e5.png][]
> 
> cur走一遍数组遇到的两种情况：
> 
>  *  cur位置为0
>  *  cur位置为非0
> 
> 当cur位置为0，cur++；
> 
> 当cur不为0时，swap交换一下就好，dest++；

#### 解题代码： ####

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

### 1089. 复写零 ###

[1089. 复写零![icon-default.png?t=N6B9][icon-default.png_t_N6B9]https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/10a1e6e195db4e58bd4cea2d6cd0e40e.png][1089. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_duplicate-zeros]

#### 题目： ####

给你一个长度固定的整数数组 `arr` ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 **就地** 进行上述修改，不要从函数返回任何东西。

#### ![4f5b926e300a4c8f9e8b64e05ab54b02.png][] 解题思路： ####

> 本题要求我们要就地修改，不能使用额外的数组，我们先用额外的数组想一想
> 
> 我们发现结果是这样的
> 
> ![11b7d00ba58c4c11bf8c57c136d6d1d1.png][]
> 
> 我们再将使用额外数组的双指针方法用在本地去实验一下，我们发现dest=-1和cur=0，去正向解决问题不可以，会有元素被覆盖丢失的问题！
> 
> 我们试着反向去操作呢，dest=size-1（指向最后一个元素），那我们如何确定cur的位置呢？
> 
> 我们可以再利用一次双指针的方法来确认cur的位置，一开始cur=0，dest=-1
> 
> 遍历数组，当cur遇到0时，dest+=2；当cur遇到非0时，cur++；
> 
> 这里会有一种边界情况需要我们去考虑：
> 
> 示例：1 0 2 3 0
> 
> 我们通过上述方式来确定cur时，会出现以下这种情况：
> 
> ![1e04de1835cd4c08b793a17838678af6.png][]
> 
> 会出现dest越界的情况，我们考科一让size-1的位置置为0，然后cur--，dest-=2这样就可以解决问题了
> 
> 然后从后向前遇到0就是置两次0，遇到非0就是复制咯，这一步简单
> 
> ![fb5c87324cac43d3aed04cbd49963c8a.png][]

#### 解题代码： ####

class Solution {
    public:
        void duplicateZeros(vector<int>& arr) {
            int dest=-1;
            int cur=0;
            int size=arr.size();
            //确认cur的位置
            while(cur<size)
            {
                if(arr[cur]==0)dest+=2;
                else dest++;
    
                if(dest>=size-1)break;
                cur++;
            }
            //边界情况，示例：1 0 2 3 0,当dest的位置越界了
            if(dest==size)
            {
                arr[size-1]=0;
                dest-=2;
                cur--;
            }
            while(cur>=0)
            {
                if(arr[cur]!=0)
                {
                    arr[dest--]=arr[cur--];
                }
                else 
                {
                    arr[dest--]=0;
                    arr[dest--]=0;
                    cur--;
                }
            }
        }
    };

![6359ddb1097b417b8dbf252269d20c98.gif][]

[54014841d127486389b3b9e18484aad0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/52587d4e4d594d2d84358532ed8151e8.png
[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[283. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_move-zeroes]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/593fd43fee364ff48a4a3e6db9a7883e.png
[cc192a66d20f493c859cee4e68767783.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b4d484017a5e4e46805cb57a22015c67.png
[d0a1825e9ed54273983b4e1d13ca06e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c1b9004dd5ff45a9b903fb14cebef1cd.png
[1089. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_duplicate-zeros]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/10a1e6e195db4e58bd4cea2d6cd0e40e.png
[4f5b926e300a4c8f9e8b64e05ab54b02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ad9407a216f34a7ab47b291e828e92e3.png
[11b7d00ba58c4c11bf8c57c136d6d1d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d1d6a50cb5ab49e4a87befea7046562e.png
[1e04de1835cd4c08b793a17838678af6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/26dadcb8dd69405db7f34043166590d1.png
[fb5c87324cac43d3aed04cbd49963c8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/20f89ded36e24f9298ea715b6e96c4da.png
[6359ddb1097b417b8dbf252269d20c98.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c070b7df142f47b6933e4662593f3dcc.png