• 算法——双指针(day1)


    283.移动零

    力扣链接:283.移动零

    题目解析:

    从示例1中我们可以看出在把0移到数组末尾的过程中,1,3,12这三者的相对顺序是没有发生改变的。而这题的核心就在于利用双指针的思想进行数组划分。

    首先我们先对两个指针(利用数组下标)赋予职能。

    dest:在已处理区间内,非0元素的最后一个位置

    cur:遍历扫描数组

    当我们使用双指针后就会发现数组已经被我们三块区间~

    • [0,dest]:非0区间
    • [dest+1,cur-1]:0区间
    • [cur,n-1]:未处理区间

    算法过程解析:

    下面我们来演示一遍~

    最开始cur是要承担遍历数组的角色,所以指向首个元素。而dest则是用来作为非0元素的分界线,因此要指向-1位置,若指向0则违背自己职能。

    一开始cur遍历到0,仍保持3区间稳定指向下一位。当指向1(非0元素)时,我们就需要在非0元素区间内把1插入,那么dest就要后移一位给1位置。

    最后二者交换,cur继续指向下一位置遍历。我们可以发现,在cur不断扫描元素的过程中,我们都是在为了稳定3大区间(数组划分)而进行调整。

    我们把这个调整过程用代码总结:

    • 当cur遇0:cur++(继续遍历)
    • 当cur遇到非0:dest++,swap(nums[dest],nums[cur]),cur++

    代码:

    1. class Solution {
    2. public:
    3. void moveZeroes(vector<int>& nums) {
    4. for(int dest = -1, cur = 0;cursize();cur++)
    5. {
    6. if(nums[cur])
    7. {
    8. swap(nums[++dest],nums[cur]);
    9. }
    10. }
    11. }
    12. };

    总结:

    双指针核心就在于通过赋予相应的职能去划分数组,待处理区间暂且不谈,关键就在于处理区间中的非0区间和0区间,两区间做到真正的数组划分。

    1089.复写零

    力扣链接:1089.复写零

    题目描述:

     因为题目要求是就地而非异地,那么我们额外开辟一个数组的做法就作废了。

    如果按照老规矩先设置双指针,在从左往右复写的过程中会遇到数值覆盖这种问题。

    所以我们不妨换个思路,既然从前往后会遇到数值覆盖,那我们从后往前试试。

    算法过程解析:

    假设我们指向最后一个复写的位置时,开始从后往前遍历。

    具体规则为:

    • cur遇非零:dest复写cur指向的数值。然后dest与cur一起前进一位继续遍历。
    • cur遇零:dest连续复写两次零,每次复写完前进一位,共计两位。cur前进一位。 

    所以我们的思路就变得清晰起来:

    • 首先找到最后一个复写的位置
    • 其次处理一下边界情况(特殊越界)
    • 最后完成复写操作

    而如何找到我们需要的复写位置呢?

    这同样可以用到双指针来帮助我们~顺带说一下要注意的边界情况~

    • cur遇到非零:dest前进一位,cur++
    • cur遇到零:dest前进两位,cur++

    而我们条件满足的需求只是dest到达数组中n-1或n的位置,只要满足这个条件就行了就不用再cur++(一开始就是因为这个错误调试半天。。。)

    当dest指向n位置说明数组越界了,基本上也只有最后一位复写才会发生越界所以我们可以直接在数组中n-1的位置上复写一个0,然后dest-=2,cur--解决越界问题。其实就是人为复写一次,后面就是正常利用循环复写了。

    代码:

    1. class Solution {
    2. public:
    3. void duplicateZeros(vector<int>& arr) {
    4. int dest = -1;
    5. int cur = 0;
    6. int n = arr.size();
    7. //找第一个复写0
    8. while (cur
    9. {
    10. if (arr[cur] != 0)
    11. {
    12. dest++;
    13. }
    14. else
    15. {
    16. dest += 2;
    17. }
    18. if(dest>=n-1) break;
    19. cur++;
    20. }
    21. //边界情况
    22. if(dest==n)
    23. {
    24. arr[n-1] = 0;
    25. dest-=2;
    26. cur--;
    27. }
    28. //开始复写
    29. while(cur>=0)
    30. {
    31. if(arr[cur]!=0)
    32. {
    33. arr[dest--] = arr[cur--];
    34. }
    35. else
    36. {
    37. arr[dest--] = 0;
    38. arr[dest--] = 0;
    39. cur--;
    40. }
    41. }
    42. }
    43. };

    总结:

    本题核心仍是双指针,区别就在于是把从前往后的遍历改为从后往前的遍历,这种方法可以有效避免数组覆盖问题~

  • 相关阅读:
    数组逆序.
    网络安全工程师面试题整理
    【Spring】Spring MVC 拦截器的使用
    blender导出UE4用的FBX骨骼动画
    逢人必推的4款实用软件,国产良心,相遇不易
    多线程系列(十四) -一文带你搞懂线程池技术
    本周大新闻|苹果MR已进行Pre-EVT测试,Quest 2涨价100美元
    Linux:动静态库
    基于Sider-chatgpt3.5-编写一个使用springboot2.5连接elasticsearch7的demo程序,包括基本的功能,用模板方法
    python+flask计算机毕业设计web的智慧云医疗的设计与实现(程序+开题+论文)
  • 原文地址:https://blog.csdn.net/fax_player/article/details/140455392