安庆建设工程造价网站,网站每年都要续费吗,云南建设厅网站安全处,品牌网站建设策划复写零 .习题链接题目描述算法原理初始值步骤1步骤2我的答案: . 习题链接
复写零
题目描述
给你一个长度固定的整数数组 arr #xff0c;请你将该数组中出现的每个零都复写一遍#xff0c;并将其余的元素向右平移。
注意#xff1a;请不要在超过该数组长度的位置写入元素… 复写零 .习题链接题目描述算法原理初始值步骤1步骤2我的答案: . 习题链接
复写零
题目描述
给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。
注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。 输入arr [1,0,2,3,0,4,5,0] 输出[1,0,0,2,3,0,0,4] 解释调用函数后输入的数组将被修改为[1,0,0,2,3,0,0,4] 算法原理
这道题用到的算法是双指针算法,我们定义两个指针:cur和dest,这两个指针需要帮助我们完成两件事:
找到最后一个复写的数从后往前进行复写操作
初始值
cur的初始值为0,因为它需要从零开始遍历数组中的数 dest的初始值为-1,因为它表示复写后的最后一位数的地址
步骤1
步骤1是利用双指针中的快慢指针来完成:
判断当前cur的值是否为0如果cur为零,dest就往后走两步,不为零则走一步判断当前dest是否已经走到数组的末尾,如果没有,则执行下一步cur
步骤2
判断dest是否已经越界,如果已经越界,执行下面步骤 a. 将n-1的位置修改为0 b. cur向前倒退一步,即cur–;dest倒退两步从cur位置开始遍历数组,依次进行复写操作判断cur当前的值: a. 如果是0,dest以及dest-1的位置修改为0,然后dest-2; b. 如果非0,dest位置修改为cur位置的值,dest-1; c.cur–,然后复写下一个数
我的答案:
class Solution {public void duplicateZeros(int[] arr) {int cur 0;int dest -1;int n arr.length;//1.找到复写的最后一个数for(;destn-1;cur){if(arr[cur]0){dest2;}else{dest;}if(destn-1) break;}//2.从后往前进行复写//a.处理特殊情况if(destn-1){arr[n-1]0;cur--;dest-2;}while(cur0){if(arr[cur]0){arr[dest--]0;arr[dest--]0;}else{arr[dest--]arr[cur];}cur--;}}
}
