[leetcode]Happy-Number-快乐数-三种解法

题目

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.
一个快乐数如下过程定义:在给定的进位制下,该数字所有数位(digits)的平方和,得到的新数再次求所有数位的平方和,如此重复进行,最终结果必为1。
Example: 19 is a happy number
比如, 19 是一个快乐书
12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

思路

对于所有数字,会有三种情况
1. 快乐数
2. 无限循环不快乐数
3. 无限不循环不快乐数
其中,不循环不快乐书不是绝对不循环,比如 2 , 算算就知道一直会在 4 之后循环. 但是 4 就会在本身开始, 循环.

普通解法

建立 set 表,每次得到的数值都需要查阅是否出现过,出现过就说明死循环了

class Solution {
public:
    bool isHappy(int n) {
        set<int> s;
        while (n != 1) {
            int temp = 0;
            while (n) {
                temp += (n % 10) * (n % 10);
                n /= 10;
            }
            n = temp;
            if (s.count(n)) break;
            else s.insert(n);
        }
        return n == 1 ? true : false;
    }
};

难得一见的解法

leetcode 偶然得到的代码,不去做 set 查重,而是设立两个速度不一样的 slow, fast 中间值,中间值追击相遇了,说明要么结果为 1,要么陷入循环。

class Solution {
    int calcSum(int n){
        int sum = 0;
        while(n){
            int num = n % 10;
            sum += num * num;
            n /= 10;
        }
        return sum;
    }
public:
    bool isHappy(int n) {
       int slow = n, fast = n;
       do{
           slow = calcSum(slow);
           fast = calcSum(fast);
           fast = calcSum(fast);
       } while(slow != fast);

        return slow == 1 ? true : false;
    }
};

第三种解法

第三种解法就很奇技淫巧,被发现凡是不开心数,计算过程中肯定有4,这可能就是被称为不快乐的原因吧,4,死?

class Solution {
public:
    bool isHappy(int n) {
        while (n != 1 && n != 4) {
            int t = 0;
            while (n) {
                t += (n % 10) * (n % 10);
                n /= 10;
            }
            n = t;
        }
        return n == 1;
    }
};

[最后一种方法来源][https://discuss.leetcode.com/topic/12587/my-solution-in-c-o-1-space-and-no-magic-math-property-involved]

发表评论

电子邮件地址不会被公开。 必填项已用*标注