m***p
发帖数: 86 | 1 Happy Number 定义为 (只考虑正整数):
1是Happy number,
各个数字的平方和为happy number, 那么这个数字是happy number
例子: 13 -> 1^2+3^2 -> 10 -> 1^2+0^2 -> 1
这样13和10都是happy number
我的思路是: 如果计算出1， 返回true， 如果算出了以前出现过的数，返回false(因
为会形成一个循环，这样永远到不了1)
看网上的思路大体就是这样，可是今天面的三哥非要问：
为什么不能有第三种情况，就是一直不出现重复数字，还一直无法得到1(不断增长下去
)？
我也给不出严格证明，三哥最后给个方案，如果下一个int数字overflow的话，就返回
false
可是这完全多此一举，因为不会有这种情况的，请问如何能给出严格证明？ |
l******6
发帖数: 340 | 2 Suppose the number gets to n digits, next number is less than
9^2 * n = 81 * n
this is strictly less than the number itself, which is greater than
10^(n - 1)
when n gets greater or equal than 4
so the number will decrease after operation
no possible to overflow
laoyin doesn't know math |
r******l
发帖数: 10760 | 3 CS的面试题不要过多地从数学角度想。毕竟出这个题是考查你coding方面的能力，而不
是你数学有多强。他的意思应该就是看你的程序能否cover各种情况而已。
我以前碰到过一个面试题让不用sqrt函数计算平方根。我说用泰勒级数来算，他不愿意
。扯了半天发现其实他想要的答案是binary search而已。 |
K*******g
发帖数: 26 | 4 考虑INT_MAX，共10位，平方和小于10*（9*9）=810。
之后的平方和都小于810，所以不会一直增长，更不可能溢出。
【在 m***p 的大作中提到】
: Happy Number 定义为 (只考虑正整数):
: 1是Happy number,
: 各个数字的平方和为happy number, 那么这个数字是happy number
: 例子: 13 -> 1^2+3^2 -> 10 -> 1^2+0^2 -> 1
: 这样13和10都是happy number
: 我的思路是: 如果计算出1， 返回true， 如果算出了以前出现过的数，返回false(因
: 为会形成一个循环，这样永远到不了1)
: 看网上的思路大体就是这样，可是今天面的三哥非要问：
: 为什么不能有第三种情况，就是一直不出现重复数字，还一直无法得到1(不断增长下去
: )？
|
s******d
发帖数: 424 | 5 可以证明啊
9*9=81
9..9 设有N个9，当N>2，总有 81*N < 10^N
所以是有限的，不可能不断增长 |
w*****e
发帖数: 1050 | 6 http://en.wikipedia.org/wiki/Happy_number
Sequence behavior 给出了证明
so any number over 1000 gets smaller under this process and in particular
becomes a number with strictly fewer digits. Once we are under 1000, the
number for which the sum of squares of digits is largest is 999, and the
result is 3 times 81, that is, 243. |
f********x
发帖数: 2086 | |
l**********a
发帖数: 181 | 8 laoyin does not know math |
