题目链接

题目:

分析:

• 就地对数组进行操作, 肯定是需要双指针的 
• 那么我们从左往右进行复写, 定义一个cur用来遍历数组, 一个dest用来修改数组的值, 如果cur下标的值不为零, 那么将cur的值写到dest位置, cur++, dest++; 如果cur下标的值为0, 那么就将dest下标的值写为0, dest++, 再将dest的值写为0, dest再++;如果这样做, 就会将数组原来的值覆盖为0 , 就会丢失数据
• 从左往右不行, 那么我们就想到用从右往左的方式复写, 这样就不会覆盖掉数组原来的值

思路:

1. 先找到最后一个复写的数, 因为如果数组中有零, 题目要求不能超出数组的长度, 所以所有的数据不可能都被复写, 所以我们要找到最后一个需要复写数
   1. 我们要模拟一下复写的过程, 所以定义双指针, 一个cur 遍历数组, 找到最后一个被复写的数, 一个dest, 模拟复写的位置, 这个位置不能超过数组的长度
   2. 如果cur == 0, dest++,cur++;
   3. 如果cur != 0, dest +=2;
   4. 特殊:如果最后一个被复写的数是0, 那么dest可能会超过数组的下标, 那么就会越界访问, 所以当dest == 数组的长度时, 我们直接跳过复写这个0, 即, arr[arr.length-1] = 0, dest-= 2, cur--;
2. 这样, 我们就需要对cur前面的数依次进行复写, 如果cur下标的值不为零, 那么将cur的值写到dest位置, cur--, dest--; 如果cur下标的值为0, 那么就将dest下标的值写为0, dest--, 再将dest的值写为0, dest再--, cur--;

代码:

class Solution {public void duplicateZeros(int[] arr) {int cur = 0;int dest = -1;for(cur = 0;cur<arr.length;cur++){if(arr[cur] == 0){dest += 2;}else dest++;if(dest >= arr.length-1 ){break;}}if(dest == arr.length){arr[arr.length -1] = 0;dest -=2;cur--;}while(cur >= 0){if(arr[cur] == 0){arr[dest--] = 0;arr[dest--] = 0;cur--;}else arr[dest--] = arr[cur--];}}
}