【算法刷题】Day7

283. 移动零

原题链接

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

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

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

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

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

然后：
cur 从前往后遍历
遇到 0 元素：cur++
遇到非零元素：swap(dest+1,cur); dest++; cur++;

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

1089. 复写零

原题链接

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

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

方法：

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

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 >= n-1) {break;}cur++;}//2、处理边界情况if (dest == n) {arr[n - 1] = 0;cur--;dest -= 2;}//3、从后向前完成复写操作while (cur >= 0) {if(arr[cur] != 0) {arr[dest--] = arr[cur--];}else {arr[dest--] = 0;arr[dest--] = 0;cur--;}}}