优选算法——双指针专题 3.快乐数 4.盛水最多的容器

优选算法——双指针专题 3.快乐数 4.盛水最多的容器

一.快乐数

1.题目解析

[题目传送门](202. 快乐数 - 力扣（LeetCode）)

2.原理解析

第一种情况：数最后变成1

第二种情况：无限循环但不是1

但两种都可以抽象成一种，有点像之前做过的带环链表

解法：快慢双指针

1.定义快慢指针

2.慢指针每次向后移动一步，快指针每次向后移动两步

3.判断相遇时候的值

3.代码实现

classSolution{public:intBitSum(int n)//返回每一位数上的平方和{int sum=0;while(n){int m=n%10; sum+=m*m; n=n/10;}return sum;}boolisHappy(int n){int slow=n,fast=BitSum(n);while(slow!=fast){ slow=BitSum(slow); fast=BitSum(BitSum(fast));}return slow==1;}};

二.盛水最多的容器

[题目传送门](11. 盛最多水的容器 - 力扣（LeetCode）)

1.题目解析

2.原理解析

解法一：暴力枚举

时间复杂度O(N^2) 会超时

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

在这一组数中拿出一个区间 6，2，5，4

我们先用最两边的数算一个容积，然后小的那个固定住(也就是4) ,向内枚举

如果遇到比它小的数(也就是2)，高度跟宽度都减小，v减小

如果遇到比它大的数(也就是5),高度不变（还是4），宽度减小，v减小

所以我们可以直接舍去小的那一个，在研究下一个区间

3.代码实现

classSolution{public:intmaxArea(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;}};