当前位置:网站首页>快乐数[环类问题之快慢指针]
快乐数[环类问题之快慢指针]
2022-07-01 21:45:00 【REN_林森】
前言
分析题意,出现死循环相关问题,则属于环类问题,需用紧密联系的知识点快慢指针解决。保持快慢指针对环问题/死循环问题的敏感性。
一、快乐数
二、快慢指针
package everyday.doublePoint;
// 快乐数
public class IsHappy {
/* target:将一个数变成另一个数,按照一条固定的路径变下去,变到1就是快乐数,进入死循环就是非块乐数。 这就类似一个路径可能有环,可能无环。 最关键的地方在于判定是否有环,无环则是快乐数,有环则是非快乐数。 最直观的想法就是hash记录。 但是对于环问题,和其紧密关联的知识点就是快慢指针,如果快慢指针相碰,则有环,否则快指针走到末尾。 */
public boolean isHappy(int n) {
// 初始化快慢指针位置,快的在前,慢的再后。
int fast = getNext(n), slow = n;
// 一快一慢开始寻找。
while (fast != 1 && fast != slow) {
// fast走两步,slow走一步,要是有环必相碰,否则fast走到末尾的1.
fast = getNext(getNext(fast));
slow = getNext(slow);
}
// 看看是因为环结束,还是因为fast走到末尾结束。
return 1 == fast;
}
private int getNext(int n) {
int sum = 0;
while (n > 0) {
int mod = n % 10;
sum += mod * mod;
// 更新n
n /= 10;
}
return sum;
}
}
总结
1)保持快慢指针对环问题/死循环问题的敏感性。
参考文献
[1] LeetCode 快乐数
边栏推荐
- Yan Rong looks at how to formulate a multi cloud strategy in the era of hybrid cloud
- [live broadcast review] the first 8 live broadcasts of battle code Pioneer have come to a perfect end. Please look forward to the next one!
- 比较版本号[双指针截取自己想要的字串]
- Electron学习(三)之简单交互操作
- One of the basic learning of function
- linux下清理系统缓存并释放内存
- BlocProvider 为什么感觉和 Provider 很相似?
- 上半年暂停考试要补考?包含监理工程师、建筑师等十项考试
- Go — 相关依赖对应的exe
- Manually implement function isinstanceof (child, parent)
猜你喜欢
What is the difference between PMP and NPDP?
【juc学习之路第9天】屏障衍生工具
Manually implement function isinstanceof (child, parent)
Mask wearing detection method based on yolov5
Do you want to make up for the suspended examination in the first half of the year? Including ten examinations for supervision engineers, architects, etc
多种智能指针
Introduction à l'ingénierie logicielle (sixième édition) notes d'examen de Zhang haifan
焱融看 | 混合云时代下,如何制定多云策略
100年仅6款产品获批,疫苗竞争背后的“佐剂”江湖
MySQL之MHA高可用配置及故障切换
随机推荐
The correct way to set the bypass route
mysql 学习笔记-优化之SQL优化
Count the number of each character in the character
Smart micro mm32 multi-channel adc-dma configuration
Unity uses SQLite
GaussDB(DWS)主动预防排查
首席信息官对高绩效IT团队定义的探讨和分析
[NOIP2013]积木大赛 [NOIP2018]道路铺设 贪心/差分
函数基本学习之一
Aidl basic use
Medium pen test questions: flip the string, such as ABCD, print out DCBA
Copy ‘XXXX‘ to effectively final temp variable
信标委云原生专题组组长,任重道远!
MySQL之MHA高可用配置及故障切换
《QTreeView+QAbstractItemModel自定义模型》:系列教程之三[通俗易懂]
A debugging to understand the slot mechanism of redis cluster
What is the difference between consonants and Initials? (difference between initials and consonants)
多种智能指针
[intelligent QBD risk assessment tool] Shanghai daoning brings you leanqbd introduction, trial and tutorial
Basic operation of binary tree