当前位置：首页 > news >正文

LeetCode 202 Happy Number(floyd判圈算法(龟兔赛跑算法))

news 来源：原创 2024/5/15 17:54:33

题目链接：https://leetcode.com/problems/happy-number/description/

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

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Credits:
Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.

题意：

由一个整数开始，之后由整数每一位数字的平方和的总和代替这个数，然后重复这个过程，直到最后是1为止，或者这个循环是一个没有包含1的死循环。这些过程中最终结果是1的这些数被称为快乐数。

分析：

就是让你验证一个数是否为欢乐数。

这里用到了一个名为龟兔赛跑的判断链表是否存在环的算法，不同于拓扑排序判断有向图是否存在环，也不同于floyd求最小环算法。其空间复杂度为O(1)，时间复杂度O(n)[我感觉不止...]。对于一种链表，每个节点只有一个后继，但到达它的前驱可能不止一个，该算法便是利用了只有一个后继的特点去进行求环。该算法能够确定从某点开始到达环中的第一个节点，以及该环的长度。所以多用来寻找循环节，循环节不恰好就是上述链表的特性嘛。

具体思想见：http://blog.csdn.net/u012534831/article/details/74231581。

下面贴下自己写的模板代码：

int nex[maxn];	//存储后继 
void work(int S)
{
	int k1 = S, k2 = S;  
    do  
    {  
        k1 = nex[k1];  
        k2 = nex[k2];  
        //if(k2 == -1) return 0;  //如果有链尾，此处可判断无环 
        k2 = nex[k2];  
        //if(k2 == -1) return 0;  
    }  
    while(k1 != k2);  
    
	//将一个指针移到起点，求出非环部分长度和环的起点 
	int cnt1 = 0;
    k1 = S;
    do  
    {  
        k1 = nex[k1];  
        k2 = nex[k2];
		++cnt1;  
    }  
    while(k1 != k2);  
    int start = k1; //求出从S到环中的第一个点  
      
    int cnt2 = 0;    //求环部分长度   
    do
	{
		++cnt2;
		k1 = nex[k1];  
	} 
    while(k1 != start);
}

所以知道龟兔赛跑算法之后再看本题就很简单了(这题是外国网站的题，原来自己写的c++还不是国际认可标准...)

ac代码：

int bas[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
class Solution {
public:
    int nex(int d)
    {
        int res = 0;
        while(d)
        {
            res += bas[d%10];
            d /= 10;
        }
        return res;
    }
    bool work(int d)
    {
        int k1 = d, k2 = d;
        do
        {
            k1 = nex(k1);
            k2 = nex(k2);
            if(k2 == 1) return 1;
            k2 = nex(k2);
            if(k2 == 1) return 1;
        }
        while(k1 != k2);
        return 0;
    }
    bool isHappy(int n) {
        return work(n);
    }
};

继续加油~