您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

快乐数(图文)

第十三双眼睛2023-12-03【数据结构与算法】人已围观

简介快乐数
编写一个算法来判断一个数 n 是不是快乐数。
快乐数定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

思路：先定义一个函数，用来把某个数转换为它各位上的平方和。如果一个数不是快乐数，它的各位上的平方和就会出现循环，利用这个特性，我们就能判断一个数是不是快乐数，定义一个集合，不断的循环，每次都把当前数转换为各位数的平方和，然后判断该数是不是1，如果是1，则返回true，如果不是1，则判断集合中是否存在该数，如果已经存在，则返回false，如果部存在，则把该数放入集合。代码如下：

public static boolean method1(int num) {
   Set<Integer> set = new HashSet<>();
   while (num != 1 && !set.contains(num)) {
       set.add(num);
       num = test(num);
   }
   return num == 1;
}

public static int test(int num) {
   int sum = 0;
   while (num >0) {
       // 把低位取下来
       int temp = num % 10;
       num = num / 10;
       sum = sum + temp * temp;
   }
   return sum;
}

上面的方法需要定义一个集合来存储每次运算后的结果，可能这个集合会非常大，因此有了第二种思路
第二种思路：使用快慢指针法，定义两个指针，一个每次变换一次，另一个每次变换两次，如果这个数是快乐数，经过一定次数的循环之后，他们都会称为1，如果不是快乐数，他们最终都会进入环中循环，而快指针最终会追上慢指针，他们的值也会相等，因此，一直循环，当他们的值相等的时候，跳出循环，判断此时随便一个指针的值是不是1即可。代码如下：

public static boolean method2(int num) {
   int slow = num;
   int fast = num;
   do {
       slow = test(slow);
       fast = test(fast);
       fast = test(fast);
   } while (fast != slow);
   return fast == 1;
}

思路三：因为每次拆分，都是拆成一位数，而1位数中，只有2，4不是快乐数，因此在循环的过程中，只要遇到2,4和经他们得到的数，都不是快乐数，其他的都是可以条春循环的。因此代码如下：

public static boolean method3(int num) {
   while (num != 1) {
       if (num == 4 || num ==16 || num == 37 || num == 58 || num == 89 || num == 145 || num == 20 || num == 42) {
           return false;
       }
       num = test(num);
   }
   return true;
}

Tags：

很赞哦！ ()

上一篇：颠倒二进制位(图文)

下一篇：移除链表元素(图文)