[Code] 闲聊判圈算法

作者: 敲代码的密斯想 | 来源:发表于2017-08-14 18:04 被阅读60次
在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

相关文章

  • [Code] 闲聊判圈算法

    在LeetCode上看到一道题 #141 Given a linked list, determine if i...

  • 转载 闲聊判圈算法

    转载 闲聊判圈算法floyd(Floyd cycle detection) 问题:如何检测一个链表是否有环,...

  • Floyd判圈算法(龟兔赛跑算法)

    点击查看原文一、算法简述 Floyd判圈算法(Floyd Cycle Detection Algorithm),又...

  • floyd判圈算法

    问题:如何检测一个链表是否有环,如果有,那么如何确定环的起点.要求 : 空间复杂度为O(1), 时间复杂度为O(n...

  • 判环算法以及链表常见算法题

    由于涉及到Floyd判环算法,故先简单阐述一下Floyd判环算法原理。Floyd判环算法算法原理:设置两个指针同时...

  • lintcode 126 堆栈用法

    思路 以及算法过程:图片.png code:

  • 判活算法

    引用计数算法 很多教科书判断对象是否存活的算法是这样的:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器...

  • 闲聊 Hash 算法

    最近读了一篇好文:【微信高并发资金交易系统设计方案——百亿红包背后的技术支撑】,其中关于高并发性能问题的解决方案中...

  • 【算法】Code Review

    1.架构/设计 单一职责原则 一个类只干一件事情,一个方法只干一件事情,常见的违背:类即干UI,又干逻辑 行为是否...

  • JAVA加解密8-消息摘要算法-MAC算法系列

    一、简述mac(Message Authentication Code,消息认证码算法)是含有密钥散列函数算法,兼...

网友评论

    本文标题:[Code] 闲聊判圈算法

    本文链接:https://www.haomeiwen.com/subject/wltprxtx.html