Leetcode Summary 01 — Cycle Detection

前言

前段时间忙于找工作，因而有正大光明的托词和导师说，11月之后再去做课题相关的事情，也就有了一段较为自由的时间。 其中诸多准备，免不了在Leetcode上刷题，虽然对于最终的结果来说没有帮助，但刷题过程中遇到了一些解决思路相似的问题，就依次将这些共性问题阐述一遍罢了。 本系列的第一篇介绍的是环检测问题，对应的维基百科页面有Cycle detection。这类问题最常见的求解算法是Floyd Cycle Algorithm/Floyd's Tortoise and Hare，中文名通常为Floyd判圈算法/龟兔赛跑算法。

<!--more-->

1. 问题描述

在计算机科学中，有一类问题称之为环检测问题，即对于一个由迭代函数(iterated function)值组成的序列，判断该序列是否有环及环出现的位置。 关于什么是迭代函数(iterated function)，严格定义可以查看这里，简单来说就是一个函数$f$，其定义域和值域都是集合$X$，那么对于某个自变量/输入$a$，其因变量/输出$b$也可以作为函数$f$的自变量/输入，如此给定一个初始值$x$，将$f$的每一次输出作为下一次的输入，如此重复$n$次，就称作函数$f$的第$n$次迭代。

对于上述函数$f$，如果其集合$X$是有限的，那么对于序列:

$$S = \{x_0, x_1 = f(x_0), x_2 = f(x_1), \cdots, x_i = f(x_{i-1}), \cdots\}$$

那么必然会有两个位置$i$和$j$，且$i < j$，其$x_i = x_j$，一旦出现这种状况，显然在$j$位置之后，会重复从$x_i$到$x_{j-1}$的序列。所谓环检测问题，就是给定$f$和$x_0$，要求找到$i$和$j$。 当然对于无限集合$X$，是有可能不存在环的，这取决于$f$和$x_0$的共同作用。例如$f=x^2$，如果$X$的范围是复数域，那么$x_0=0,1,-1,e^{\frac{2\pi{}mi}{n}}$，则有环，否则没有。这里$m$的取值范围是整数，$n$的取值范围是${1,2,3,4,6,7,8,12,14,15,16,24,28,30,31,32,\cdots}$，就不仔细推导了，有兴趣的可以自行推导。

2. 求解算法

对于上述问题，最常见的算法是Floyd's Tortoise and Hare，其次还有Brent's algorithm和Gosper's algorithm等。 最直接的想法是记录每次迭代的值，建立一个hash表，这样可以在重复出现时直接定位，但是这种方法空间复杂度太高，故弃。

2.1 Floyd's Tortoise and Hare

对于问题描述中迭代函数组成的序列，如果存在环，那么对于$i\ge{}\mu$，则$x_i = x_{i+k\lambda}$，其中$\lambda$是环的长度，$\mu$是环的第一个元素出现的位置。 基于此，可以推出，$\exists{}i = k\lambda\ge\mu\Longrightarrow{}x_i = x_{2i}$ 因此，只要设定两个指针$P1$和$P2$，其中$P2$的步长是2，$P1$的步长是1，那么就可以找到两个指针指向值相等的位置，反过来说，即只要存在相等值，就存在环，此时可以得出$\nu = P2 - P1 = P1 = k\lambda$. 显然$x_{\mu{}+\nu} = x_{\mu}$，即$x_{\nu{}+\mu} = x_{\mu}$，故找到上述位置之后，$P1$仍保持原来位置，而$P2$放回序列最初位置，此时两个指针的推进步长都设置为1，两指针指向的值再次相等时，就是环开始的位置。找到环开始的位置后，向后迭代找到下一次重复位置，就可以得到环的长度$\lambda$了。

2.2 Brent's algorithm

Floyd's Tortoise and Hare算法很精巧，但是判断环存在、找到环开始位置和确定环长度需要分为三步，Brent's algorithm效率更高，且只需要两步。 Brent's algorithm也是利用了快慢两个指针的想法，但是它的想法是动态增加步长，加快搜索速度。 其基本意图是设立两个指针，尽快让第一个指针到达环内，然后第二个指针以步长1前进，再次相等时走过的步数正好是环的长度$\lambda$，具体做法如下。 首先，设定两个指针$P1$和$P2$，$P2$第一次先前进$2^0=1$步，在前进的过程中若始终$x_{P2}\ne{}x_{P1}$，则令$P1 = P2$，然后$P2$再前进$2^1=2$，在前进的过程中若始终$x_{P2}\ne{}x_{P1}$，则令$P1 = P2$，然后$P2$再前进$2^2=4$...... 如此，直到出现相等的位置，在出现相等位置之前，最后一次$P2$前进的步数就是环的长度$\lambda$。 此时，将$P1$放于序列开始位置0，$P2$放于$\lambda$位置，由于$x_{\mu} = x_{\lambda{}+\mu}$，故只要让$P1$和$P2$依次向前前进，等到两者指向值相同时，$P1$的位置正好就是环的开始位置。

Brent's algorithm的效率比Floyd's Tortoise and Hare要高，最差情况是Floyd's Tortoise and Hare算法。其主要原因是，步长动态增加，速度提高，以及首次找到相同值时，记录了环的长度，而Floyd's Tortoise and Hare算法首次找到相同值时，并不知道环的长度，只能知道环长度的整数倍。

2.3 Gosper's algorithm

Gosper算法可以参考此处，Kino还没有细看，就不细说了。

3. 相关练习

Leetcode上有以下数题与此相关。

3.1 Leetcode 141. Linked List Cycle

Link

Description: Given a linked list, determine if it has a cycle in it.

Floyd's Tortoise and Hare

class Solution {
public:
  bool hasCycle(ListNode *head) {
    if(!head || !(head->next)) {
      return false;
    }
    ListNode* tortoise = head->next;
    ListNode* hare = head->next->next;
    while(hare && hare->next) {
      if(tortoise == hare) {
        return true;
      }
      tortoise = tortoise->next;
      hare = hare->next->next;
    }
    
    return false;
  }
};

Brent's algorithm

class Solution {
public:
  bool hasCycle(ListNode *head) {
    if(!head || !(head->next)) {
      return false;
    }
    int current_step = 1;
    int limited_step = 1;
    ListNode* tortoise = head->next;
    ListNode* hare = head->next->next;
    while(hare && hare->next) {
      if(tortoise == hare) {
        return true;
      }
      if(current_step == limited_step) {
        current_step = 0;
        limited_step *= 2;
        tortoise = hare;
      }
      hare = hare->next;
      current_step++;
    }
    
    return false;
  }
};

3.2 Leetcode 142. Linked List Cycle II

Link

Description: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Floyd's Tortoise and Hare

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    if(!head || !(head->next)) {
      return NULL;
    }
    ListNode* tortoise = head->next;
    ListNode* hare = head->next->next;
    while(tortoise != hare) {
      if(!hare || !(hare->next)) {
        return NULL;
      }
      tortoise = tortoise->next;
      hare = hare->next->next;
    }
    
    tortoise = head;
    while(tortoise != hare) {
      tortoise = tortoise->next;
      hare = hare->next;
    }
    
    return tortoise;
  }
};

Brent's algorithm

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    if(!head || !(head->next)) {
      return NULL;
    }
    int current_step = 1;
    int limited_step = 1;
    ListNode* tortoise = head->next;
    ListNode* hare = head->next->next;
    while(tortoise != hare) {
      if(!hare || !(hare->next)) {
        return NULL;
      }
      if(current_step == limited_step) {
        current_step = 0;
        limited_step *= 2;
        tortoise = hare;
      }
      hare = hare->next;
      current_step++;
    }
    
    tortoise = head;
    hare = head;
    while(current_step--) {
      tortoise = tortoise->next;
    }
    
    while(tortoise != hare) {
      tortoise = tortoise->next;
      hare = hare->next;
    }
    
    return tortoise;
  }
};

3.3 Leetcode 202. Happy Number

Link

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.

Floyd's Tortoise and Hare

class Solution {
public:
  bool isHappy(int n) {
    int tortoise = nextNum(n);
    int hare = nextNum(nextNum(n));
    while(tortoise != hare) {
      tortoise = nextNum(tortoise);
      hare = nextNum(nextNum(hare));
    }
    
    return tortoise == 1;
  }
  
  int nextNum(int n) {
    int nxt = 0;
    while(n) {
      int digit = n%10;
      nxt += digit*digit;
      n /= 10;
    }
    
    return nxt;
  }
};

Brent's algorithm

class Solution {
public:
  bool isHappy(int n) {
    int current_step = 1;
    int limited_step = 1;
    int tortoise = nextNum(n);
    int hare = nextNum(nextNum(n));
    while(tortoise != hare) {
      if(current_step == limited_step) {
        current_step = 0;
        limited_step *= 2;
        tortoise = hare;
      }
      hare = nextNum(hare);
      current_step++;
    }
    
    return tortoise == 1;
  }
  
  int nextNum(int n) {
    int nxt = 0;
    while(n) {
      int digit = n%10;
      nxt += digit*digit;
      n /= 10;
    }
    
    return nxt;
  }
};

3.4 Leetcode 287. Find the Duplicate Number

Link

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Floyd's Tortoise and Hare

class Solution {
private:
  vector<int> nums;
public:
  int findDuplicate(vector<int>& nums) {
    if(nums.empty()) {
      return -1;
    }
    this->nums = nums;
    
    int tortoise = f(nums[0]);
    int hare = f(f(nums[0]));
    while(tortoise != hare) {
      tortoise = f(tortoise);
      hare = f(f(hare));
    }
    
    tortoise = nums[0];
    while(tortoise != hare) {
      tortoise = f(tortoise);
      hare = f(hare);
    }
    
    return tortoise;
  }
  
  int f(int n) {
    return nums[n];
  }
};

Brent's algorithm

class Solution {
private:
  vector<int> nums;
public:
  int findDuplicate(vector<int>& nums) {
    if(nums.empty()) {
      return -1;
    }
    this->nums = nums;
    
    int current_step = 1;
    int limited_step = 1;
    int tortoise = f(nums[0]);
    int hare = f(f(nums[0]));
    while(tortoise != hare) {
      if(current_step == limited_step) {
        current_step = 0;
        limited_step *= 2;
        tortoise = hare;
      }
      hare = f(hare);
      current_step++;
    }
    
    tortoise = nums[0];
    hare = nums[0];
    while(current_step--) {
      tortoise = f(tortoise);
    }
    
    while(tortoise != hare) {
      tortoise = f(tortoise);
      hare = f(hare);
    }
    
    return tortoise;
  }
  
  int f(int n) {
    return nums[n];
  }
};

4. 实际应用

环检测(cycle detection)问题的实际应用有 伪随机数生成器(pseudorandom number generators)强度的度量，比如 线性同余生成器(linear congruential generator)，加密哈希函数的冲突检测，细胞自动机(cellular automaton)的振荡周期配置等