做一个新公司网站要多少钱,开源cms下载,wordpress支持PHP吗,深圳网络营销Problem: 1089. 复写零 文章目录 题目解析算法原理分析找到最后一个复写的位置从后往前进行复写操作 代码展示 题目解析 首先我们来分析一下本题的题目意思 可以看到题目中给到了一个数组#xff0c;意思是让我们将数组中的零元素都复写一遍#xff0c;然后将其余的元素向后平… Problem: 1089. 复写零 文章目录 题目解析算法原理分析找到最后一个复写的位置从后往前进行复写操作 代码展示 题目解析 首先我们来分析一下本题的题目意思 可以看到题目中给到了一个数组意思是让我们将数组中的零元素都复写一遍然后将其余的元素向后平移 光就上面这样来看还是不太形象我们通过画图来分析一下通过下图我们可以看到凡是0的都复写了两遍凡不是0的都复写了一遍 但是呢题目中很明显地讲到只能让我们在数组上进行就地操作但是就我们上面的操作而言则是在另外开辟了一块数组的空间 那在下面我们就去考虑一下在数组原地的操作 可以看到在下面我使用到了双指针的操作若是cur遍历到0的话就进行两次的复写操作不过呢大家可以看到在第一次的复写操作完成之后【2】被覆盖了但是这个【2】是我们需要的那也就造成了一定的问题 那么反应快的同学可以意识到如果要进行覆盖操作的话就需要 从后往前 进行遍历操作才可以
算法原理分析 好接下去呢我们就来分析一下解决本题的思路 找到最后一个复写的位置
上面说到是要从后往前开始做复写操作那么第一步我们所要做的就是找到最后一个复写的位置即让这个dest指向最后的0 那要怎么去找呢头一次尝试幻灯片≧ ﹏ ≦ 可以分为以下几步
判断cur位置的值决定dest走一步还是两步判断dest是否到达末尾决定cur是否
,,,,,, 但是呢就上面这样的逻辑去走的话其实是不对的因为我们还未考虑到特殊的边界情况 即下面的这种情况当测试用例的倒数第二个数为0的时候此时dest又刚好到这个位置那么就需要向后移动两步此时就造成了越界问题 所以此时我们应该要考虑处理一下这个边界问题 因为倒数第二个数为0那么对其进行复写操作的话最后一个也是0我们将其做一个修改即可不过呢两个指针cur和dest也需要去做一个变化cur前移一位即可dest因为做了复写操作所以需要前移两位 从后往前进行复写操作 上面呢我们已经找到了需要复写的最后一个位置那接下去我们就要正式开始复写操作了 这一块的话就不做动画演示了读者可以试着自己去手动模拟一下也就是从我们上面所找到的cur位置开始慢慢地向前遍历然后去做复写操作即可将数一一地复写到dest所在的位置如果arr[cur]为0的话那我们就需要考虑复写两次了 代码展示 最后来展示一下整体的代码 class Solution {
public:void duplicateZeros(vectorint arr) {// 1.找到复写的最后一个位置// (1) 判断cur位置的值决定dest走一步还是两步// (2) 判断dest是否到达末尾决定cur是否int dest -1;int cur 0;int sz arr.size();while(dest sz){if(arr[cur]) dest;else dest 2;if(dest sz - 1)break;cur;}// 2.判断边界的情况if(dest sz){arr[dest - 1] 0;cur--;dest - 2;} // 3.从右往左复写0while(cur 0){if(arr[cur]) arr[dest--] arr[cur--];else{arr[dest--] 0;arr[dest--] 0;cur--;}} }
};
下面是运行后的结果
