在做题中学习（37）：复写零

1089. 复写零 - 力扣（LeetCode）

思路：双指针法

1.因为是就地修改不能用新数组，但可以试试看看结果是什么（结尾数是4）

（cur遍历数组）（当cur！=0时替换一个 当cur==0 时替换两个）

2.从前到后会覆盖所以不行

3.试试从后往前

因为用两个数组看出修改后数组最后一个元素为4，所以可以从后往前试试，结果发现可以哎！

所以现在问题是如何找出修改后的数组最后的数字在原数组的位置。

4.找出它的位置? ? ?（思路是由上面1用两个数组实践来的）

????????依旧是双指针法

????????1.判断cur位置的值

????????2.dest根据cur走一步或两步

????????3.判断dest是否到数组末尾（到了的话，此时cur所指元素就是要找的末尾元素）

? ? ? ? 4.cur++

4.5边界情况

有可能dest因为cur最后走两步走到了n下标位置（越界）

解决方法：1.n-1? ->0

? ? ? ? ? ? ? ? ? 2. cur--? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? 3.dest-=2

若遇到边界情况，最后的下标

class Solution 
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        //1.找到最后一个复写的数
        int cur = 0, dest = -1, n = arr.size();
        while(cur<n)
        {
            if(arr[cur])
            {
                dest++;
            }
            else
            {
                dest += 2;
            }
            if(dest >= n-1)
            {
                break;
            }
            cur++;
        }
        //走到这里dest要么是n-1下标位置，要么是n下标位置
        //2.处理n下标位置的边界情况
        if(dest == n)
        {
            arr[n-1] = 0;
            cur--;
            dest -= 2;
        }
        //走到这里cur是最后一个要复写的数
        //3.从后往前复写0
        while(cur>=0)
        {
            if(arr[cur])
            {
                arr[dest--] = arr[cur--];
            }
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }

    }
};