LeetCode.202.Happy Number 快乐数

题目描述

202 Happy Number
https://leetcode-cn.com/problems/happy-number/

Write an algorithm to determine if a number n is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example: 

Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

---

相似题目

Floyd判圈算法/龟兔赛跑算法

有环单链表的环长、环起点和链表长
LeetCode.141.Linked List Cycle 判断链表是否有环
LeetCode.142.Linked List Cycle II 有环链表的环起点

判圈算法的其他应用
LeetCode.287.Find the Duplicate Number 数组中重复的数
LeetCode.202.Happy Number 快乐数

---

解题过程

官方题解中给了说明，通过各位平方和来找下一个数，不会变的无穷大，比如
9999999999999 的各位平方和是 1053
9999 的各位平方和是 324
其实有结论：
1、对于 3 位以下的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。
2、对于 4 位或 4 位以上的数字在每一步都会至少丢失一位，直到降到 3 位为止。
所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去。

快慢指针/链表有环判断/Floyd判圈

弗洛伊德判圈算法的应用，把 n 和 next(n) 看成链表的前后两个节点，如果有循环则此链表一定有环，使用弗洛伊德判圈算法（快慢指针）进行有环判断。

Map标记已访问过的数

用一个哈希集合 visited 标记已访问过的数，遇到已访问过的数说明存在循环，可退出循环返回false
时间复杂度 O(logn)，空间复杂度 O(logn)

private static class SolutionV2020Hash {
    public boolean isHappy(int n) {
        // 是否已访问过，遇到已访问过的数说明存在循环，可直接返回false
        Set<Integer> visited = new HashSet<>();
        while (!visited.contains(n)) {
            if (n == 1) {
                return true;
            }
            visited.add(n);
            int sum = 0;
            while (n != 0) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            n = sum;
        }
        return false;
    }
}

固定循环10000次

不知道进入无限循环后如何结束，写了个固定循环 10000 次，也能通过。
因为整数 n 的位数是 logn，所以每次获取下一个数字的时间复杂度是 O(logn)

// 循环 10000 次，可通过
private static class SolutionV2020Brutal {
    public boolean isHappy(int n) {
        int loops = 0;
        while (loops < 10000) {
            if (n == 1) {
                return true;
            }
            int sum = 0;
            while (n != 0) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            n = sum;
            loops++;
        }
        return false;
    }
}

---

LeetCode2020年三四月每日一题打卡奖牌

2020 年 3、4月每日一题完整打卡，拿到奖牌了

LeetCode 2020 年三四月每日一题打卡奖牌

---

GitHub代码

algorithms/leetcode/leetcode/_202_HappyNumber.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_202_HappyNumber.java

---