双指针_快乐数

本文主要是介绍双指针_快乐数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快乐数

题目链接：快乐数

内容：

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

这篇关于双指针_快乐数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---