双指针_快乐数

快乐数

题目链接：快乐数

内容：

思路1：

对一个数不断执行这个过程，会有两个结果

1.变为1

2.不为1并无限循环。

其实第一种情况也可以看成无限循环，只不过循环的这组数据全是1.

而第二种情况 循环的这组数据的值每个都不一样，循环到起点值又会重新循环。

 

所以我们用两个快慢指针，两指针相遇时退出循环，此时指针的值如果为1就是快乐数。

1.把这个过程用funct函数实现

2.进行一次funct相当于移动到下一个值，slow是第一个值，fast第二个值。slow每次走一次，fast走两次，直到相遇。

代码实现

class Solution {
public:
    int funct(int n)
    {
        int sum=0;
        while (n) 
         {
            int i = n % 10;
            sum+=i*i;
             n /= 10;
        }
            return sum;
    }
    bool isHappy(int n) 
    {
        int slow=n,fast=funct(n);
        while(slow!=fast)
        {
            slow=funct(slow);
            fast=funct(fast);
            fast=funct(fast);            
        }
        return slow==1;
    }
};

思路2：

题目中n的值最大为2^31-1也就是2,147,483,647 。在其范围的1,999,999,999经过funct后的值(sum)是最大的即730。

也就是说经过731次循环还没结束的话就不是快乐数了。

代码实现：

class Solution {
public:
int funct(int n)
    {
        int sum=0;
        while (n) 
         {
            int i = n % 10;
            sum+=i*i;
             n /= 10;
        }
            return sum;
    }
    bool isHappy(int n) 
    {
        int count=731;
        while (count--) 
        {
            n=funct(n);
            if(n==1)return true;
        }
        return false;
    }
};

盛最多水的容器

思路：

首先我们通过暴力求解的方式算每两个元素间的体积，这种做法时间复杂度O(n^2),在这道题是不行的。

所有我们要找到其中的数学规律才行。

想一下任意两个元素之间的体积V1,如果里面存在更大的V2,那V2盛水的高度要更高。

水的高度取决于较小的值，更改较小的值找比它大的值代替。每更改一次就计算一次体积。

 

那么怎么样才能不漏掉任意一种情况呢？
1.先创建两个指针left指向第一个元素，right指向最后一个元素，并算出体积V

2.更换较小的值。如果nums[left] < nums[right] ,left++直到找到比它大的值。找到后计算体积并与V比较，大于V就更换。反之right--

3.当left>=right时结束。

代码实现：

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