个人建网站需要多少钱,中国互联网十大巨头公司,建筑设计说明模板,wordpress植物网站链接快乐数题序号202题型数组解题方法哈希表难度简单熟练度✅✅✅✅
题目 编写一个算法来判断一个数 n 是不是快乐数。 [快乐数] 定义为#xff1a; 对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1#xff0…链接快乐数题序号202题型数组解题方法哈希表难度简单熟练度✅✅✅✅
题目 编写一个算法来判断一个数 n 是不是快乐数。 [快乐数] 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true 不是则返回 false 。 示例 1 输入n 19 输出true 解释 12 92 82 82 22 68 62 82 100 12 02 02 1 示例 2 输入n 2 输出false 提示 1 n 231 - 1
题解
核心思想使用哈希表来记录已经出现过的数字如果在计算过程中某个数字重复出现说明进入了循环返回 false如果最终计算结果为 1返回 true。复杂度时间复杂度O(logn)因为每次计算下一个数的时间复杂度为 O(logn)空间复杂度O(1)不需要额外的存储空间。c 实现算法
class Solution {
public:bool isHappy(int n) {unordered_setint seen; // 用于存储已经出现过的数字检测循环//如果 find(n) 返回 seen.end()表示 n 不存在于集合中查找失败。//如果 find(n) 返回的迭代器不是 seen.end()表示 n 存在于集合中查找成功。while (n ! 1 seen.find(n) seen.end()) {seen.insert(n); // 将当前数字加入集合n getNext(n); // 计算下一步的平方和}return n 1; // 如果 n 1返回 true否则进入循环返回 false}private:int getNext(int n) {int sum 0;while (n 0) {int digit n % 10; // 提取个位数,如果 n 123则 digit 123 % 10 3sum digit * digit; // 累加平方n / 10; // 去掉个位,如果 n 123执行 n / 10 后n 12}return sum;}
};算法推演 初始值 输入数字n 2 seen 集合空集合 {} 第一步计算平方和 当前数字n 2 计算平方和 224 更新数字n 4 检查 4 是否在 seen 集合中否将 4 加入集合。 集合更新为{2} 第二步计算平方和 当前数字n 4 计算平方和 4216 更新数字n 16 检查 16 是否在 seen 集合中否将 16 加入集合。 集合更新为{2, 4} 第三步计算平方和 当前数字n 16 计算平方和 126237 更新数字n 37 检查 37 是否在 seen 集合中否将 37 加入集合。 集合更新为{2, 4, 16} 第四步计算平方和 当前数字n 37 计算平方和 327258 更新数字n 58 检查 58 是否在 seen 集合中否将 58 加入集合。 集合更新为{2, 4, 16, 37} 第五步计算平方和 当前数字n 58 计算平方和 528289 更新数字n 89 检查 89 是否在 seen 集合中否将 89 加入集合。 集合更新为{2, 4, 16, 37, 58} 第六步计算平方和 当前数字n 89 计算平方和 8292145 更新数字n 145 检查 145 是否在 seen 集合中否将 145 加入集合。 集合更新为{2, 4, 16, 37, 58, 89} 第七步计算平方和 当前数字n 145 计算平方和 12425242 更新数字n 42 检查 42 是否在 seen 集合中否将 42 加入集合。 集合更新为{2, 4, 16, 37, 58, 89, 145} 第八步计算平方和 当前数字n 42 计算平方和 422220 更新数字n 20 检查 20 是否在 seen 集合中否将 20 加入集合。 集合更新为{2, 4, 16, 37, 58, 89, 145, 42} 第九步计算平方和 当前数字n 20 计算平方和 22024 更新数字n 4 检查 4 是否在 seen 集合中是说明进入循环。 结论 输入 2 会进入循环无法到达 1因此 2 不是一个快乐数。 循环检测 通过集合 seen我们检测到了循环路径 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (循环) 这是算法检测非快乐数的重要机制避免了死循环。 c 完整demo
#include iostream
#include unordered_set
using namespace std;class Solution {
public:bool isHappy(int n) {unordered_setint seen; // 用于存储已经出现过的数字检测循环//如果 find(n) 返回 seen.end()表示 n 不存在于集合中查找失败。//如果 find(n) 返回的迭代器不是 seen.end()表示 n 存在于集合中查找成功。while (n ! 1 seen.find(n) seen.end()) {seen.insert(n); // 将当前数字加入集合n getNext(n); // 计算下一步的平方和}return n 1; // 如果 n 1返回 true否则进入循环返回 false}private:int getNext(int n) {int sum 0;while (n 0) {int digit n % 10; // 提取个位数,如果 n 123则 digit 123 % 10 3sum digit * digit; // 累加平方n / 10; // 去掉个位,如果 n 123执行 n / 10 后n 12}return sum;}
};int main() {Solution solution;int n 2;if (solution.isHappy(n)) {cout n is a happy number! endl;} else {cout n is not a happy number! endl;}return 0;
}
