【算法优选】双指针专题——贰

野性酷女 2024-04-17 10:40 79阅读 0赞

#### 文章目录 ####

*  ?前言
 *  ?\[快乐数\](https://leetcode.cn/problems/happy-number/)
 *   *  ?题目描述
     *  ?题⽬分析：
     *  ?算法思路：
     *  ?代码实现：
 *  ?\[盛水最多的容器\](https://leetcode.cn/problems/container-with-most-water/)
 *   *  ?题目描述
     *  ?算法思路：
     *  ?代码实现
 *  ?\[有效三角形个数\](https://leetcode.cn/problems/valid-triangle-number/)
 *   *  ?题目描述
     *  ?算法思路：
     *  ?代码实现：
 *  ⭕总结

## ?前言 ##

常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针  
对撞指针：⼀般⽤于顺序结构中，也称左右指针。

*  对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
 *  对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

> left == right （两个指针指向同⼀个位置）  
> left > right （两个指针错开）

快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

这种⽅法对于处理环形链表或数组⾮常有⽤。其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：

*  在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢

## ?[快乐数][Link 1] ##

### ?题目描述 ###

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

*  对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
 *  然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
 *  如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

*  示例 1：  
    输入：n = 19  
    输出：true  
    解释：  
    12 + 92 = 82  
    82 + 22 = 68  
    62 + 82 = 100  
    12 + 02 + 02 = 1
 *  示例 2：  
    输入：n = 2  
    输出：false  
    解释：（这⾥省去计算过程，只列出转换后的数）  
    2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16  
    往后就不必再计算了，因为出现了重复的数字，最后结果肯定不会是 1

class Solution {
        
        public boolean isHappy(int n) {
        
    
        }
    }

### ?题⽬分析： ###

为了⽅便叙述，将「对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平⽅和」这⼀个操作记为x 操作；  
题⽬告诉我们，当我们不断重复 x 操作的时候，计算⼀定会「死循环」，死的⽅式有两种：

*  情况⼀：⼀直在1 中死循环，即1 -> 1 -> 1 -> 1…
 *  情况⼆：在历史的数据中死循环，但始终变不到1

由于上述两种情况只会出现⼀种，因此，只要我们能确定循环是在「情况⼀」中进⾏，还是在「情况⼆」中进⾏，就能得到结果

***简单证明：***

1.  经过⼀次变化之后的最⼤值 9^2 \* 10 = 810 ( 2^31-1=2147483647 。选⼀个更⼤的最⼤ 9999999999)，也就是变化的区间在 \[1, 810\] 之间；
2.  根据「鸽巢原理」，⼀个数变化 811 次之后，必然会形成⼀个循环；
3.  因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决

### ?算法思路： ###

根据上述的题⽬分析，我们可以知道，当重复执⾏ x 的时候，数据会陷⼊到⼀个「循环」之中。⽽「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1，那么这个数⼀定是快乐数；如果相遇位置不是 1 的话，那么就不是快乐数

***补充知识：***  
如何求⼀个数n每个位置上的数字的平⽅和。

1.  把数 n 每⼀位的数提取出来：  
    循环迭代下⾯步骤：

> int t = n % 10 提取个位；  
> n /= 10 ⼲掉个位；

直到 n 的值变为 0 ；

1.  提取每⼀位的时候，⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平⽅和

> tmp = tmp + t \* t

### ?代码实现： ###

class Solution
    {
        
        // 返回 n 这个数每⼀位上的平⽅和
        public int bitSum(int n) {
        
            int sum = 0;
            while(n != 0) {
        
                int t = n % 10;
                sum += t * t;
                n /= 10;
            }
            return sum;
        }
        public boolean isHappy(int n) {
        
            int slow = n;
            int fast = bitSum(n);
            while(slow != fast) {
        
                //走一步
                slow = bitSum(slow);
                //走两步
                fast = bitSum(bitSum(fast));
            }
            return slow == 1;
        }
    }

## ?[盛水最多的容器][Link 2] ##

### ?题目描述 ###

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height\[i\]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

***说明：你不能倾斜容器。***

*  示例 1：  
    输入：\[1,8,6,2,5,4,8,3,7\]  
    输出：49  
    ![在这里插入图片描述][410933689a62423882999d928ba7e923.png]解释：图中垂直线代表输入数组 \[1,8,6,2,5,4,8,3,7\]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 *  示例 2：  
    输入：height = \[1,1\]  
    输出：1

class Solution {
        
        public int maxArea(int[] height) {
        
    
        }
    }

### ?算法思路： ###

设两个指针 left ， right 分别指向容器的左右两个端点，此时容器的容积

v = (right - left) \* min( height\[right\], height\[left\])

容器的左边界为 height\[left\] ，右边界为 height\[right\] 。为了⽅便叙述，我们假设「左边边界」⼩于「右边边界」。

如果此时我们固定⼀个边界，改变另⼀个边界，⽔的容积会有如下变化形式：

*  容器的宽度⼀定变⼩。
 *  由于左边界较⼩，决定了⽔的⾼度。如果改变左边界，新的⽔⾯⾼度不确定，但是⼀定不会超过右边的柱⼦⾼度，因此容器的容积可能会增⼤。
 *  如果改变右边界，⽆论右边界移动到哪⾥，新的⽔⾯的⾼度⼀定不会超过左边界，也就是不会超过现在的⽔⾯⾼度，但是由于容器的宽度减⼩，因此容器的容积⼀定会变⼩的。

由此可⻅，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下⼀个左右边界。

当我们不断重复上述过程，每次都可以舍去⼤量不必要的枚举过程，直到 left 与 right 相遇。期间产⽣的所有的容积⾥⾯的最⼤值，就是最终答案

### ?代码实现 ###

public class Solution {
        
        public int maxArea(int[] height) {
        
            int left = 0, right = height.length - 1, ret = 0;
            while(left < right) {
        
                int v = Math.min(height[left], height[right]) * (right - left);
                ret = Math.max(ret, v);
                if(height[left] < height[right]) {
        
                    left++;
                } else {
        
                    right--;
                }
            }
            return ret;
        }
    }

## ?[有效三角形个数][Link 3] ##

### ?题目描述 ###

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

*  示例 1:  
    输入: nums = \[2,2,3,4\]  
    输出: 3  
    解释:有效的组合是:  
    2,3,4 (使用第一个 2)  
    2,3,4 (使用第二个 2)  
    2,2,3
 *  示例 2:  
    输入: nums = \[4,2,3,4\]  
    输出: 4

class Solution {
        
        public int triangleNumber(int[] nums) {
        
    
        }
    }

### ?算法思路： ###

先将数组排序。我们固定⼀个「最⻓边」，然后在⽐这条边⼩的有序数组中找  
出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤「对撞指针」来优化。  
设最⻓边枚举到 i 位置，区间 \[left, right\] 是 i 位置左边的区间（也就是⽐它⼩的区  
间）：

*  如果 nums\[left\] + nums\[right\] > nums\[i\] ：

> ▪ 说明 \[left, right - 1\] 区间上的所有元素均可以与 nums\[right\] 构成⽐ nums\[i\]⼤的⼆元组  
> ▪ 满⾜条件的有right - left 种  
> ▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕，right-- ，进⼊下⼀轮判断

*  如果 nums\[left\] + nums\[right\] <= nums\[i\] ：

> ▪ 说明 left 位置的元素是不可能与 \[left + 1, right\] =位置上的元素构成满⾜条件 的⼆元组  
> ▪ left 位置的元素可以舍去， left++ 进⼊下轮循环

### ?代码实现： ###

class Solution {
        
        public int triangleNumber(int[] nums) {
        
            // 1. 优化：排序
            Arrays.sort(nums);
            // 2. 利⽤双指针解决问题
            int ret = 0, n = nums.length;
            // 先固定最⼤的数
            for(int i = n - 1; i >= 2; i--)  {
        
                // 利⽤双指针快速统计出符合要求的三元组的个数
                int left = 0;
                int right = i - 1;
                while(left < right) {
        
                    if(nums[left] + nums[right] > nums[i]) {
        
                        ret += right - left;
                        right--;
                    } else {
        
                        left++;
                    }
                }
            }
            return ret;
        }
    }

## ⭕总结 ##

关于《【算法优选】双指针专题——贰》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！一起加油

[Link 1]: https://leetcode.cn/problems/happy-number/
[Link 2]: https://leetcode.cn/problems/container-with-most-water/
[410933689a62423882999d928ba7e923.png]: https://img-blog.csdnimg.cn/410933689a62423882999d928ba7e923.png
[Link 3]: https://leetcode.cn/problems/valid-triangle-number/