2024年10月28日练习（双指针算法）

一.11. 盛最多水的容器 - 力扣（LeetCode）

    1.题目描述：

这个题目代表的意思就是数组上每个对应的值就相当于每条垂直线的高度，就相当于短板效应，两

个高度的线会取最短的长度因为那样水才不会漏。而两条线的数组的下标相减就相当于长度，而

容积就是长度乘以高度。而这里就是找容积最高的。

2.算法原理：

    方法一：

        暴力解法，就是将所有情况都过一遍，然后找出容积最大的那种情况，这里用两层for循环即

可解决，就是先固定一条线，然后另一条线走，也就是固定的那条线就是外层循环，另一条线走就

是内层循环。但是这样的时间复杂度就是O(n^2)这样时间就会超时，是错误的。

    方法二：

这是我们利用数组里的一小段分析出来的规律，那么要想找到整个数组就要按照这种规律来，先直

接找一头一尾的容积，然后记录下来：

如果左边指针的数小于右边指针的数那么就左边的加加，然后得到一个新的容积，然后比较一下这

两个容积的大小：

如果右边的数小于左边的数，那么右边减减，得到一个新的容积再去比较：

就这样一步步比较，然后直到两个指针相遇就结束循环，然后找到最大的容积。

3.代码展示：

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

二.202. 快乐数 - 力扣（LeetCode）

1.题目描述：

也就是拆解每一位数然后平方再加在一起就和，然后如果最后这样到1了，那么就是快乐数了，如

果一直循环到不了1，那么就不是快乐数。

现在看两个例子就能更加显而易见了：

这个就是快乐数的循环情况。

这种就是无限循环但始终出现不了一的情况。

这题目的意思也就是我们上面说的那两种情况，就都是会有环出现的

2.算法原理：

总结一下上面讲到的两种情况：

第一种情况就是快乐数的情况，循环里一直是1，而第二种情况是不是快乐数，但其始终会出现循

环的情况。

这图一画就想到了之前做到过的题目就是判断一个链表是否是循环链表的那个题目：

环形链表题解析-CSDN博客

在这里我们仅需要判断一下这个环里面的数是否为1即可，在环形链表的题目中我们判断链表是否

有环，利用的是快慢指针来写的，所以这里我们也可以用快慢双指针。

这里思想不要被限制死了，并不是定义两个真正的指针，这里是利用每次拆分出来的数作为指针来

移动的：

变一次那么slow就变成4，变两次那么fast变成16：

所以接下来的就是利用数来操作快慢双指针的。

3.代码展示：

class Solution {
public:
    int Sum(int n)//用来拆分每位数然后求和
    {
        int sum=0;
        while(n){
            int tmp=n%10;
            sum+=tmp*tmp;
            n/=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow=n,fast=Sum(n);
        while(slow!=fast){
            slow=Sum(slow);//慢指针走一步
            fast=Sum(Sum(fast));//快指针走两步
        }
        //此时退出循环时已经相遇，此时判断一下相遇的值是否为1即可：
        return slow==1;
    }
};