【算法刷题】Day7

本文介绍: 我们这里可以运用**“双指针”**的方法这里的双指针，并不是 c 语言中的指针，而是用数组模拟的指针。看到题目，首先看一下题干的要求，是在原数组内进行操作，平切保持非零元素的相对顺序。遇到非零元素：swap(dest+1,cur);首先先看题干，把数组中每个零都复写一遍，其他元素水平右移，并且就地修改。这个时候，数组就被 cur 和 dest 分成了三个区间。dest：已处理的区间内，在非零元素的最后一个位置。我们要定义两个“指针”，cur 和 dest。[ dest+1, cur-1 ] 0元素。

文章 目录

283. 移动零
1089. 复写零

283. 移动零

在这里插入图片描述
原题链接

看到题目，首先看一下题干的要求，是在原数组内进行操作，平切保持非零元素的相对顺序

这个时候我们看到了示例一：
[ 0, 1, 0, 3,12 ]
这个时候输出成为了
[ 1, 3, 12, 0, 0 ]

我们这里可以运用**“双指针”**的方法这里的双指针，并不是 c 语言中的指针，而是用数组模拟的指针

首先：
我们要定义两个“指针”，cur 和 dest
cur：从左往右扫描数组，遍历数组
 des t：已处理的区间内，在非零元素的最后一个位置

这个时候，数组就被 cur 和 des t 分成了三个区间
[ 0, des t ] 存放非零元素
[ des t+1, cur-1 ] 0元素
[ cur, n-1 ] 未处理的元素

然后：
cu r 从前往后遍历
 遇到 0 元素：cur++
遇到非零元素：swap(des t+1,cur); d es t++; cur++;

public void moveZeroes(int[] nums) {
        int cur = 0;
        int dest = -1;
        for (; cur &lt; nums.length; cur++) {
            if (nums[cur] != 0) {
                dest++;
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
            }
        }
    }

在这里插入图片描述

1089. 复写零

在这里插入图片描述
原题链接

首先先看题干，把数组中每个零都复写一遍，其他元素水平右移，并且就地修改
这里我们需要用到双指针，从后往前进行复写

但是这里我们需要先遍历一遍，找到要复写的数字

方法：

定义cur 和 dest
cur：遍历数组
dest：目标的位置
先用双指针找到要复写的数字
 遇到 0，dest += 2;
这里会遇到复写两个0，但是最后一个0超出数组范围
 这个时候我们需要把数组最后一个位置置为0，dest 的位置-2，cur–
从后往前遍历

public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.length;
        //1、找到最后一个需要复写的数
        while (cur < n) {
            if (arr[cur] == 0) {
                dest += 2;
            }else {
                dest += 1;
            }
            if (dest &gt;= n-1) {
                break;
            }
            cur++;
        }
        //2、处理边界情况
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        //3、从后向前完成复写操作
        while (cur &gt;= 0) {
            if(arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            }else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }