谷哇网站建设,wordpress英文版改中文,网络维护工作怎么样,软件开发兼职平台个人主页#xff1a;Lei宝啊
愿所有美好如期而遇 力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试#xff1f;力扣提供海量技术面试资源#xff0c;帮助你高效提升编程技能#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://le…
个人主页Lei宝啊
愿所有美好如期而遇 力扣LeetCode官网 - 全球极客挚爱的技术成长平台备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/duplicate-zeros/
算法原理
双指针法不一定是说就要使用指针只是一种形象的说法在数组中我们一般将数组下标当做指针这道题目我们仍然定义cur以及dest当我们将cur和dest都定义在数组开始时按照逻辑执行下去那么遇到0时后面的部分值会被覆盖所以我们不能从左向右走而是从右向左走但是这样的话我们又怎么知道cur和dest的位置呢我们看图示
图示
正常从左向右走图示 2就被覆盖了但是我们先走下去(不考虑覆盖)看看cur和dest的最终位置 当dest到达右边界时停止。
也就是说我们可以先遍历找到指针位置再倒过来复写图示 我们还有一种特殊情况就是dest越过边界到了size那么我们就要先将数组下标为size-1的位置置0因为size位置不能置0是越界的然后我们dest - 2cur--接下来正常走就好。 代码
class Solution {
public:void duplicateZeros(vectorint arr) {int cur 0;int dest -1;int n arr.size();while(cur n){if(arr[cur] ! 0){dest;}else{dest 2;} if(dest n - 1){break;}cur;}if(dest n - 1){arr[n - 1] 0;dest - 2;cur--;}while(cur 0){ if(arr[cur] ! 0){arr[dest--] arr[cur--];}else{arr[dest--] 0;arr[dest--] 0;cur--;} } }
};
