202. 快乐数

题目地址(202. 快乐数)

https://leetcode-cn.com/problems/happy-number/

题目描述

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为  1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
提示：
1 <= n <= 231 - 1

前置知识

公司

• 暂无

思路

由于循环中可能会出现重复的数字陷入死循环 需要使用hashset来判断数字是否出现过
再使该数的位数平方相加 继续循环

关键点

• 求和的过程

先将整体数字%10 得到个位 个位乘积相加
然后将数字/10 当前的个位等于之前的10位 以此类推

• 使用hashset判断是否重复循环

代码

• 语言支持：Java

Java Code:

class Solution {
        public boolean isHappy(int n) {
            //这个数字可能会无限循环 使用set判断是否出现过该数字
            HashSet<Integer> result = new HashSet<>();
            //当 n!=1 和set中不包含重复的数字的时候指执行
            while (n != 1 && !result.contains(n)) {
                result.add(n);
                //n = 每个位数乘积相加
                n = getNextNumber(n);    
            }
            //判断 n是否=1 等于返回true反之亦然
            return n == 1;
        }
        public int getNextNumber(int n) {
            int result = 0;
            while (n > 0) {
                //得到个位的数字
                int temp = n % 10;
                //个位的数字平方
                result += temp * temp;
                //当前十位变为个位 直到n<0
                n /= 10;
            }
            return result;
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=au0Z3)
• 空间复杂度：#card=math&code=O%28n%29&id=jQAUT)