去哪个网站可以做写手,网站开发报价单,如何做网站搭建api接口,设置wordpress文章图片不显示[双指针] Leetcode 283.移动零和1089.复写零
移动零
283. 移动零 1.题意分析
(1) 给你一个数组#xff0c;将数组中的所有0移动到数组的末尾
(2) 保证非0元素在数组中相对位置不变
(3) 在原数组中操作
2.解题思路
由于题目要求我们移动数组内容#xff08;也就是交换两…[双指针] Leetcode 283.移动零和1089.复写零
移动零
283. 移动零 1.题意分析
(1) 给你一个数组将数组中的所有0移动到数组的末尾
(2) 保证非0元素在数组中相对位置不变
(3) 在原数组中操作
2.解题思路
由于题目要求我们移动数组内容也就是交换两个数的位置所以我们很容易想到双指针解法。
解法双指针
定义两个“指针”(left 和 right)right遍历整个数组遇到0就交换两个数的位置。
nums[right] 0right;nums[right] ! 0swap(nums[right], nums[left]), right, left示例1[0, 1, 0, 3, 12] 请先自己尝试实现代码再来继续往下看。 3.代码实现
class Solution {
public:void moveZeroes(vectorint nums) {for(int left 0, right 0; right nums.size(); ){if(nums[right] ! 0) swap(nums[left], nums[right]);else right;}}
};4.总结
细节1right的大小由我们自己在if-else控制并不需要写入循环。
细节2right的大小超过数组的size即为遍历完整个数组。
复习零
1089. 复写零 1.题意分析
(1) 给你一个长度固定的数组将数组中的0再次写一遍即为在0后再加一个0
(2) 其余的数向右平移
(3) 超过数组长度终止写入元素
(4) 在原数组上进行操作
2.解题思路
题目要求我们进行复写0即需要知道两个数的位置所以可以使用两个“指针”一前一后判断0添加0。
解法双指针
由于数组空间是固定的我们首先需要知道最后一个数的位置然后倒着进行修改数组。
nums[i] 0count 2;nums[i] ! 0count;count nums.size-1break;i;i即为新数组的最后一个数我们在倒着写回数组。
nums[i] 0nums[count] 0, count[count-1] 0, i--, count - 2;nums[i] ! 0nums[count] nums[i], i--, count--。示例1
nums[] [1, 0, 2, 3, 0, 4, 5, 0] 注意处理这样的数组: nums[] {8, 4, 5, 0, 0, 0, 0, 7}
请先自己尝试实现代码再来继续往下看。 3.代码实现
class Solution {
public:void duplicateZeros(vectorint arr) {//1.计算数组最后一个位置int count -1, i 0, n arr.size();while(count n){if(arr[i] ! 0) count;else count 2;if(count n-1) break;i;}//处理特殊情况if(count n){arr[n-1] 0;i--;count - 2;}//2.逆向填充数组while(i 0){if(arr[i] ! 0) arr[count--] arr[i--];else {arr[count--] 0;arr[count--] 0;i--;}}}
};4.总结
细节1count为什么初始化为-1因为数组下标是从0开始的从-1开始可以和数组下标对应上不会越界从0开始最后又得减掉后续处理十分麻烦。
细节2求最后的复写数时循环中if(count n-1) break;如果此时count已经大过数组的size-1(也就是超出数组的范围)就没有必要再让当前的下标i再加1了。
细节3nums[] {8, 4, 5, 0, 0, 0, 0, 7}这样的数组我们最后复写出来的结果为{8, 4, 5, 0, 0, 0, 0, 0}因为第三个0会有一个0复写时越界了我们之前的算法无法处理这种特殊情况需要我们手动处理一下count nums.size时将数组的最后一位手动赋值0最后复写的数的下标i应该-1而count应该-2(看不懂就画一下图)。
END, THANKS。
