LeetCode算法题-Happy Number（Java实现） _LeetCode算法

历览千载书，时时见遗烈。这篇文章主要讲述LeetCode算法题-Happy Number（Java实现）相关的知识，希望能为你提供帮助。
这是悦乐书的第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; } }

【LeetCode算法题-Happy Number（Java实现）】

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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！