【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器

超、凢脫俗 2024-03-23 22:04 58阅读 0赞

## ![5f1fe013d7dd4c0aa37a8349a775ee02.png][] ##

## 202. 快乐数 ##

[202. 快乐数![icon-default.png?t=N6B9][icon-default.png_t_N6B9]https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/21dfc2593a9c4dcead203e35237e30a4.png][202. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_happy-number]

### 题目： ###

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

**「快乐数」** 定义为：

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

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

![d10a253e5e3447ff9a62b9f7a6c2a230.png][]

### 解题思路： ###

> 我们先通过这两个测试用例来看看是什么情况
> 
> ![0770281d50a84541abebd3f39fec5380.png][]
> 
> 我们发现不管是19还是2都会形成一个环状结构（19的环状结构内都是1）
> 
> 那这样我们就可以使用快慢指针来操作！！！
> 
> 定义一个slow和fast，slow一次走一步，fast一次走两步
> 
> 他们一定会相遇的，只不过相遇的时候会有两种情况，相遇的数是1或者不是1

> 那为什么一定会形成环状结构呢？我们来简单论证一下！
> 
> 鸽巢原理：就是当n个巢穴，n+1个鸽子的时候，一定至少有一个巢穴的鸽子>1
> 
> 我们注意一下n的范围，n最大为2的31次方，也就是2亿多（10位数）,那我们将它放大10个9（也就是最大的那个10位数，我懒得打9了），也就是说，它最多就是10个9，经过f操作最大就是9^2\*10=810,也就是相当于我们最多有810个位置，我们处理813次的f，肯定会有重复的数出现！
> 
> 那同理：
> 
> ![1285d4fba8cb42a39a0b483669240842.png][]

### 解题代码： ###

class Solution {
    public:
        int f(int n)
        {
            int arr[11] = { 0 };
            int i = 1;
            for (int i = 1; i < 11; ++i)
            {
                if (n < 10)
                {
                    arr[i] = n;
                    break;
                }
                arr[i] = n % 10;
                n = n / 10;
            }
            int x = 0;
            for (int i = 1; i < 11; ++i)
            {
                x += (arr[i] * arr[i]);
            }
            return x;
        }
        bool isHappy(int n) {
            //快慢双指针
            int slow = n;
            int fast = n;
            //更新slow和fast
            slow = f(slow);
            fast = f(fast);
            fast = f(fast);
            if (slow == fast && slow == 1)return true;
            while (slow != fast)
            {
                //更新slow和fast
                slow = f(slow);
                fast = f(fast);
                fast = f(fast);
            }
            if (slow == 1)
                return true;
            else
                return false;
        }
    };

## 11. 盛最多水的容器 ##

[11. 盛最多水的容器![icon-default.png?t=N6B9][icon-default.png_t_N6B9]https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ad377e4558d64b20b8ac96a9c5a0b34c.png][11. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_container-with-most-water]

### 题目描述： ###

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

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

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

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

![6423d88e7ea9400ca38d6a126b2dec38.png][]

### 解题思路： ###

> 体积V=h\*w,当我们利用双指针从左右两边向中间逼近，w一定是减小的，只有当h增大才可能增大

### 解题代码： ###

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(v,ret);
                if(height[left] < height[right]) left++;
                else right--; 
            }
            return ret;
        }
    };

### ![db397bb4c89b4436bd42e228132b27d2.gif][] ###

[5f1fe013d7dd4c0aa37a8349a775ee02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9e5362cde4eb4d5bba057bfeb9122088.png
[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[202. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_happy-number]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/21dfc2593a9c4dcead203e35237e30a4.png
[d10a253e5e3447ff9a62b9f7a6c2a230.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2308f527f1e34ed4beca774fe09f15c1.png
[0770281d50a84541abebd3f39fec5380.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d60bf6f1bd1449b88ba8ffc8d25e9621.png
[1285d4fba8cb42a39a0b483669240842.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9819dc904cd34575a086d719a03f48d6.png
[11. _icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_leetcode.cn_problems_container-with-most-water]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ad377e4558d64b20b8ac96a9c5a0b34c.png
[6423d88e7ea9400ca38d6a126b2dec38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bfb5f37bd5814188bb48fd31c106c02c.png
[db397bb4c89b4436bd42e228132b27d2.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e0f837aef56e41f1a64cae6046745c72.png