[双指针](一) Leetcode 283.移动零和1089.复写零

这篇具有很好参考价值的文章主要介绍了[双指针](一) Leetcode 283.移动零和1089.复写零。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[双指针] Leetcode 283.移动零和1089.复写零

移动零

283. 移动零

[双指针](一) Leetcode 283.移动零和1089.复写零,LEETCODE,leetcode,算法,职场和发展

1.题意分析

(1) 给你一个数组,将数组中的所有0移动到数组的末尾

(2) 保证非0元素在数组中相对位置不变

(3) 在原数组中操作

2.解题思路

由于题目要求我们移动数组内容(也就是交换两个数的位置),所以我们很容易想到双指针解法。

解法:双指针

定义两个“指针”(left 和 right),right遍历整个数组,遇到0就交换两个数的位置。

nums[right] == 0:right++;

nums[right] != 0:swap(nums[right],    nums[left]),  right++, left++

示例1:[0, 1, 0, 3, 12]

[双指针](一) Leetcode 283.移动零和1089.复写零,LEETCODE,leetcode,算法,职场和发展

[双指针](一) Leetcode 283.移动零和1089.复写零,LEETCODE,leetcode,算法,职场和发展

请先自己尝试实现代码,再来继续往下看。


3.代码实现
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int left = 0, right = 0; right < nums.size(); )
        {
            if(nums[right] != 0) swap(nums[left++], nums[right++]);
            else right++;
        }
    }
};

[双指针](一) Leetcode 283.移动零和1089.复写零,LEETCODE,leetcode,算法,职场和发展

4.总结

细节1:right的大小由我们自己在if-else控制,并不需要写入循环。

细节2:right的大小超过数组的size即为遍历完整个数组。

复习零

1089. 复写零

[双指针](一) Leetcode 283.移动零和1089.复写零,LEETCODE,leetcode,算法,职场和发展

1.题意分析

(1) 给你一个长度固定的数组,将数组中的0再次写一遍,即为在0后再加一个0

(2) 其余的数向右平移

(3) 超过数组长度,终止写入元素

(4) 在原数组上进行操作

2.解题思路

题目要求我们进行复写0,即需要知道两个数的位置,所以可以使用两个“指针”,一前一后:判断0,添加0。

解法:双指针

由于数组空间是固定的,我们首先需要知道最后一个数的位置,然后倒着进行修改数组。

nums[i] == 0:count+= 2;

nums[i] != 0:count++;

count >= nums.size-1:break;

i++;

i即为新数组的最后一个数,我们在倒着写回数组。

nums[i] == 0:nums[count] = 0, count[count-1] = 0, i--, count -= 2;

nums[i] != 0:nums[count] = nums[i], i--, count--。

示例1:

nums[] = [1, 0, 2, 3, 0, 4, 5, 0]

[双指针](一) Leetcode 283.移动零和1089.复写零,LEETCODE,leetcode,算法,职场和发展

注意处理这样的数组: nums[] = {8, 4, 5, 0, 0, 0, 0, 7}

请先自己尝试实现代码,再来继续往下看。


3.代码实现
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        //1.计算数组最后一个位置
        int count = -1, i = 0, n = arr.size();
        while(count < n)
        {
            if(arr[i] != 0) count++;
            else count += 2;
            if(count >= n-1) break;
            i++;
        }
        //处理特殊情况
        if(count == n)
        {
            arr[n-1] = 0;
            i--;
            count -= 2;
        }
        //2.逆向填充数组
        while(i >= 0)
        {
            if(arr[i] != 0) arr[count--] = arr[i--];
            else 
            {
                arr[count--] = 0;
                arr[count--] = 0;
                i--;
            }
        }
    }
};

[双指针](一) Leetcode 283.移动零和1089.复写零,LEETCODE,leetcode,算法,职场和发展

4.总结

细节1:count为什么初始化为-1:因为数组下标是从0开始的,从-1开始可以和数组下标对应上,不会越界;从0开始最后又得减掉,后续处理十分麻烦。

细节2:求最后的复写数时,循环中if(count >= n-1) break;:如果此时count已经大过数组的size-1(也就是超出数组的范围),就没有必要再让当前的下标i再加1了。

细节3:nums[] = {8, 4, 5, 0, 0, 0, 0, 7}:这样的数组,我们最后复写出来的结果为{8, 4, 5, 0, 0, 0, 0, 0}因为第三个0,会有一个0复写时越界了,我们之前的算法无法处理这种特殊情况,需要我们手动处理一下:count == nums.size时,将数组的最后一位手动赋值0,最后复写的数的下标i应该-1,而count应该-2(看不懂就画一下图)。

END, THANKS。文章来源地址https://www.toymoban.com/news/detail-718476.html

到了这里,关于[双指针](一) Leetcode 283.移动零和1089.复写零的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode283. 移动零

    难度:简单题 题目 给定一个数组  nums ,编写一个函数将所有  0  移动到数组的末尾,同时保持非零元素的相对顺序。 请注意  ,必须在不复制数组的情况下原地对数组进行操作。 思路: 一开始想,从前往后遍历,遇到0就挪到最后。类似于冒泡的思想,但是这样做的话时

    2024年02月12日
    浏览(80)
  • Leetcode 283.移动零

    给定一个数组  nums ,编写一个函数将所有  0  移动到数组的末尾,同时保持非零元素的相对顺序。 请注意  ,必须在不复制数组的情况下原地对数组进行操作。 示例 1: 示例 2: 提示 : 1 = nums.length = 104 -231 = nums[i] = 231 - 1 进阶: 你能尽量减少完成的操作次数吗? 直接采用快

    2024年02月22日
    浏览(39)
  • Leetcode 283. 移动零

    题目链接 283. 移动零 给定一个数组 nums ,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 示例 1: 示例 2: 这道题目的意思是我们将所有的0都移动到数组的后面,非零的元素放在前面.不过我

    2024年02月08日
    浏览(50)
  • LeetCode283.移动零

     这道题还是很简单的,我用的是双指针,左指针i从头开始遍历数组,右指针j是从i后面第一个数开始遍历,当左指针i等于0的时候,右指针j去寻找i右边第一个为0的数和i交换位置,交换完了就break内层循环,i往后移1位,j又从i的下一位开始,如果i不等于0,就不用进内层循环

    2024年02月12日
    浏览(41)
  • 【每日一题】Leetcode - 283. 移动零

    Leetcode - 283. 移动零 从右向左遍历,遇到0,就将后面所有元素前移,同时更新长度,使其减1,因为移动n次,倒数n位就被0占据,后续操作可忽略 前面的操作,从右向左,每次遇到0移动都要跑半个数组,慢在整体前移; 换个思路,从左向右,记录首个0的位置,将后面的第一

    2024年02月11日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(47)
  • LeetCode 1089. Duplicate Zeros

    Given a fixed-length integer array  arr , duplicate each occurrence of zero, shifting the remaining elements to the right. Note  that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything. Example 1: Example 2: Constraints: 1 = arr.length = 104 0 = arr[i] = 9 这题

    2024年02月11日
    浏览(38)
  • LeetCode每日一题之 复写0

    目录 题目介绍: 算法原理: 特殊位置处理: 代码实现: 题目链接:. - 力扣(LeetCode) 这种对数组元素进行修改,移动的题目我们仍然可以使用双指针法,不过我们按照常规思路从左到右处理数组,不难发现如下这种问题: 当cur指向1时,让dest下一个元素复写cur指向的元素

    2024年04月23日
    浏览(50)
  • 力扣:1089. 复写零

    今日分享一道力扣经典题目,复写0! 题目如下: 题目要求是进行复写0,而且不能超过原数组长度,且只能在原地进行操作! 解决本题最好的方法就是进行双指针方法! 一、双指针算法先 找到最后一个要复写的数 ! 二、然后 从后向前进行完成复写 (因为如果要是从前向

    2024年02月06日
    浏览(27)
  • 【LeetCode】 双指针,快慢指针解题

    1.删除有序数组中的重复项 2.移除元素

    2024年02月11日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包