网站建设备案哪家好,成功的个人网站,昆山网站建设书生商友,网页设计的基本原则有哪些复写零原题地址
方法一#xff1a;双指针法
从前向后复写#xff0c;会造成覆盖。所以#xff0c;应该从后向前复写#xff0c;这样我们可以考虑维护一个栈。遍历数组#xff0c;如果遇到非0元素#xff0c;就入栈1次#xff1b;如果遇到0#xff0c;就入栈2次。当栈…复写零原题地址
方法一双指针法
从前向后复写会造成覆盖。所以应该从后向前复写这样我们可以考虑维护一个栈。遍历数组如果遇到非0元素就入栈1次如果遇到0就入栈2次。当栈中的元素个数超出数组的元素个数时把栈中的元素重新从后向前写入数组即可。
如对于数组[1 2 0 0 3 0 4]
1入栈1次[1]
2入栈1次[1 2]
0入栈2次[1 2 0 0]
0入栈2次[1 2 0 0 0 0]
3入栈1次[1 2 0 0 0 0 3]
此时栈中元素个数和数组元素个数相等重新写入数组即可。
再举一个例子对于数组[1 2 0 0 3 0 4 5]
1入栈1次[1]
2入栈1次[1 2]
0入栈2次[1 2 0 0]
0入栈2次[1 2 0 0 0 0]
3入栈1次[1 2 0 0 0 0 3]
0入栈2次[1 2 0 0 0 0 3 0 0]
此时栈中元素个数比数组元素个数多1个需要去掉最后一个0把[1 2 0 0 0 0 3 0]写入数组。
由于不允许开辟O(N)的额外空间我们可以考虑用top来维护栈顶即栈中的有效数据个数模拟出入栈过程。假设数组长度为n当topn时可以继续入栈。
用下标i来记录要复写的元素下标j来记录复写的目标位置。在前面模拟入栈的过程中可以记录最后一个入栈的元素在数组中的下标即i。由于是从后向前复写j要初始化为n-1。
对于栈中元素个数比数组元素个数多一个即topn1的特殊情况最后一个0只需要复写1次其余情况正常复写即可。复写时把[0,i]的元素按照是否为0进行分类非零元素复写1次零复写2次。
// 方法一双指针
class Solution {
public:void duplicateZeros(vectorint arr) {int n arr.size();int top 0; // 记录栈顶int i -1;// 模拟把数组元素放入栈中while (top n){if (arr[i]){top;}else{top 2;}}// i表示要复写的数据// j表示要复写的位置int j n - 1;// 最后放入2个0导致栈中元素比数组多if (top n 1){arr[j--] 0;--i;}// while(j0)也可以但是第一个位置是否复写没有区别while (j 0){arr[j--] arr[i];if (arr[i] 0){arr[j--] 0;}--i;}}
};
