电商网站管理,四川建设公共查询平台,seo专业术语,天天外链目录
1. 复写零
2. 算法原理
一般情况下
改为就地操作#xff1a;从左到右#xff08;错误#xff09;
从右到左
总结一下解决方法#xff1a;
如何找到最后一个复写的数
特殊情况 完整步骤#xff1a;
3. 代码 1. 复写零 题目链接#xff1a;1089. 复写零 - 力…目录
1. 复写零
2. 算法原理
一般情况下
改为就地操作从左到右错误
从右到左
总结一下解决方法
如何找到最后一个复写的数
特殊情况 完整步骤
3. 代码 1. 复写零 题目链接1089. 复写零 - 力扣LeetCodehttps://leetcode.cn/problems/duplicate-zeros/description/ 2. 算法原理 其实本题严格来说是一题半模拟半双指针的题目 一般情况下 我们可以先进行异地操作然后再优化成为双指针下的就地操作 当Cur遇到非0元素的时候直接写下来当遇到0的时候就需要写两遍..... 改为就地操作从左到右错误 将两个指针定义到一个数组上 但是我们发现当cur到达第一个0时dest执行两次写入0将原本2的值给覆盖掉了那么整个数组都会出现错误所以从左到右这个方法是不可以的 从右到左 那我们来试试从右到左能否成功 因为是从右到左所以我们将dest指向最后一个数cur指向最后一个复写的数以示例1为例就是指向4 如果cur当前指向的值不为0那么就直接把cur指向的值写入dest再同时-- 如果cur当前指向的值为0那么cur往左移动一位dest移动2位 然后我们发现从右到左这种方法是可以的 总结一下解决方法 1. 先找到最后一个复写的数 2. 以从右到左的顺序完成复写操作 如何找到最后一个复写的数 双指针算法 1. 定义一个cur指向数组里第一个数的位置dest指向-1的位置 因为要把dest定义为结果中最后一个的位置因此我们只需要判断dest是否跑到最后一个位置就可以了 然后按照下面的步骤来重复进行 然后就找到最后一个复写的数了 特殊情况 当查找最后一个复写的数时cur为0时我们会发现会出现访问越界的问题会造成内存泄漏的情况 解决方法也很简单我们直接将4这个位置也就是n-1变为0然后再进行cur--dest-2 完整步骤 1. 先找到最后一个复写的数 2. 处理特殊情况 3. 以从右到左的顺序完成复写操作 3. 代码
class Solution {
public:void duplicateZeros(vectorint arr) {//1. 先找到最后一个复写的数int cur0,dest-1,narr.size();while(curn){//先判断cur位置的值//不为0dest往后移动1步为0移动2步if(arr[cur]) dest;else dest2;//判断一下dest是否已经到达结束位置if(destn-1) break;//n为size在数组最后一个位置的下一个位置//curcur;} //2. 处理特殊情况 //如果dest越界if(destn){arr[n-1]0;cur--;dest-2;}//3. 以从右到左的顺序完成复写操作while(cur0){//如果cur当前指向的值不为0那么就直接把cur指向的值写入dest再同时--if(arr[cur]) arr[dest--]arr[cur--];else{//为0要写2遍//然后cur往左移动一位dest移动2位arr[dest--]0;arr[dest--]0;cur--;}}}
}; 未完待续~
