算法——双指针（day2）

目次

 202.快乐数
标题分析：
算法分析：
 代码：
11.盛最多水的容器
标题分析：
算法分析：
代码：

---

 202.快乐数

力扣链接：202.快乐数

标题分析：

   本文中最告急的一句话就是重复平方和过程直到数字变为1，也大概是无穷循环始终稳定1.
  这里我们可以画出示例图来分析。
  

  我们终极可以发现只有两种情况，要么内部循环都为1，要么内部循环不为1.而二者共同点就在于肯定会循环~
  算法分析：

   这里我们还是可以使用双指针的解法——快慢指针~信托各人不会陌生，快慢指针通过慢走一步快走两步的特点可以很快判定出来是否成环（即循环）。而本题我们不须要验证是否循环，只须要在快慢指针相遇的时间（无穷循环中）判定环中数字是否为1即可~
  
 代码：

1. class Solution {
2. public:
3.     //处理平方和
4.     int sumsum(int n)
5.     {
6.         int sum = 0;
7.         while (n)
8.         {
9.             int a = n % 10;
10.             sum += a * a;
11.             n /= 10;
12.         }
13.         return sum;
14.     }
15.     bool isHappy(int n) {
16.         //初始化优先错开
17.         int slow = n;
18.         int fast = sumsum(n);
19.         //快慢指针相遇
20.         while (fast != slow)
21.         {
22.             slow = sumsum(slow);
23.             fast = sumsum(sumsum(fast));
24.         }
25.         return slow == 1;
27.     }
28. };

复制代码

11.盛最多水的容器

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

标题分析：

   

  通过示例图可以我们看出根本盘算为：选择的下标相减 X 两数间最小数
  算法分析：

   

  我们先划出一个小范围，然后实行在该范围内里选出最大容量。我们优先选取两头数，如许可以包管长度是最长的，然后我们再实行收缩范围（拿宽短的实行比力），如许我们可以得出两种结果：
  要么是 长度和宽度都减小了（2---4）,要么是长度减小宽度稳定（5--4）.终极的容量都不如最开始v1（6--4）的大，因此我们可以直接清除4，由于在后续的比力中毫偶然义。
  

  当我们知道规律后就很简单了，列出双指针指向两头。记载每一次所指向的两个数对应的容量，然后两数谁小谁就先缩进一位继续比力，直到相遇。末了我们再对比全部记载的容量选出最大的谁人即可~ 
  代码：

1. class Solution {
2. public:
3.     int maxArea(vector<int>& height) {
4.         int n = height.size();
5.         int left = 0;
6.         int right = n-1;
7.         int sum = 0;
8.         int sum1 = 0;
9.         while(left<right)
10.         {
11.             sum1 = min(height[left],height[right])*(right-left);
12.             if(height[right]>=height[left])
13.             {
14.                 left++;
15.             }
16.             else
17.             {
18.                 right--;
19.             }
20.              sum = max(sum,sum1);
21.         }
22.         return sum;
23.     }
24. };

复制代码