[LeetCode]-283. 移动零-1089. 复写零

2023-12-13 03:06:08

目录

283. 移动零

描述

?解析

代码

1089. 复写零

描述

解析

代码


283. 移动零

283. 移动零icon-default.png?t=N7T8https://leetcode.cn/problems/move-zeroes/

描述

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

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

示例 1:

输入:nums=[0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入:nums=[0]
输出: [0]

?解析

利用双指针思想,前指针cur遍历数组,判断nums[cur],找出非0的数,再与后指针dest下标所在的数nums[dest]交换,将数组划分为三块区域非0区、0区、带处理区,直到cur处理完数组的最后一个数字。

代码

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

1089. 复写零

1089. 复写零icon-default.png?t=N7T8https://leetcode.cn/problems/duplicate-zeros/

描述

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

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

示例 1:

输入:arr = [1,0,2,3,0,4,5,0]
输出:[1,0,0,2,3,0,0,4]
解释:调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4]

示例 2:

输入:arr = [1,2,3]
输出:[1,2,3]
解释:调用函数后,输入的数组将被修改为:[1,2,3]

解析

1.先找到最后一个“复写”的数

双指针算法:1.先判断cur位置的值。2.决定dest向后移动异步或者两步。3.判断一下是否已经结束为止。4.cur++

2.处理一下边界情况

3.“从后往前”完成复写操作

代码

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

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