这是悦乐书的第 188 次更新, 第 190 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 47 题 (顺位题号是 202). 编写算法以确定数字是否 "幸福".
幸福数字是由以下过程定义的数字: 从任何正整数开始, 将数字替换为其数字的平方和, 并重复该过程, 直到最后数字等于 1. 这个过程以 1 结尾的那些数字是幸福的数字. 如果陷入无限循环则不是幸福数字. 例如:
输入: 19
输出: true
说明:
- 1x1 + 9x9 = 82
- 8x8 + 2x2 = 68
- 6x6 + 8x8 = 100
- 1x1 + 0x0 + 0x0 = 1
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
从题目给的例子可以看出, 每获得一个新的数字, 都需要按照个十百位拆分然后计算乘积, 直到最后得到的是 1 为止, 而那些不是幸福数字的数, 会陷入死循环里面, 因此, 我们需要将每次新计算得到的结果保存起来, 如果下次计算的时候遇到, 可以直接判断该数字不是幸福数字, 因此我们使用 HashMap 来存值, 使用递归来循环处理数据. 因为需要多次使用 Map, 所以将其定义在方法外面, 可以全局使用.
- Map<Integer, Integer> map = new HashMap<Integer, Integer>();
- public boolean isHappy(int n) {
- if (n <= 0) {
- return false;
- }
- if (n == 1) {
- return true;
- }
- int index = 1;
- int sum = 0;
- for (int i=0; i <(n+"").length(); i++) {
- sum += Math.pow((n+"").charAt(i)-'0', 2);
- }
- if (sum == 1) {
- return true;
- }
- if (map.containsKey(sum)) {
- return false;
- } else {
- map.put(sum, index++);
- }
- return isHappy(sum);
- }
03 第二种解法
思路与上面一样, 不过使用的是迭代的方法, 所以, 定义的 HashMap 放在你方法里面. 使用了两层循环, 外层控制 map 判断 key 是否存在以及替换新的 n, 内层循环处理新数不同位整数的平方和.
- public boolean isHappy2(int n) {
- if (n <= 0) {
- return false;
- }
- if (n == 1) {
- return true;
- }
- Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();
- int index = 1;
- int sum = 0;
- while (true) {
- for (int i=0; i <(n+"").length(); i++) {
- sum += Math.pow((n+"").charAt(i)-'0', 2);
- }
- if (sum == 1) {
- return true;
- }
- if (map2.containsKey(sum)) {
- return false;
- } else {
- map2.put(sum, index++);
- }
- n = sum;
- sum = 0;
- }
- }
04 第三种解法
如果你算过几个特殊的数, 比如 2,4,14,16,18, 这些数字都会陷入死循环, 并且是数字 4. 至于其他的数, 如果不是幸福数, 都会陷入死循环里面, 死循环的入口就是 4 或者 16, 对此, 我们可以不使用 HashMap, 只要判断新得到的数是否等于 4 或者 16 即可表示此数字不是幸福数字.
此解法同样是使用迭代的方法, 借助两层循环, 外层做判断, 内层做不同位数字的平方和.
- public boolean isHappy3(int n) {
- int sum = 0;
- while (sum != 1) {
- if (n == 4 || n == 16)
- break;
- while (n> 0) {
- int rem = n % 10;
- sum += rem * rem;
- n /= 10;
- }
- if (sum == 1)
- return true;
- n = sum;
- sum = 0;
- }
- return false;
- }
05 第四种解法
使用 HashSet, 借助其不能存在重复元素的特性, 思路和第一, 第二种解法一样, 都是先去获取新数的平方和, 然后添加进 HashSet, 如果添加失败, 说明已经存在该整数, 即不是幸福数. 不过这里是改变了 n 的原始值, 所以最后判断的是 n 是否等于 1.
- public boolean isHappy4(int n) {
- HashSet<Integer> seen = new HashSet<>();
- while (seen.add(n)) {
- int square = 0;
- int sum = 0;
- while (n!=0) {
- square = n%10;
- sum += (square*square);
- n /=10;
- }
- n = sum;
- }
- return n==1 ? true : false;
- }
06 第五种解法
借助环的思路. 如果你还对之前的判断一个链表是否存在环的那道题目有印象的话, 那么此题是与之类似的, 每次新得到的数就代表一个节点, 如果此节点出现过一次, 即表示此链表是有环的, 也就是说明此数是幸福数.
借助双指针, 一个每次进行一次计算, 另外一个每次计算两次, 相当于速度是前一个的两倍, 如果存在相同的数, 两个指针肯定会相遇.
- public boolean isHappy5(int n) {
- int slow = n;
- int fast = n;
- do {
- slow = digitSquareSum(slow);
- fast = digitSquareSum(fast);
- fast = digitSquareSum(fast);
- if (slow == 1 || fast == 1) {
- return true;
- }
- } while(slow != fast);
- return false;
- }
- public int digitSquareSum(int n) {
- int sum = 0, tmp;
- while (n> 0) {
- tmp = n % 10;
- sum += tmp * tmp;
- n /= 10;
- }
- return sum;
- }
07 小结
算法专题目前已连续日更超过一个月, 算法题文章 47 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/609a8978a310