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² + 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

Credits:

Special thanks to  and  for adding this problem and creating all test cases.

题意：给定一个整数，判断该数是否为Happy Number。

Happy Number的定义：计算整数的各个位上数字的平方和，重复该过程，如果出现和为1，则说明该数是Happy Number。如果在一个数字圈中无限循环，且该数字圈不包括1，则说明该数不是Happy Number。

 

方法一：开始理解错题意，想成了如果一个数不是Happy Number，则会出现平方和一直为某一个值的无限循环。提交不通过后又读一遍题，发现是如果一个数不是Happy Number，则平方和会从某处开始一直循环（想想也是这个道理）。

利用Set不能存放重复元素的特性，将每次的平方和都存入set，如果某次的平方和sum在set中已经出现过，则说明已经进入循环，该数字不是一个Happy Number。

beats 18.50 % of java submissions.

public boolean isHappy(int n) {        int sum = 0, temp;        Set
     
       set = new HashSet<>();        while(!set.contains(n)){            set.add(n);            while(n != 0){                temp = n % 10;                sum += temp * temp;                n = n / 10;            }            if(sum == 1)                return true;            n = sum;            sum = 0;        }        return false;    }
     

 

方法二：将每次计算的平方和存入一个链表，利用快慢指针，如果快指针跟慢指针重逢，则说明存在一个环，该数不是Happy Number。

beats 78.05 % of java submissions.

public boolean isHappy(int n) {        int sum = 0, temp;        Node head = new Node(n);        Node fast = head, slow = head, test = head;        while(slow == test || fast.val != slow.val){
   //slow == test用于排除fast和slow都指向第一个结点的初试情况            while(n != 0){                temp = n % 10;                sum += temp * temp;                n = n / 10;            }            if(sum == 1)                return true;            n = sum;            sum = 0;            head.next = new Node(n);            head = head.next;            if(fast.next.next != null){                fast = fast.next.next;                slow = slow.next;            }        }        return false;    }        class Node{        int val;        Node next;        public Node(int val){            this.val = val;        }    }

 

方法三：只是与方法二的循环结束条件不同

public boolean isHappy(int n) {        int sum = 0, temp;        Node head = new Node(n);        Node fast = head, slow = head, test = head;;        while(n != 1){            while(n != 0){                temp = n % 10;                sum += temp * temp;                n = n / 10;            }            n = sum;            sum = 0;            head.next = new Node(n);            head = head.next;            if(fast.next.next != null){                fast = fast.next.next;                slow = slow.next;            }            if(slow != test && fast.val == slow.val)                return false;        }        return true;    }

 

方法四：利用函数来取代快慢指针，参考：https://www.jianshu.com/p/f7b632e31d5f

beats 78.05 % of java submissions.

public boolean isHappy(int n){        int sum = 0;        int fast = n, slow = n;        while(sum != 1){            slow = getSum(slow);            if(slow == 1)                return true;            fast = getSum(getSum(fast));             if(fast == slow)                return false;            sum = slow;        }        return true;    }    public int getSum(int n){        int temp, sum = 0;        while(n != 0){            temp = n % 10;            sum += temp * temp;            n /= 10;        }        return sum;    }