
问题
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
输入: 19
输出: true
解释:




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:




示例
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
分析:
该题的时间复杂度分析依赖于一些数学知识,若有看官知道如何分析请给我留言,不胜感激!

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3856。