哈希-力扣202快乐数

发布时间:2024年01月09日

题目

编写一个算法来判断一个数?n?是不是快乐数。

「快乐数」?定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是?无限循环?但始终变不到 1。
  • 如果这个过程?结果为?1,那么这个数就是快乐数。

如果?n?是?快乐数?就返回?true?;不是,则返回?false?。

示例 1:

输入:n = 19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2:

输入:n = 2
输出:false

提示:

  • 1 <= n <= 2^31 - 1

思路

题目已经告诉我们本题的结果要么是无限循环要么就是得到1,从这我们可以得知只需要寻找前面是否出现过某数即可,该题数据量n明显较大,且不需要计数,找到就停,因此我们可以采用unordered_set该哈希表。

代码实现

class Solution {
public:
	int S(int n){
		int t,sum=0;
		while(n!=0){
			t=n%10;
			sum+=t*t;
			n/=10;
		}
		return sum;//计算每位平方和
	}
	bool isHappy(int n) {//判断是否是快乐数
		unordered_set<int>s;//哈希表,用find函数
		while(1){
			if(n==1)return true;//如果是1就返回
			else if(s.find(n)!=s.end())return false;//如果找到,说明重复
			s.insert(n);//插入该数
			n=S(n);//重置快乐数
		}
	}
};

反思

本题再次使用了unordered_set类型的哈希表,在未知范围和不需计数的查找中效率最快,内置find和insert函数方便查询,通过此题再次深入对哈希表类型的选择。

尾声

unordered_set类型,效率最快,时间复杂度最低,笔者希望本题可以让大家更加熟知类型的挑选和使用,如果觉得笔者写的还不错,记得留下您的点赞关注和支持哦~

文章来源:https://blog.csdn.net/2302_79862641/article/details/135458171
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。