《算法闯关指南：优选算法-双指针》--03快乐数，04盛水最多的容器
🔥草莓熊Lotso：个人主页
❄️个人专栏：《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受。
🎬博主简介：
目录
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
03.快乐数
题目链接：
202. 快乐数 - 力扣（LeetCode）
题目描述：
题目示例：
题目分析：
为了方便叙述，将【对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和】这一个操作记为 x 操作；
题目告诉我们，当我们不断重复 x 操作的时候，计算一定会【死循环】，死的方式有两种：
- 情况一：一直在 1 中死循环，即 1 -> 1 -> 1- > 1……
- 情况二：在历史的数据中死循环，但始终变不到 1
由于上述两种情况只会出现一种，因此，只要我们能够确定循环时在【情况一】中进行，还是在【情况二】中进行，就能得到结果。
简单证明：
- 1.经过依次变化之后的最大值 9^2*10=810 (2^31-1=2147483647。选一个更大的最大9999999999），也就是变化的区间在【1，810】之间；
- 2.根据【鸽巢原理】，一个数变化 811 次之后，必然会形成一个循环；
- 3.所以，变化的过程最终会走到一个圈里面，因此可以用【快慢指针】来解决。
解法：（快慢指针）
算法思路：
根据上述的题目分析，我们可以知道，当重复执行 x 的时候，数据会陷入到一个 【循环】之中。而【快慢指针】有一个特性，就是在一个圆圈里，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇的位置的值是 1 ，那么这个数一定是快乐数；如果相遇的位置不是 1 的话，那么就不是快乐数。
补充知识：如何求一个数n每个位置上的数字的平方和
1.把数 n 的每一位的数都提取出来，循环迭代以下步骤
- 1.1 int t = n % 10 提取个位；
- 1.2 n /= 10 干掉个位；
直到 n 的值变为 0；
2.提取每一位的时候，用一个变量 tmp 记录这一位的平方与之前提取位数的平方和
- tmp = tmp + t * t
C++代码演示：
class Solution { int bitsum(int n) { int sum=0; while(n) { int t=n%10; sum+=t*t; n/=10; } return sum; } public: bool isHappy(int n) { int slow=n; int fast=bitsum(n); while(slow!=fast) { slow=bitsum(slow); fast=bitsum(bitsum(fast)); } return slow==1; } };算法总结&&笔记展示：
笔记的字有点丑，大家见谅：
04.盛水最多的容器
题目链接：
11. 盛最多水的容器 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（对撞指针）
--这里暴力枚举也可以解决这个问题，但是会超时所以这里就不展示了
算法思路：
设两个指针 left ，right 分别指向容器的左右两个端点，此时容器的容积：
v = （right - left）* min（height[right]，height[left]）
容器的左边界为 height[left]，右边界为 height[right]。
为了方便叙述，我们假设 【左边边界】小于 【右边边界】。
如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：
- 容器的宽度一定变小
- 由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会增大。
- 如果改变右边界，无论右边界移动到哪里，新的水面高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度减小，因此容器的容积是一定会变小的。
由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下一个右边界。（那在本题里就是先比较左右谁小，如果左边小就left++，右边小就right--）
当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到 left 与 right 相遇。期间产生的所有的容积里面的最大值，就是最终答案。
C++代码演示：
class Solution { public: int maxArea(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; } };算法总结&&笔记展示：
笔记的字有点丑，大家见谅：
往期回顾：
《算法闯关指南：优选算法-双指针》--01移动零，02复写零
结语：本篇博客分享了两个经典算法题的解题思路：快乐数问题采用快慢指针法判断循环类型，盛水容器问题利用对撞指针优化计算。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。
✨把这些内容吃透超牛的！放松下吧✨
ʕ˘ᴥ˘ʔ
づきらど
