双指针练习题复写零

本文主要是介绍双指针练习题复写零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

复写零

给你一个长度固定的整数数组 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 <= arr.length <= 104
• 0 <= arr[i] <= 9

1.题目解析

2.讲解算法原理

解法: 双指针算法，先根据“异地”操作，然后优化成双指针下的“就地”操作

（1）异地操作来实现

以示例1来画图阐述：

（2）双指针下的“就地”操作

从左到右，发现不行。

开始从右向左尝试，发现可以

总结思路

1. 先找到最后一个“复写”的数;
2. "从后向前”完成复写操作

待完成的问题：如何找到最后一个“复写”的数？

答：也是一个双指针算法。

dest判断是否从前往后遍历完这个数组的时候，对cur这个下标指向的数判断是否为0。
cur不为0，cur++, dest++;
cur为0，cur++, dest。

用双指针书写代码运行的过程

1. 先判断cur位置的值
2. 决定dest向后移动一步或者两步
3. 判断一下dest是否已经到结束位置
4. cur++

画图阐述找到最后一个“复写”的数的过程

存在的特殊情况

解决: 对边界情况进行处理一下

存在当dest在n的位置时，n-1的位置设为0，cur - -,dest -= 2

3.编写代码

class Solution {public void duplicateZeros(int[] arr) {int cur = 0, dest = -1, 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--;}}}
}

运行结果：

这篇关于双指针练习题复写零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---