算法:双指针

十念  金牌会员 | 2024-8-30 10:06:11 | 来自手机 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题

主题 567|帖子 567|积分 1701

标题:复写零

固然标题说必须要就地但是我们可以先试试异地然后再想办法优化成当地
算法解说:

异地

可以界说两个指针让它们分别指向当地和异地,当当地指针指向零时这时候就往异地写入两个零其余就照常写,说完异地做法那我们应该如何优化成绩地做法呢?
就地

当地也要界说两个指针

往前
cur往前每走一步时dest也会跟一步当cur指向0时dest会指向cur前面一个而且把它变成零那这样cur前面永远都是零了。
既然往前遍历不行那今后呢?
今后
要思量 cur 和 dest 应该分别指向哪里。如果 cur 依然指向0,dest 指向-1,那和前向遍历是一样的,没有区别。但从标题中可以看到,输出结果的末了一个数字是4,而不是0。因此,我们可以将 cur 指向4的位置。cur 既然在前向遍历时指向第一个元素,那在后向遍历时指向输出结果的末了一个元素也是公道的。这样,cur 的位置已经确定了。那么 dest 应该指向哪里呢?
dest 是指向0照旧5,或者其他位置?这个位置不好判断。不妨直接开始遍历。当 cur 指向4时,dest 应该复写4的位置;当 cur 指向0时,dest 应该将4和5都复写为0。这样我们可以推断出 dest 的位置。
找末了一个被复写数的位置
我们希望找到复写后数组的末了一个元素,但直接继承今后遍历显然不行。尽管通过标题我们知道末了一个元素的值,但是遍历的竣事条件是什么呢?因此,我们必要改变计谋:从往前遍历转为使用“快慢指针”方法。
快指针比慢指针走得更快。当快指针到达数组的末尾或空位时,慢指针应该指向精确的位置。这样我们就可以确保通过快慢指针的方法定位到数组复写后指定的末了一个元素。
但是,必要注意的是,这种方法也是有限制的。具体来说,当 cur 指向0时,dest 必要往前走两步,而在其他情况下,dest 只必要往前走一步。
界限问题
在力扣上的标题只要是野指针就会报错,那在上面我们说过“当快指针到达数组的末尾或空位时”其中只要指针指向空位就会报错,那该如何办理呢?
当 cur 指向0时,如果剩下的空间不足2个位置,会导致 dest 出现越界。这时我们可以直接将末了一个位置修改为0。这背后的缘故起因是,如果空间不足两个位置,那末了一个位置必然是0,不然 dest 就不会越界。因此,我们可以放心地将其修改为0。
一旦末了一个位置被复写为0,意味着复写操纵已经完成。这时,cur 应该向前移动一位,dest 也必要向前移动。不过,由于复写0必要占用两个位置,以是 dest 应该减去2。
代码实现:

  1. class Solution
  2. {
  3. public:
  4.     void duplicateZeros(vector<int>& arr)
  5.     {
  6.       // 找到最后一个数
  7.       int len = arr.size();
  8.       int cur = 0;
  9.       int dest = -1;
  10.       while(cur < len)
  11.       {
  12.         if(arr[cur])
  13.         {
  14.             dest++;
  15.         }
  16.         else
  17.         {
  18.             dest+=2;
  19.         }
  20.         if(dest >= len - 1)
  21.         {
  22.             break;
  23.         }
  24.         cur++;
  25.       }
  26.       
  27.       if(dest == len)
  28.       {
  29.         arr[len - 1] = 0;
  30.         dest-=2;
  31.         cur--;
  32.       }
  33.       //进行复写
  34.        while(cur >= 0)
  35.     {
  36.         if(arr[cur])
  37.         {
  38.             arr[dest--] = arr[cur--];
  39.         }
  40.         else
  41.         {
  42.             arr[dest--] = 0;
  43.             arr[dest--] = 0;
  44.             cur--;
  45.         }
  46.     }
  47.     }
  48. };
复制代码
 
 
 
 

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

十念

金牌会员
这个人很懒什么都没写!

标签云

快速回复 返回顶部 返回列表