1089. 复写零

Difficulty
easy
Tags
双指针
URL
https://leetcode.cn/problems/duplicate-zeros/
Star
给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。
要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
示例 1：
输入：[1,0,2,3,0,4,5,0]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
示例 2：
输入：[1,2,3]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,2,3]
提示：
  1. 1 <= arr.length <= 10000
  1. 0 <= arr[i] <= 9
通过次数31,952提交次数53,080

法 1 前缀 0

思路
统计每一位前面有几个0，然后该位数值就要往后偏移几位，如果该位是0的话，还需要往后再写一位。
以为涉及到修改，所以倒着往回遍历，同时注意修改的时候下标是否越界
题解
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        # 统计每一位前面有几个 0
        prefix = [0] * (len(arr)+1)
        for i in range(1, len(prefix)):
            prefix[i] = prefix[i-1] + int(prefix[i-1]==0)       

        for i in range(len(arr)-1, -1, -1):
						# i 位置的值需要 写入 到 idx 位置上
            idx = i + prefix[i]
            if idx >= len(arr):
                continue
            
            arr[idx] = arr[i]
            if arr[i] == 0 and idx + 1 < len(arr):
                arr[idx + 1] = 0
            
        return arr
优化：先保存一份 arr 副本，然后利用 一个变量 offset 来统计 偏移量，该偏移量的计算方式其实就是前缀中 0 的个数。
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        arr_ = [i for i in arr]
        # 偏移量，初始为 0
        offset = 0

        i = 0
        while i < len(arr):
            arr[i] = arr_[i-offset]
            if arr[i] == 0 and i < len(arr)-1:
                i += 1
                arr[i] = 0
                offset += 1
            i += 1

法 1 用栈模拟

思路
遍历 arr, 当arr[i] == 0时，往栈中放两个数字，否则，把当前元素放入栈中。
当栈的长度为 len(arr)时候，停止，此时栈中的元素就是答案。再倒腾回去即可。
题解
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        stack = []
        idx = 0
        for i in range(0, len(arr)):
            if arr[i] == 0:
                stack.append(0)
                stack.append(0)
            else:
                stack.append(arr[i])

            if len(stack) > len(arr):
                while len(stack) > len(arr):
                    stack.pop()
                break
                
        
        for i in range(len(arr)-1, -1, -1):
            arr[i] = stack.pop()

法2 双指针模拟栈

思路
我们可以假设已经通过原数组 arr 处理出最终的目标数组 ans，起始使用指针 i 指向原数组的开头位置，使用指针 j指向目标数组的开头位置。
然后开始同时从前往后处理，默认情况下，两个指针每次往后移动一位，当在原数组中出现 arr[i] = 0 时，根据题意，我们需要在目标数组 ans[j] 后面复写多一位，因此此时让 j 多走一位。
当 j 走到的位置已超出数组长度，此时 i 也停在了该被截断的位置的下一位。
此时我们先将 i 和 j 同时往回走一步，确保 i 落在真正的截断后的位置，但需要注意，由于 j 在之前的往前走逻辑中可能会走两步，因此 j 在往回走一步后仍可能在数组以外的位置。
然后考虑如何在 i 和 j 所在位置开始「往回」赋值：每次将 arr[i] 赋值给 arr[j]（需要确保 j 下标合法），由于 i 必然不会出现在 j 的后面（即不会出现 j < i），因此不会出现值被提前覆盖的问题。因此通常情况下，我们可以不断的同时减少 i 和 j，并将 arr[i] 赋值给 arr[j]。当出现 arr[i] = 0 时，我们需要额外让 j 往前多走一步，并将该位置置为 0，来实现目标数组「复写零」的效果。
当 i 指针越过开头的位置，说明已完成从 arr 到 ans 的转换。
题解
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        i, j = 0, 0
        while j < len(arr):
            if arr[i] == 0:
                j += 1
            i += 1
            j += 1

        i -= 1
        j -= 1

        # 此时 j 任然有可能 == len(arr), 因为最后一次 j 可能走了两步
        # 所以这里纠正一下
        if j == len(arr):
            j -= 1
            arr[j] = 0
            i -= 1
            j -= 1
        while j >= 0:
            arr[j] = arr[i]
            if arr[i] == 0:
                j -= 1
                arr[j] = 0
                
            j -= 1
            i -= 1