[Algorithm][双指针][复写零]详细解读 + 代码实现

• 题目链接

1. 先找到最后一个"复写"的数
   • 先判断cur位置的值
   • 决定dest向后移动一步或者两步
   • 处理边界情况，if(num[n - 2] == 0)
     • num[n - 1] = 0
     • cur--;
     • dest -= 2;
   • 判断dest是否到末尾
   • cur++;
2. "从后向前"完成复写操作

void DuplicateZeros(vector<int>& arr) 
{
    int cur = 0, dest = -1;
    int n = arr.size();

    // 找最后一个"复写"位置
    while(cur < n)
    {
        if(arr[cur])
        {
            dest++;
        }
        else
        {
            dest += 2;
        }

        if(dest >= n - 1)
        {
            break;
        }

        cur++;
    }

    // 处理一下边界情况
    if(dest == n)
    {
        arr[n - 1] = 0;
        cur--;
        dest -= 2;
    }

    // 从后往前复写
    while(cur >= 0)
    {
        if(arr[cur])
        {
            arr[dest--] = arr[cur--];
        }
        else
        {
            arr[dest--] = 0;
            arr[dest--] = 0;
            cur--;
        }
    }
}