首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。