【鼠鼠优选算法-双指针】003：快乐数 & 004：盛水最多的容器
🎈主页传送门:良木生香
🔥个人专栏:《C语言》 《数据结构-初阶》 《鼠鼠的算法之路》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
目录
今天我们来看两道有意思的题目，分别是力扣的11号和202号题目，题目链接2我会在讲到题目的时候放给大家
一、快乐数
这是题目链接：
题目描述:
原理解析：
这道题讲的是如果某个数能够按照他所给的规则进行变化，最后得到1，那这个数就是快乐数，意思很容易理解，那么下面我们来看看这道题该怎么实现算法吧~~
想要判断这个数是不是快乐数字，我们要做的是以下步骤：
1.将这个数字拆分
2.将这个数字的每一位数字进行平方操作，再相加
3.经过与偶先次循环后，看看整个数是不是等于1
现在我们对题目给出来的样例进行推导：
数字19题目已经帮我们推导过了，那现在我们自己来试试推导数字2：
由此可见，数字2最后并回不到1，所以它不是快乐数字
讲到这里，我们就可以知道，这道题现在有三种情况：
那我们现在不妨想一想，这道题如果不循环的进行下去，我们该怎么判断会不会等于1呢？
那么在这道题目中，就涉及到一个小小定理，叫做鸽巢原理，下面我就详细讲讲这个原理：
鸽巢原理：
定义：假设有 n 个 “物品”，要放进 m 个 “抽屉” 里；如果 物品数 n > 抽屉数 m，那么至少有一个抽屉里会装着至少 2 个物品。
这样子讲可能不好理解，那我们讲个例子来体会体会：
由此可见，数字2最后并回不到1，所以它不是快乐数字，那我们不妨想一想，是不是每个数字最后都会循环到同一个数字上呢？即使不是它本身？
我们想要将三个苹果放进两个抽屉里面，那么肯定有一个抽屉放了两个苹果
那这个原理在这道题目里面有什么用呢？，抽屉是对应题目里面的什么？苹果对应的又是题目里的什么？
我们知道，这道题的过程是“计算数字各位的平方和”，那么我们就可以计算一下，在2^10这些数字中,他们的各位平方和的范围是多少?现在题目给出了数据的范围:1~21亿,想知道这些数字的运算范围,我们直接用上极限法,直接计算9999999999这个数字的各位平方和,计算得到810,也就是说,这么大的一个数的各位平方和都只是810,那么在21亿这个数之内的数的各位平方和一定小于810,那么他们的范围就是【1，810】，这时候就明了了，这个数字范围就是抽屉，整个21亿范围内的数字的各位平方和就是苹果，那么根据鸽巢原理的定义，这些数字不论怎么变化，最后肯定会和其中某一个数字相同，所以我们最后只用判断在循环出现的数字中有没有1这个数字就可以了
我们可以使快慢指针的方式,遍历一遍所有可能生成的数字,如果慢指针与快指针相等同时等于1,那么这个数就是快乐数字,如果不等于1,那就不是快乐数字,现在可以实现代码了:
代码实现:
//想要实现这个操作,还要再写一个操作函数 int Func(int num){ int sum=0; while(num!=0){ int temp = num%10; sum += temp*temp; num /= 10; } return sum; } bool isHappy(int n) { //这道题可以使用快慢指针来解决 //先定义一个慢指针 int slow = n; //再定义一个快指针 int fast = Func(n);//因为慢指针走一步,快指针走两步 //现在进入循环,知道这两个相等为止 while(slow!=fast){ slow = Func(slow); fast = Func(Func(fast)); } return slow == 1; }
二、盛最多水的容器
题目链接：
题目描述：
原理解析：
这道题木意思很明了，就是想让我们将容积最大的数字计算出来，实际上就是让我们找到x与y乘积的最大值,说是这么说,但是还是要注意一点,这里的乘法是遵循木桶效应的,两个数相乘.
容器的体积 = distence(两数之之间的距离)*heigh(两数之间小的那个数字)
这里我们同样可以使用双指针,将两个指针分别放在数组的左右两侧,先计算本次的容积,再判断两个指针所指向的数字(一下简称左右指针)哪个小,如果是左指针小,那就将左指针向右移动一位,反之就是右指针向左移动
为什么呢?
因为左指针在移动的过程中,他与右指针的距离distence在缩小,如果高度heigh不变,那整个容积仍然是减小的,如果高度heigh还减小,那整个体积会更加小,所以我们会尽全力的争取高度最大,因为distence是肯定会减小的
最后在计算的过程中,只用再加上一个变量maxV用来记录当前容积的最大值即可,那么,上代码:
代码实现:
int maxArea(int* height, int heightSize) { int left = 0; int right = heightSize-1; int maxV=0; int volume=0; while(left<right){ volume = (right-left)*(height[left]>height[right]?height[right]:height[left]); if(volume>maxV){ maxV = volume; } height[left]<height[right]?left++:right--; } return maxV; }这道题拿督不大,整体给到NPC
以上就是我对这个两道题的分享了,感谢大佬们的阅读~~~~
