1. Description of the problem
English description
Write an algorithm to determine if a number n 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.
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.
Return true if n is a happy number, and false if not.Example 1:
Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1Example 2:
Input: n = 2
Output: falseConstraints:
1 <= n <= 2^31 – 1
Product description
Write an algorithm to determine whether a number n is a happy number.
Happiness number is defined as:
For a positive integer, replace the number each time with the sum of squares of the numbers at each of its positions. And then you repeat the process until the number is 1, or it could go on forever but it never gets to 1. If you can change it to 1, then that number is happiness. Return true if n is the happy number; If not, return false.
Example 1:
Input: 19 Output: true Description: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
Example 2:
Input: n = 2 Output: false
Tip:
1 <= n <= 2^31 – 1
Source: LeetCode link: leetcode-cn.com/problems/ha… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Second, the idea of solving the problem
Method one — sets
That’s the easiest way to think about it.
Store each iterated value (except 1) in the collection, and when a new value appears, see if it already exists in the collection.
If it does, it’s going through a cycle that never reaches 1
Method two — loop linked lists
Since the rule has unique directivity (given a number, its next number is determined), the progress of the rule can be regarded as a one-way linked list. When there is repetition in the running process, it indicates that there is a cycle in the linked list, which is a circular linked list.
So if there is no 1 before the list is found to be a circular list, that number is not a happy number.
It is more important to exercise algorithmic thinking and understand another use of circular lists.
It is important to note that whether Pointers meet here is determined not by whether Pointers are equal, but by whether the values of the nodes are equal.
Three, AC code
Only the solution code for the circular linked list is provided here
C++
class Solution { public: struct Node { Node(int data) : data(data), next(NULL) {} int data; Node *next; }; int getNextData(int n) { int res = 0; while(n ! = 0) { res += pow(n % 10, 2); n /= 10; } return res; } bool isHappy(int n) { Node *head = new Node(n); int tem = getNextData(n); head->next = new Node(tem); if(head->data == 1 || head->next->data == 1) return true; Node *slow = head, *fast = head->next; While (fast->data! = 1 && slow->data ! = fast->data) { slow = slow->next; tem = getNextData(tem); if(tem == 1) return true; fast->next = new Node(tem); tem = getNextData(tem); fast->next->next = new Node(tem); fast = fast->next->next; } return fast->data == 1; }};Copy the codeJava
class Solution { class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } int getNextData(int n) { int res = 0; while(n ! = 0) { res += Math.pow(n % 10, 2); n /= 10; } return res; } public boolean isHappy(int n) { ListNode head = new ListNode(n); int tem = getNextData(n); head.next =new ListNode(tem); if(head.val == 1 || head.next.val == 1) return true; ListNode slow = head; ListNode fast = head.next; while(fast.val ! = 1 && slow.val ! = fast.val) { slow = slow.next; tem = getNextData(tem); if(tem == 1) return true; fast.next = new ListNode(tem); tem = getNextData(tem); fast.next.next = new ListNode(tem); fast = fast.next.next; } return fast.val == 1; }}Copy the codeFourth, the problem solving process
The first,
Get out of my way! I’m gonna play B!
