在做题中学习(37):复写零

发布时间:2023年12月22日

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--;
            }
        }

    }
};
文章来源:https://blog.csdn.net/yiren_liusong/article/details/135146748
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。