在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  

如何確定鏈表是否有環(huán)呢？

Floyd判圈算法
假設(shè)龜兔從同一起點(diǎn)（鏈表的起始位置）出發(fā)，如果該鏈表有環(huán)，當(dāng)兔子和烏龜均進(jìn)入后，必定兔子會(huì)在領(lǐng)先烏龜一圈后與烏龜在鏈表的環(huán)中相遇。所以可以用以下代碼判斷鏈表是否有環(huán)。其中slow的起始位置為head，每次移動(dòng)一步；fast的起始位置也為head，每次移動(dòng)兩步，當(dāng)兩者相遇時(shí)即說明該鏈表有環(huán)。

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

那么，如何判斷環(huán)的長(zhǎng)度呢？

首先要確定鏈表中有環(huán)。

假設(shè)環(huán)起始的位置距離鏈表起始距離為m，而環(huán)的長(zhǎng)度為λ，第一次相遇點(diǎn)距離環(huán)的起點(diǎn)距離為k。則第一次相遇時(shí)烏龜走過的距離ν = m + λ * a + k， 兔子走過的距離2ν = m + λ * b + k。所以ν = (b-a) * λ 為環(huán)長(zhǎng)度的倍數(shù)。

此時(shí)將兔子抓回起點(diǎn)命令其以和烏龜同樣的速度行走，而烏龜則在原地繼續(xù)以之前的速度行走。當(dāng)兔子的行走距離為m（即走到環(huán)的起點(diǎn)）時(shí)，烏龜走了ν + m，而由于ν為環(huán)長(zhǎng)度的倍數(shù)，所以此時(shí)烏龜也走在環(huán)的起點(diǎn)，即兔子和烏龜相遇在環(huán)的起點(diǎn)。

當(dāng)然還有更簡(jiǎn)便的方法，當(dāng)兩者相遇后，命令烏龜靜止不動(dòng)，兔子降速為每次前進(jìn)一步，當(dāng)兔子再次遇見烏龜時(shí)，它比烏龜多跑的距離就是環(huán)的長(zhǎng)度。

求環(huán)的長(zhǎng)度

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))

    # 方法一、烏龜回到原點(diǎn)，兔子降速（與兔子回原點(diǎn)降速相同）    
    m = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        m += 1
 
    # 方法二、烏龜靜止不動(dòng)，兔子降速每次前進(jìn)一步
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, m

習(xí)得龜兔同跑的判圈算法后，來看一下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數(shù)"的含義為：將一個(gè)數(shù)字的每位平方后相加，相加后的數(shù)繼續(xù)進(jìn)行每位平方后相加，如此循環(huán)，當(dāng)相加到最后的數(shù)字始終為1時(shí)，即為"happy數(shù)"。

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