【优选算法篇】2

【优选算法篇】2

这道题如果没理解好题目，是很难的，但理解题目就容易啦

意思就是：一个数组长度是固定的，里面的元素，只要是0，就需要在原有的基础上，在0的后面多加一个0，以此类推，不为0的数就得往后移动，最后保持原有的数组长度不变，像上图第一个示例的5和0就是因为前面0要写两个，所以要被去掉~

class Solution 
{
public:
    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--;
            }
        }
    }
};    

我这里实现主要是先遍历一遍数组，如果arr【cur】为非0，则dest走一步，cur++，如果为0，dest则走两步，直到dest到达最后一位，则break，此时cur的位置则为0复写后数组的最后一位数。

注意：在这里需要注意越界问题，如下图：

有一个0越界，直接n-1位置变为0，然后cur--，dest-=2即可！！！