【优选算法篇】2----复写零

---------------------------------------begin---------------------------------------

这道算法题相对于移动零，就上了一点点强度咯，不过照旧很容易理解的啦~
题目解析：

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

讲解算法原理：

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

编写代码：

1. class Solution
2. {
3. public:
4.     void duplicateZeros(vector<int>& arr)
5.     {
6.         int cur = 0, dest = -1;
7.         int n = arr.size();
8.         while (cur < n)
9.         {
10.             if (arr[cur])
11.                 dest++;
12.             else
13.                 dest += 2;
14.             if (dest >= n - 1)
15.                 break;
16.             cur++;
17.         }
18.         if (dest == n)
19.         {
20.             arr[n - 1] = 0;
21.             cur--;
22.             dest -= 2;
23.         }
24.         while (cur >= 0)
25.         {
26.             if (arr[cur])
27.             {
28.                 arr[dest--] = arr[cur--];
29.             }
30.             else
31.             {
32.                 arr[dest--] = 0;
33.                 arr[dest--] = 0;
34.                 cur--;
35.             }
36.         }
37.     }
38. };   

复制代码

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

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

------------------------------------end--------------------------------------------


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。