博客

今天在leetcode刷题时，碰到一个好玩的简单题

其实这道题的题干非常简单易懂，但是涉及到了一个无限循环的可能。

从数学上来说，如何证明它是无限循环而不是无限不循环也许是一个有挑战性的问题，但是这里我还给不出证明。

我们仅讨论如何利用快慢指针判断无限循环。

如果一个数列从某项开始是无限循环的数列，那必然

存在一个周期T，

使得f（x）==f（x+T）；

我们可以让slow指针去遍历整个数列，直到它进入循环，slow每次自增1，而fast每次多自增一次，即fast自增两次。

当slow==T时，fast=2*slow=2T；即有slow[i]==fast[i],此时可判定无限循环

代码如下

bool isHappy(int n) {
    int slow = n, fast = n;
    do {
        slow = bitSquareSum(slow); cout << "slow=" << slow << endl;
        fast = bitSquareSum(fast); cout << "fast=" << fast