首页 > 代码库 > 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判圈算法(龟兔赛跑算法))