首页 > 其他分享 >Leetcode 1089. 复写零

Leetcode 1089. 复写零

时间:2023-10-28 10:06:47浏览次数:37  
标签:src arr dest 元素 1089 我们 数组 复写 Leetcode


复写零

题目链接1089. 复写零

给你一个长度固定的整数数组 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]

题目解释

解释一下题意.什么是复写0,说人话就是我们的遍历整个数组,如果我们遇到一个元素,判断这个元素.

  • 如果是0,那么新增两个0
  • 如果不是0, 直接添加

我们遍历整个数组之后,然后裁出来和原本数组长度相等的子数组就是我们的结果.

算法原理

先说一下这个题目,本来是是非常简单的,我们可以借助一个辅助数组,然后遍历我们原来的数组,下面是我们遇到的两个情况

  • 遇到的元素是 0: 新数组里面尾插两个0
  • 遇到的元素非 0: 新数组里面将这个元素尾插
int n = nums.size();
vector<int> new_num(n);
int index = 0;
for(int i = 0; i < n; ++i)
{
    if(nums[i] == 0) 
    {
        new_num[index++] = 0;
        new_num[index++] = 0;
    }
    else 
    {
         new_num[index++] = nums[i];
    }
    if(index == n) break;
}
// 将new覆盖回去就可以了

这里我们又发现一个规律,我们使用了一个辅助数组,那么是不是可以说使用双指针?可以的,但是这里存在一个情况,我们的辅助数组的p2可能会比我们原数组跑的快,那么这就是造成一个问题,我们后面的元素会被覆盖,

Leetcode 1089. 复写零_职场和发展

这里我们也是可以使用双指针的,只不过我们需要从右向左走.对于原来数组的一个元素,他的目标位置有两个情况

  • 源位置和一个目标位置 这个元素非0
  • 原位置和两个目标位置 这个元素是0

下面我们遍历一边数组,根据题意的规则我们可以找到我们的目标位置达到n-1就可以了.这个解决了我们元素被覆盖的问题,但是存在下面一个问题.考虑一下下面的情况

我们dst为何可以到达下标n,这是因为我们的dst有可能跳2个位置,那么为何出现这种情况呢?一定是n-2位置的元素是0,这样他的目标位置就会覆盖后面的两个,所以我们需要解决一下.

Leetcode 1089. 复写零_职场和发展_02

下面是解决的办法

if (dest == n)
{
  arr[n - 1] = 0;
  src--;
  dest -= 2;
}

代码编写

class Solution
{
public:
  void duplicateZeros(vector<int> &arr)
  {
    int src = 0;
    int dest = -1;
    int n = arr.size();
    while (src < n)
    {
      if (arr[src] != 0)
      {
        dest++;
      }
      else
      {
        dest += 2;
      }
      if (dest >= n - 1)
        break;
      src++;
    }
    if (dest == n)
    {
      arr[n - 1] = 0;
      src--;
      dest -= 2;
    }

    // 找到我们的数据并且可以将我们的src的元素赋值给我们的dest
    while (src >= 0)
    {
      if (arr[src] != 0)
      {
        arr[dest] = arr[src];
        dest--;
      }
      else
      {
        arr[dest] = arr[src];
        arr[dest - 1] = arr[src];
        dest -= 2;
      }
      src--;
    }
  }
};


标签:src,arr,dest,元素,1089,我们,数组,复写,Leetcode
From: https://blog.51cto.com/byte/8065002

相关文章

  • LeetCode 611. 有效三角形的个数
    有效三角形的个数题目链接611.有效三角形的个数给定一个包含非负整数的数组nums,返回其中可以组成三角形三条边的三元组个数。示例1:输入:nums=[2,2,3,4]输出:3解释:有效的组合是:2,3,4(使用第一个2)2,3,4(使用第二个2)2,2,3示例2:输入:nums=[4,2,3,4]输出:......
  • Leetcode 283. 移动零
    移动零题目链接283.移动零给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。请注意,必须在不复制数组的情况下原地对数组进行操作。示例1:输入:nums=[0,1,0,3,12]输出:[1,3,12,0,0]示例2:输入:nums=[0]输出:[0]题目解释这道题目......
  • LeetCode 2: Add Two Numbers
    https://leetcode.cn/problems/add-two-numbers/description/FinallyIjoinedaforeigncompany'sChinabranchtolearnEnglishandstartanewjourney.PS:FromnowformeseemsMoreleisurely,elegant,high-tech,andalittlewise(inleadership)compa......
  • [Leetcode] 0104. 二叉树的最大深度
    104.二叉树的最大深度题目描述给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例:给定二叉树[3,9,20,null,null,15,7],3/\920/\157返回它的最大深度 3。......
  • #yyds干货盘点# LeetCode程序员面试金典:生命游戏
    题目根据百度百科,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。给定一个包含m×n个格子的面板,每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态:1即为活细胞(live),或0即为死细胞(dead)。每个细胞与其八个相邻位置(水平,垂......
  • #yyds干货盘点# LeetCode程序员面试金典:最小操作次数使数组元素相等 II
    题目给你一个长度为n的整数数组nums,返回使所有数组元素相等需要的最小操作数。在一次操作中,你可以使数组中的一个元素加1或者减1。 示例1:输入:nums=[1,2,3]输出:2解释:只需要两次操作(每次操作指南使一个元素加1或减1):[1,2,3] => [2,2,3] => [2,2,2]示......
  • leetcode98-验证二叉搜索树
    一开始没有考虑到左子树的所有节点都要小于根节点,右子树要大于根节点,本质上是边界没有考虑仔细,所以比较时需向上比较(和父节点)而不是向下比较(和子节点比大小)根节点没有父节点,因此初始化时引用最大最小值即可,注意这里的数值范围点击查看代码classSolution{publicboolean......
  • [Leetcode] 0101. 对称二叉树
    101.对称二叉树题目描述给你一个二叉树的根节点root,检查它是否轴对称。 示例1:输入:root=[1,2,2,3,4,4,3]输出:true示例2:输入:root=[1,2,2,null,3,null,3]输出:false 提示:树中节点数目在范围[1,1000]内-100<=Node.val<=100 进阶:你可以运用递......
  • LeetCode 283. 移动零
    移动零题目链接283.移动零给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。请注意,必须在不复制数组的情况下原地对数组进行操作。示例1:输入:nums=[0,1,0,3,12]输出:[1,3,12,0,0]示例2:输入:nums=[0]输出:[0]题......
  • LeetCode 1089. 复写零
    复写零题目链接1089.复写零给你一个长度固定的整数数组arr,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。注意:请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改,不要从函数返回任何东西。示例1:输入:arr=[1,0,2,3,0,4,5,0]输......