【算法专题--双指针算法】leecode-202. 快乐数(medium)、leecode-11. 盛最多水的容器(medium)

---

🍁你好，我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ，故事既有了开头，就要画上一个完美的句号，让我们一起加油

---

---

目录

• 前言
• 1. 快乐数（medium）
• 2. 解法
• 3. 盛水最多的容器（medium）
• 4. 解法
• • 解法一（暴力求解)(会超时):
  • 解法二（对撞指针）：

    ---

    前言

    双指针

    常见的双指针有两种形式，一种是对撞指针，⼀种是左右指针。

    对撞指针：一般用于顺序结构中，也称左右指针。

    • 对撞指针从两端向中间移动。一个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼

      近。

    • 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循

      环），也就是：

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

          快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列

          结构上移动。

          这种方法对于处理环形链表或数组非常有用。

          其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快

          慢指针的思想。

          快慢指针的实现方式有很多种，最常用的⼀种就是：

          • 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

            1. 快乐数（medium）

            题目描述：

            编写一个算法来判断一个数 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

            提示：

            1 public: int ProductSum(int n) { int sum = 0; while(n) { int temp = n % 10; sum += temp*temp; n /= 10; } return sum; } bool isHappy(int n) { int slow = n,fast = n; // 快慢指针，找环的相遇位置 do { slow = ProductSum(slow); fast = ProductSum(ProductSum(fast)); }while(slow != fast); // 如果相遇时是 1 就是快乐数 return slow == 1; } }; public int bitSum(int n) // 返回 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, fast = bitSum(n); while (slow != fast) { slow = bitSum(slow); fast = bitSum(bitSum(fast)); } return slow == 1; } } public: int maxArea(vector int n = height.size(); int ret = 0; // 两层 for 枚举出所有可能出现的情况 for (int i = 0; i