首页 > 代码库 > 【LeetCode】202. Happy Number

【LeetCode】202. 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.

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

比较直接的想法就是用一个map建立一个hash_table,对应的值为1说明出现过,那就是false。排除掉n==1的情况。不过耗时9ms,效率太低。

class Solution {public:    bool isHappy(int n) {        bool happy = false;        unordered_map<int, int> mps;        int tmpNum = n;        if (n == 1) return true;        while (tmpNum != 1) {            int buff = 0;            mps[tmpNum] = 1;            while (tmpNum % 10 != 0 || tmpNum / 10 != 0 ) {                buff += (tmpNum % 10)*(tmpNum % 10);                tmpNum /= 10;            }            tmpNum = buff;            if (buff == 1) {                happy = true;                break;            }            else if (mps[buff] == 1)        break;        }        return happy;    }};

参考discussion的别人的代码,只用了4ms

class Solution {public:    bool isHappy(int n) {        int sum = 0;        if (n == 1) return true;        if (n < 10 && n != 7) return false;                while (n>=10) {            sum += (n % 10)*(n % 10);            n /= 10;        }        sum += n*n;        if (sum == 1) {            return  true;        }        else return isHappy(sum);    }};

利用递归来判断。对于小于10的来说,除了7以外都不是happy number

 

【LeetCode】202. Happy Number