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

目录

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

前言

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

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

快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列
结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快
慢指针的思想。

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

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

1. 快乐数（medium）

题目描述：
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：

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

示例 1：

输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8²= 100
1² + 0²+ 0² = 1

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 231 – 1

2. 解法

思路：
可以把题目中的两种情况当成一种情况来看，就是一直在死循环

1. 对于情况一：⼀直在 1 中死循环
2. 对于情况二：在历史的数据中死循环，但始终变不到 1

为什么会死循环？

题目所给数据范围是小于整型（int）的最大值 2³¹-1=2147483647,这里我们们不难发现最大值的位数是 10，那么我们可以用一个十位数的最大值来变换，即 9999999999，那么它经过变换得到的值就是 9² * 10 = 810 ，那么经过所有变换的结果就会在区间 [1, 810] 之间；
根据【鸽巢原理】，⼀个数变化 811 次之内，必然会在一个循环中有重复。
因此，可以⽤「快慢指针」来解决。

解题方法:

1. ProductSum 函数：

• 这个函数计算一个整数的每个位上数字的平方和。
• 通过不断地对整数取模 10 来获取其最后一位数字，然后将其平方并累加到 sum 变量中。
• 每次迭代，整数都通过整除 10 来移除最后一位数字。
• 当整数变为 0 时，函数返回累加的和 sum。

2. isHappy 函数：

• 使用“快慢指针”技术来检测循环。
• slow 和 fast 初始时都指向 n。
• slow 每次移动一步，即计算当前数字的平方和。
• fast 每次移动两步，即连续计算两次平方和。
• 如果 n 是一个快乐数，slow 和 fast 最终都会达到 1。
• 如果 n 进入循环，slow 和 fast 会在循环中的某个点相遇（即它们的值相等）。
• 如果 slow 和 fast 相等且等于 1，则 n 是快乐数。
• 算法中使用了 do-while 循环而不是 while 循环，以确保至少执行一次循环体（即至少计算一次ProductSum），即使 slow 和 fast 初始时就相等。

复杂度

时间复杂度: O(logN)
空间复杂度: O(1)

C++算法代码：

class Solution {
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;
    }
};

java算法代码：

class Solution
{
	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;
	 }
}

3. 盛水最多的容器（medium）

题目描述：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

4. 解法

解法一（暴力求解)(会超时):

算法思路:
枚举出能构成的所有容器，找出其中容积最大的值。

容器容积的计算方式:
设两指针 i , j，分别指向水槽板的最左端以及最右端，此时容器的宽度为j - i
容器的高度由两板中的短板决定，因此可得容积公式︰v = (j - i) * min(height[il, height[j])

算法代码：

class Solution {
public:
	int maxArea(vector<int>& height) {
		int n = height.size();
		int ret = 0;
		// 两层 for 枚举出所有可能出现的情况
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				// 计算容积，找出最⼤的那⼀个
				ret = max(ret, min(height[i], height[j]) * (j - i));
			}
		}
		return ret;
	}
};

解法二（对撞指针）：

算法思路：
设两个指针 left , right 分别指向容器的左右两个端点,此时容器的容积 : v = (right - left) * min( height[right], height[left])
容器的左边界为height[left],右边界为 height[right] 。
为了方便叙述,我们假设「左边边界」小于「右边边界」. 如果此时我们固定一个边界,改变另一个边界,水的容积会有如下变化形式：

• 容器的宽度⼀定变小
• 由于左边界较小,决定了⽔的⾼度.如果改变左边界,新的水面高度不确定,但是⼀定不会超过右边的柱子高度,因此容器的容积可能会增大.
• 如果改变右边界,无论右边界移动到哪里,新的水面的高度⼀定不会超过左边界,也就是不会超过现在的水面高度,但是由于容器的宽度减小,因此容器的容积⼀定会变小的.
• 由此可见,左边界和其余边界的组合情况都可以舍去.所以我们可以 left++ 跳过这个边界,继续去判断下⼀个左右边界.

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

C++ 算法代码：

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;
	}
};

Java 算法代码：

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;
	}
}