首页 > 代码库 > leetcode202(Floyd判圈算法(龟兔赛跑算法))
leetcode202(Floyd判圈算法(龟兔赛跑算法))
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.
一个快乐数是这样定义的,规则如下:由一个整数开始,之后由整数每一位数字的平方和的总和代替这个数,然后重复这个过程,直到最后是1为止,或者这个循环是一个没有包含1的死循环。这些过程中最终结果是1的这些数被称为快乐数。
Example: 19 is a happy number
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
这个题目真的我没有想到好的思路,能想到的几点说一下,平方的值只有从0-9这几个数的平方,所以,定一个固定的数组一定比平方的计算要快,直接可以用数组下标取出最后的结果。
这道题难在如何判断它是一个死循环,而且还是没有1的。除了循环枚举我真的没有想到什么好的方法,我只能在想,肯定有几种特殊的情况是遇到一定是会出现死循环的。
网上给出的解答是这样的,具体是这样的
int digitSquareSum(int n) { int sum = 0, tmp; while (n) { tmp = n % 10; sum += tmp * tmp; n /= 10; } return sum;}bool isHappy(int n) { int slow, fast; slow = fast = n; do { slow = digitSquareSum(slow); fast = digitSquareSum(fast); fast = digitSquareSum(fast); } while(slow != fast); if (slow == 1) return 1; else return 0;}
这个算法我也是第一次见到,这我就好好研究了一番,发现这真的是一个神奇的算法。
名字叫做Floyd判圈算法(龟兔赛跑算法)
先往简单了说,就是判断有没有环,定两个起始位置一样的指针,一个跑的慢每次跑一个循环,一个跑的快每次跑相当于跑两个循环,一旦他们出现相同之后,那么就肯定是有环了,然后我们就看责怪环是不是1即可,这个算法最大的一个优点是时间复杂度低,空间复杂度也低,你不需要保存每一次出现的值然后和前面的值作比较。
具体算法的讲解我这边直接贴上地址,转载自:
http://blog.csdn.net/wall_f/article/details/8780209
说实话我很喜欢这个算法,确实棒极了!
leetcode202(Floyd判圈算法(龟兔赛跑算法))