当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.202.Happy Number 快乐数

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


上一篇 LeetCode.045.Jump Game II 跳跃游戏2

下一篇 LeetCode.1095.Find in Mountain Array 山脉数组中查找目标值

阅读
评论
772
阅读预计3分钟
创建日期 2020-04-30
修改日期 2020-04-30
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论