网站开发软件有哪,做公益网站赚钱吗,西安网站建设创意,海外公司网站 国内做备案复写零OJ链接#xff1a;1089. 复写零 - 力扣#xff08;LeetCode#xff09; 题目#xff1a; 解法#xff08;原地复写-双指针#xff09;#xff1a; 算法思路#xff1a; 如果「从前向后」进⾏原地复写操作的话#xff0c;由于 0 的出现会复写两次#xff0c;导致…复写零OJ链接1089. 复写零 - 力扣LeetCode 题目 解法原地复写-双指针 算法思路 如果「从前向后」进⾏原地复写操作的话由于 0 的出现会复写两次导致没有复写的数「被覆 盖掉」。因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候我们需要找到「最后⼀个复写的数」因此我们的大体流程分两 步 i. 先找到最后⼀个复写的数 ii. 然后从后向前进行复写操作。 算法流程 a. 初始化两个指针 cur 0 dest 0 b. 找到最后⼀个复写的数 i. 当 cur n 的时候一直执行下面循环 • 判断 cur 位置的元素: ◦ 如果是 0 的话 dest 往后移动两位 ◦ 否则 dest 往后移动一位。 • 判断 dest 时候已经到结束位置如果结束就终止循环 • 如果没有结束 cur 继续判断。 c. 判断 dest 是否越界到 n 的位置 i. 如果越界执行下面三步 1. n - 1 位置的值修改成 0 2. cur 向移动⼀步 3. dest 向前移动两步。 d. 从 cur 位置开始往前遍历原数组依次还原出复写后的结果数组 i. 判断 cur 位置的值 1. 如果是 0 dest 以及 dest - 1 位置修改成 0 dest - 2 2. 如果非零 dest 位置修改成 0 dest - 1 ii. cur-- 复写下一个位置。 C:
class Solution {
public:void duplicateZeros(vectorint arr){// 1. 先找到最后⼀个数int cur 0, dest -1, n arr.size();while (cur n){if (arr[cur]) dest;else dest 2;if (dest n - 1) break;cur;}// 2. 处理⼀下边界情况if (dest n){arr[n - 1] 0;cur--; dest - 2;}// 3. 从后向前完成复写操作while (cur 0){if (arr[cur]) arr[dest--] arr[cur--];else{arr[dest--] 0;arr[dest--] 0;cur--;}}}
}; 运行结果 PS看到这里了码字不易给个一键三连鼓励一下吧有不足或者错误之处欢迎在评论区指出
