C#LeetCode刷题之#202-快乐数（Happy Number）

问题

编写一个算法来判断一个数是不是“快乐数”。

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

输入: 19

输出: true

解释:

$1^{2} + 9^{2} = 82$
$8^{2} + 2^{2} = 68$
$6^{2} + 8^{2} = 100$
$1^{2} + 0^{2} + 0^{2} = 1$

Write an algorithm to determine if a number 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.

Input: 19

Output: true

Explanation:

$1^{2} + 9^{2} = 82$
$8^{2} + 2^{2} = 68$
$6^{2} + 8^{2} = 100$
$1^{2} + 0^{2} + 0^{2} = 1$

示例

public class Program {

    public static void Main(string[] args) {

        int nums = 19;

        var res = IsHappy(nums);

        Console.WriteLine(res);

        nums = 26;

        res = IsHappy2(nums);

        Console.WriteLine(res);

        nums = 65;

        res = IsHappy3(nums);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    private static bool IsHappy(int n) {

        //递归法

        var set = new HashSet<int>();

        return ComputerHappy(n, set);

    }

    private static bool ComputerHappy(int n, HashSet<int> set) {

        if(n == 1) return true;

        if(set.Contains(n)) return false;

        set.Add(n);

        //计算各位数平方和

        //int sum = 0;

        //for(int i = 0; i < n.ToString().Length; i++) {

        //    sum += (int)Math.Pow(n / (int)Math.Pow(10, i) % 10, 2);

        //}

        return ComputerHappy(SquareSum(n), set);

    }

    private static int SquareSum(int n) {

        //计算各位数平方和

        var sum = 0;

        while(n > 0) {

            sum += (n % 10) * (n % 10);

            n = n / 10;

        }

        return sum;

    }

    private static bool IsHappy2(int n) {

        //若一个数不是快乐数，其必定死在4手上，最终进入以下死循环

        //4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

        //4的各数位平方是16，将y进行2次各位数平方和计算

        //若相等，则到达了4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

        //这样的死循环或到达了1这样的快乐数结束值

        //返回x == 1即可判定是不是快乐数

        var x = n;

        var y = n;

        do {

            x = SquareSum(x);

            y = SquareSum(SquareSum(y));

        } while(x != y);

        return x == 1;

    }

    private static bool IsHappy3(int n) {

        //参考IsHappy2

        while(n != 1 && n != 4) {

            var sum = 0;

            while(n > 0) {

                sum += (n % 10) * (n % 10);

                n /= 10;

            }

            n = sum;

        }

        return n == 1;

    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

True

False

False

分析：

该题的时间复杂度分析依赖于一些数学知识，若有看官知道如何分析请给我留言，不胜感激！

巴特西

C#LeetCode刷题之#202-快乐数（Happy Number）

最新文章

热门文章