前言
本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!!
算法题(LeetCode刷题202快乐数)—(保姆级别讲解)
分析题目
- 题目中说了会无限循环,那么也就是说在求和过程中,
sum
会重复出现,则我们可以联想到可以通过判断sum
这个元素是否出现在集合里,如果sum
重复出现了,则代表该数肯定不是快乐数,即我们可以联想到哈希法来判断。 - 既然我们选择用哈希法来判断,则我们需要选择使用哪种数据结构来构建哈希表,由于最终集合里是保证元素不能重复,所以我们采用
unordered_set
。
算法思想(使用unordered_set实现哈希表)
class Solution {
public:
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
好!按照老样子,接下来开始详细讲解每行代码的用处,以及为什么这样写
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
这个函数的作用是取得数值各个位上的单数平方之和。那么重点肯定是如何求得各个位的数值。
在这里举个例子,假设n = 123
,则我们取得个位的方法为n%10
,即123%10 = 3
,那么在下一次取得十位的方法为n/10
,即123/10 = 12
,以此类推,12%10 = 2
,12/10=1
,1%10 = 1
,1/10 = 0
。至此,退出while
循环。
unordered_set<int> set;
由于我们选择使用unordered_set
实现哈希表,即为我们最终遍历的集合,该集合名称为set
。
int sum = getSum(n);
获得了该每一位的平方和,并且赋值为sum
。
if (sum == 1) {
return true;
}
如果直接求和之后等于1
,即代表为快乐数,不用再迭代了,直接返回。
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
unordered_set::find()
函数是C++ STL
中的内置函数,用于在容器中搜索元素。如果找到指定元素,它返回元素的迭代器,如果找不到指定元素,则返回指向unordered_set::end()
的迭代器。所以判断与set.end()
是否相等即可。
如果不相等,则代表集合中有相同的元素,即代表sum
重复了,则代表该num
肯定不是快乐数。
如果相等,则代表找不到指定元素,则我们为了再下一次循环迭代过程中,比较sum
值,我们需要将该sum
值添加到集合set
中。
n = sum;
将sum
赋值给n
,方便下一次计算新的sum
值。
结束语
如果觉得这篇文章还不错的话,记得点赞 ,支持下!!!