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.
Example
19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
思路
什么数字是happy number?
squareSum(squareSum(...(n))) == 1
什么数字不是happy number?
squareSum(...)死循环。说明有环!!!
那么我们用快慢指针(Floyd Cycle detection algorithm)的思路去做。慢指针走一步,快指针走两步。如果两个结果相等,那么就跳出来判断一下是不是1。如果是1,当然就是happy number。如果不是1,就不是happy number。
Code
public class Solution { /** * @param n an integer * @return true if this is a happy number or false */ public boolean isHappy(int n) { // Write your code here int slow = n; int fast = n; do { slow = squareSum(slow); fast = squareSum(fast); fast = squareSum(fast); } while (slow != fast); return slow == 1; } private int squareSum(int n) { int sum = 0; while (n != 0) { sum += (n % 10) * (n % 10); n /= 10; } return sum; } }