算法题——002 复写零

Han.miracle

发布于 2025-12-23 09:31:52

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

地址：复写零

这个题的思路：

双指针法

1.先找到这个要被复制的最后一个点

1.先判断 cur 位置的值

prev 如果是数组的-1索引开始的到最后就是他所在的位置是先加后赋值，这个索引已经被占了的

但是如果是prev 为 0 开始的话，就是先复制后加复制0 这个题

2. 决定 dest 向后移动一步或者两步
3.判断一下 dest 是否已经到结束为止
4.cur ++
5.处理边界情况(也就是越界 array.length 和 array.length-1为 0 )；

仅需把array.length -1 和 array.length 这个位置上的全给变成 0

cur--；

dest-2;

这三部提前处理一下

2.然后一次往前遍历复制

非0 的就复制一次，cur 赋值该数

0 的复制两次，cur 赋值，prev 记录的是这个要复制的这个数字

注意：

prev 如果是数组的-1索引开始的到最后就是他所在的位置是先加后赋值，这个索引已经被处理的

但是如果是prev 为 0 开始的话，就是先复制后加

1. `prev` 初始化为 `-1`（先加后赋值）

角色：prev 代表 “当前已处理空间的最后一个索引”（初始时无空间，故为 -1）。
处理第一个元素 0（需要占 2 个位置）：
- 先加：prev += 2 → prev = 1（此时prev指向第 2 个位置，即0扩展后占用的最后一个位置）。
- 后赋值：从后向前复写时，arr[prev--] = 0 → 先写arr[1] = 0，再prev=0；继续arr[prev--] = 0 → 写arr[0] = 0，prev=-1。
处理第二个元素 1（占 1 个位置）：
- 先加：prev += 1 → prev = 0（指向1应占的位置）。
- 后赋值：arr[prev--] = 1 → 写arr[0] = 1？不对，这里需要注意：从后向前复写时，prev的 “加” 是在第一阶段计算最终位置，第二阶段复写时是从最终位置向前推。
实际流程中，第一阶段计算完prev最终会停在2（[0,0,1]的最后一个索引），第二阶段从2开始向前复写：arr[2] = 1（prev=1），再写两个0到arr[1]和arr[0]，逻辑完全匹配。

2. `prev` 初始化为 `0`（先复制后加）

角色：prev 代表 “下一个待填充的位置起点”（初始时从第 0 位开始）。
处理第一个元素 0：
- 先复制：arr[prev] = 0（prev=0），arr[prev+1] = 0（prev=0）。
- 后加：prev += 2 → prev=2（下一个待填充位置是第 2 位）。
处理第二个元素 1：
- 先复制：arr[prev] = 1（prev=2）。
- 后加：prev += 1 → prev=3（超出数组长度，但不影响结果）。

这里第一种主播出现了严重的越界问题，也是调了很长时间的代码

if (arr[cur] == 0) {
    arr[prev--] = 0;  // 第一次赋值
    arr[prev] = 0;    // 第二次赋值 - 这里可能prev已经<0！
} else {
    arr[prev] = arr[cur];  // 这里可能prev已经<0！
}
prev--;
if(prev < 0){  // 检查太晚了！
    break;
}

在这里在第一次pre-- 的时候就应该考虑越界问题，如果prev = 0 ,prev-- 不就等于-1 了

边界处理：1

// 处理边界问题
if (prev == arr.length) {
    arr[--prev] = 0;
    cur--;
} else if (prev == arr.length - 1) {
    // 也需要处理这种情况
    arr[prev] = 0;
    prev--;
    cur--;
}

2：

3：

   if(prev == arr.length ){
            arr[--prev] = 0;
            cur--;
            prev--;
        }

import java.util.Arrays;

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int prev = -1;

        // 第一次遍历: 找到最后一个需要被复制的元素的索引 cur
        // 循环结束后，cur 将指向最后一个需要处理的元素
        while (cur < arr.length) {
            if (arr[cur] == 0) {
                prev += 2;
            } else {
                prev++;
            }
            if (prev >= arr.length - 1) {
                break;
            }
            cur++;
        }

        // 第二次遍历的写指针，从数组末尾开始
        int write_ptr = arr.length - 1;

        // 边界处理：如果 prev 溢出，说明 cur 指向的0只能被复制一次
        if (prev > arr.length - 1) {
            arr[write_ptr--] = 0; // 在数组末尾手动放置一个0
            cur--; // 从 cur 的前一个元素开始第二次遍历
        }

        // 第二次遍历：从后向前，将元素复制到正确的位置
        // cur < arr.length 的检查是为了防止数组只有一个元素且为0的情况
        for (; cur >= 0 && cur < arr.length; cur--) {
            if (arr[cur] == 0) {
                // 如果是0，则复制两次
                if (write_ptr >= 0)
                    arr[write_ptr--] = 0;
                if (write_ptr >= 0)
                    arr[write_ptr--] = 0;
            } else {
                // 如果不是0，则复制一次
                if (write_ptr >= 0)
                    arr[write_ptr--] = arr[cur];
            }
        }
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除

索引