虚拟币交易网站源码,高端网站建设哪些好,无锡网站推广经理,电子商务网站建设教程试卷目录 题目
思路
代码 题目
给你一个长度固定的整数数组 arr #xff0c;请你将该数组中出现的每个零都复写一遍#xff0c;并将其余的元素向右平移。
注意#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改#xff0c;不要从函数返回…目录 题目
思路
代码 题目
给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。
注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。 示例 1
输入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]
示例 2
输入arr [1,2,3]
输出[1,2,3]
解释调用函数后输入的数组将被修改为[1,2,3]
思路
题目依然是对数组元素原地进行修改所以可以采用双指针的思路来解题一个负责遍历一个负责更改所以可以设立两个指针cur和destcur负责遍历数组dest负责更改数据如果非零dest就复写一遍如果是0dest就往后写入两个0。 可通过观察发现如果从前往后进行遍历更改就会导致数据被覆盖。从而破坏了数组的完整性。
因为在对数组进行修改时多余的元素会从数组的队尾出所以可以从后往前去更改数组。
所以我们可以先去找到最后一个需要复写的数这样就可以确定数组的最后一个元素的值从而可
以更好的控制写入时不发生溢出。 如上所示当dest走到头时此时cur的位置就是最后一个需要复写的数。
但当以下情况出现时dest会出现越界的情况如果直接去访问就会导致越界问题。 所以当碰到越界以后需要进行一个特殊处理当destn时说明越界了也说明最后一个复写的元素绝对是0才会导致dest越界所以直接把下标为n-1也就是数组最后一个元素的值修改为0然后让dest-2同时让cur往前移动一位。此时第一步就完成了。接下来就可以修改数组数据了。 先判断cur对应的元素是否为0如果不为0 dest修改该位置元素然后向前移动一位如果为0 将该位置元素改为0然后向前把前一个位置元素也改为0。
代码
class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,dest-1,narr.size();while(curn)//找最后一个需要复写的下标{if(arr[cur]) dest;else dest2;if(destn-1) break;cur;}if(destn){dest-2;--cur;arr[n-1]0;}while(cur0){if(arr[cur])arr[dest--]arr[cur];else {arr[dest--]0;arr[dest--]0;}cur--;}}
};