[Code] 闲聊判圈算法

在LeetCode上看到一道题 #141

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

 Definition for singly-linked list.   
  class ListNode(object):  
     def __init__(self, x):  
         self.val = x  
         self.next = None  

如何确定链表是否有环呢？

Floyd判圈算法
假设龟兔从同一起点（链表的起始位置）出发，如果该链表有环，当兔子和乌龟均进入后，必定兔子会在领先乌龟一圈后与乌龟在链表的环中相遇。所以可以用以下代码判断链表是否有环。其中slow的起始位置为head，每次移动一步；fast的起始位置也为head，每次移动两步，当两者相遇时即说明该链表有环。

def hasCycle(self, head):
    try:
        slow = head
        fast = head.next
        while slow is not fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False

wiki上的python代码

def floyd(f, x0):
     tortoise = f(x0)       # f(x0) is the element/node next to x0.
     hare = f(f(x0))
     while tortoise != hare:
         tortoise = f(tortoise)
         hare = f(f(hare))
         if (tortoise == hare):
            return True
     return False

那么，如何判断环的长度呢？

首先要确定链表中有环。

假设环起始的位置距离链表起始距离为m，而环的长度为λ，第一次相遇点距离环的起点距离为k。则第一次相遇时乌龟走过的距离ν = m + λ * a + k， 兔子走过的距离2ν = m + λ * b + k。所以ν = (b-a) * λ 为环长度的倍数。

此时将兔子抓回起点命令其以和乌龟同样的速度行走，而乌龟则在原地继续以之前的速度行走。当兔子的行走距离为m（即走到环的起点）时，乌龟走了ν + m，而由于ν为环长度的倍数，所以此时乌龟也走在环的起点，即兔子和乌龟相遇在环的起点。

当然还有更简便的方法，当两者相遇后，命令乌龟静止不动，兔子降速为每次前进一步，当兔子再次遇见乌龟时，它比乌龟多跑的距离就是环的长度。

求环的长度

def floyd(f, x0):

    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

    # 方法一、乌龟回到原点，兔子降速（与兔子回原点降速相同）    
    m = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        m += 1
 
    # 方法二、乌龟静止不动，兔子降速每次前进一步
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, m

习得龟兔同跑的判圈算法后，来看一下LeetCode #202

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.

"happy数"的含义为：将一个数字的每位平方后相加，相加后的数继续进行每位平方后相加，如此循环，当相加到最后的数字始终为1时，即为"happy数"。

Example: 19 is a happy number

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Python解决方案：

def digitSquareSum(n):
    sum, tmp = 0, 0
    while n:
        tmp = n % 10
        sum += tmp * tmp
        n /= 10
    return sum


def isHappy(n):
    slow = digitSquareSum(n)
    fast = digitSquareSum(digitSquareSum(n))
    while slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    if slow == 1:
        return True
    else:
        return False