专题一：双指针之移动零，复写零，快乐数

常见的双指针有两种形式⼀种是对撞指针⼀种是左右指针。对撞指针⼀般⽤于顺序结构中也称左右指针。对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。对撞指针的终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是left right 两个指针指向同⼀个位置left right 两个指针错开快慢指针⼜称为⻳兔赛跑算法其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。这种⽅法对于处理环形链表或数组⾮常有⽤。其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快慢指针的思想。快慢指针的实现⽅式有很多种最常⽤的⼀种就是在⼀次循环中每次让慢的指针向后移动⼀位⽽快的指针往后移动两位实现⼀快⼀慢。一.移动零数组划分数组分块)1.题目描述2.算法原理在这道题目中我们可以⽤⼀个cur 指针来扫描整个数组另⼀个dest 指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur 在扫描的过程中遇到的不同情况分类处理实现数组的划分。在 cur 遍历期间使 [0, dest] 的元素全部都是⾮零元素 [dest 1, cur - 1] 的元素全是零[cur,n-1]就是未处理的区间。3.算法步骤a.初始化 cur 0 ⽤来遍历数组 dest -1 指向⾮零元素序列的最后⼀个位置。因为刚开始我们不知道最后⼀个⾮零元素在什么位置因此初始化为 -1 b.cur 依次往后遍历每个元素遍历到的元素会有下⾯两种情况i. 遇到的元素是 0 cur 直接 。因为我们的⽬标是让 [dest 1, cur - 1] 内的元素全都是零因此当 cur 遇到 0 的时候直接 就可以让 0 在 cur - 1的位置上从⽽在 [dest 1, cur - 1] 内ii. 遇到的元素不是 0 dest 并且交换 cur 位置和 dest 位置的元素之后让cur 扫描下⼀个元素。因为 dest 指向的位置是⾮零元素区间的最后⼀个位置如果扫描到⼀个新的⾮零元素那么它的位置应该在 dest 1 的位置上因此 dest 先⾃增 1 dest 之后指向的元素就是 0 元素因为⾮零元素区间末尾的后⼀个元素就是0 因此可以交换到 cur 所处的位置上实现 [0, dest] 的元素全部都是⾮零元素 [dest 1, cur - 1] 的元素全是零。class Solution { public: void moveZeroes(vectorint nums) { for(int cur 0, dest -1; cur nums.size(); cur) if(nums[cur]) // 处理⾮零元素 swap(nums[dest], nums[cur]); } };4.代码运行补充这里只关心非零元素遇到非零就往前挪零元素什么都不做自然就被“留”在了后面所以不是“处理零元素”而是“忽略零元素只处理非零元素”。前置 是先加后用后置 是先用后加。5.算法总结这个⽅法是往后我们学习快排算法的时候数据划分过程的重要⼀步。如果将快排算法拆解的话这⼀段⼩代码就是实现快排算法的核⼼步骤。二.复写零1.题目描述2.算法原理双指针 倒序遍历如果从前往后复写会遇到一个问题复写0会覆盖掉后面的元素。所以需要从后往前操作。如果从前向后进⾏原地复写操作的话由于 0 的出现会复写两次导致没有复写的数被覆盖掉。因此我们选择从后往前的复写策略。但是从后向前复写的时候我们需要找到最后⼀个复写的数因此我们的⼤体流程分两步1.先找到最后⼀个复写的数2.然后从后向前进⾏复写操作。从后往前遍历碰到 0就把后面连续位置都填0;碰到 非0数就把它挪到当前 dest 位置.指针始终同步向前走直到遍历完整个数组。3.算法步骤a. 初始化两个指针 cur 0 dest 0 b. 找到最后⼀个复写的数i. 当 cur n 的时候⼀直执⾏下⾯循环判断 cur 位置的元素:如果是 0 的话 dest 往后移动两位否则 dest 往后移动⼀位。判断 dest 时候已经到结束位置如果结束就终⽌循环如果没有结束 cur 继续判断。c. 判断 dest 是否越界到 n 的位置i. 如果越界执⾏下⾯三步n - 1 位置的值修改成 0 cur 向移动⼀步dest 向前移动两步。d. 从 cur 位置开始往前遍历原数组依次还原出复写后的结果数组i. 判断 cur 位置的值如果是 0 dest 以及 dest - 1 位置修改成 0 dest - 2 如果⾮零 dest 位置修改成 0 dest - 1 ii. cur-- 复写下⼀个位置。class Solution { public: void duplicateZeros(vectorint arr) { //先找到最后一个数 int cur 0,dest -1,n arr.size(); //因为从后面复写所以cur和dest的位置要进行说明 while(curn) { if(arr[cur]) dest; else dest 2; if(destn-1) break;//看dest是否结束怕越界 cur; } //处理一下边界问题 if(destn) { arr[n-1] 0; cur--; dest - 2; } //从后面完成复写操作 while(cur0) { if(arr[cur]) arr[dest--] arr[cur--]; else { arr[dest--] 0; arr[dest--] 0; cur--; } } } };4.代码运行三.快乐数1.题目描述方便大家理解这个题目用两个例子快乐数题⽬分析:为了⽅便叙述将对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平⽅和这⼀个操作记为 x 操作题⽬告诉我们当我们不断重复 x 操作的时候计算⼀定会死循环死的⽅式有两种情况⼀⼀直在 1 中死循环即 1 - 1 - 1 - 1......情况⼆在历史的数据中死循环但始终变不到 1由于上述两种情况只会出现⼀种因此只要我们能确定循环是在情况⼀中进⾏还是在情况⼆中进⾏就能得到结果。简单证明题目给一个正整数每次把它替换成各位数字的平方和重复这个过程。如果能变成 1就是快乐数如果进入循环且不是 1就不是快乐数。你的几行笔记对应的是a. 一次变化后的最大值一个数经过一次变化各位平方和之后能有多大9² × 位数如果位数固定比如 10 位数最大值是 81×10 810哪怕你给一个超大数比如 10 个 9平方和也不会超过 810简单理解就是任何数变化一次后结果都会落在 1~810 之间b. 为什么一定会循环因为变化结果永远在 1~810 之间总共有 810 种可能的结果。变化的过程就是一个不断往下走的过程如果你连续走 811 步一共只有 810 个“不同的目的地”那么根据鸽巢原理抽屉原理至少有一个数被重复走到一旦某一步重复后面就会无限循环c. 可以用快慢指针因为一定会进入循环不是到 1 结束就是进其他循环。这和判断链表是否有环是一类问题。快慢指针快指针一次走两步慢指针一次走一步如果相遇说明有环判断相遇点是不是12.算法原理利用平方和会将大数缩小到有限区间的特点把数的变化过程抽象成一个有环链表再用快慢指针判环。判断环中是否包含 1即可得出快乐数。3.算法思路根据上述的题⽬分析我们可以知道当重复执⾏ x 的时候数据会陷⼊到⼀个「循环」之中。⽽快慢指针有⼀个特性就是在⼀个圆圈中快指针总是会追上慢指针的也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1 那么这个数⼀定是快乐数如果相遇位置不是 1的话那么就不是快乐数。class Solution { public: int bitsum(int n) { int sum 0; while(n) { int t n%10; sum t*t; n n/10; } return sum; } bool isHappy(int n) { int slow n,fast bitsum(n); while(slow!fast) { slow bitsum(slow); fast bitsum(bitsum(fast)); } return slow1; } };4.代码运行5.补充知识如何求⼀个数 n 每个位置上的数字的平⽅和。a. 把数 n 每⼀位的数提取出来循环迭代下⾯步骤i. int t n % 10 提取个位ii. n / 10 ⼲掉个位直到 n 的值变为 0 b. 提取每⼀位的时候⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平⽅和tmp tmp t * t鸽巢原理鸽巢原理也叫抽屉原理就是说如果你有n 个鸽巢但是有n1 只鸽子那么至少有一个鸽巢里有至少 2 只鸽子。再举两个例子比如说你有 5 个抽屉却有 6 件衣服那么至少有一个抽屉里塞了 2 件衣服一年只有 365 天或 366 天如果有 366 个人至少有两个人在同一天过生日。