双指针练习题复写零

妖狐艹你老母 2024-05-06 21:22 58阅读 0赞

![v2-10e484c65d4a26c01ba06722af2483a9\_720w][v2-10e484c65d4a26c01ba06722af2483a9_720w]

[复写零][Link 1]

给你一个长度固定的整数数组 `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.题目解析 ##

![image-20240208110427330][]

## 2.讲解算法原理 ##

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

### （1）异地操作来实现 ###

以示例1来画图阐述：

![image-20240213132342202][]

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

**从左到右，发现不行。**

![image-20240213143930111][]

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

![image-20240213204947485][]

### 总结思路 ###

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

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

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

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

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

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

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

![image-20240213212823830][]

**存在的特殊情况**  
![image-20240213220159191][]

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

> 存在当`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--;
                }
            }
        }
    }

![image-20240213224315655][]

**运行结果：**  
![image-20240213224415405][]

[v2-10e484c65d4a26c01ba06722af2483a9_720w]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/824a22c3593a469a9195206978d2372c.png
[Link 1]: https://leetcode.cn/problems/duplicate-zeros/
[image-20240208110427330]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/0329f6ec32234403860f42c83ef15557.png
[image-20240213132342202]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/7df61058f968485eb6002658490345b0.png
[image-20240213143930111]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/2db5550a61e44cab9ad65df535388598.png
[image-20240213204947485]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/24d28fd18d7d4b9193a84c6846ee41be.png
[image-20240213212823830]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/ddc2d8a7a8e546f898f0c9184a41180f.png
[image-20240213220159191]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/88eb100dd37849558bd2adb7c1480a08.png
[image-20240213224315655]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/8ded065f89fc45a0b8c2c17dc5bb83bb.png
[image-20240213224415405]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/ed5123a221f844c0a24ce42003bb3adf.png