双指针专题：快乐数与盛水最多的容器

双指针专题：快乐数与盛水最多的容器

一、快乐数

1. 题目解析

LeetCode 202. 快乐数

2. 原理分析

快乐数有两种情况：

1. 数最后变成 1。

2. 无限循环但不是 1。

这两种情况都可以抽象成带环链表的问题。

解法：快慢双指针

1. 定义快慢指针。
2. 慢指针每次向后移动一步，快指针每次向后移动两步。
3. 判断相遇时候的值。

3. 代码实现

class Solution {
public:
    int BitSum(int n) // 返回每一位数上的平方和
    {
        int sum = 0;
        while (n) {
            int m = n % 10;
            sum += m * m;
            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 slow == 1;
    }
};

二、盛水最多的容器

1. 题目解析

LeetCode 11. 盛最多水的容器

2. 原理分析

解法一：暴力枚举 时间复杂度 O(N^2)，会超时。

解法二：利用单调性，使用双指针

在这一组数中拿出一个区间 6，2，5，4。我们先用最两边的数算一个容积，然后小的那个固定住（也就是 4），向内枚举。如果遇到比它小的数（也就是 2），高度跟宽度都减小，v 减小；如果遇到比它大的数（也就是 5），高度不变（还是 4），宽度减小，v 减小。所以我们可以直接舍去小的那一个，在研究下一个区间。

3. 代码实现

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