剑指46-孩子们的游戏(圆圈中最后剩下的数)

Posted on | In |

题目描述

首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

约瑟夫环问题Josephus problem。

模拟法

此代码模拟了整个过程，只是在计算出列的编号时用了求余这个操作。

  • 如果某一圈从位置0开始报数0，圈的长度为L，则报m-1的小朋友的位置将是(m-1)%L。
  • 剔除该位置元素之后，将该位置左侧子序列和右侧子序列调换位置连起来形成一个新的序列，执行第一步。直到新序列只剩下一个元素。
1
2
3
4
5
6
7
8
9
class Solution:
    def LastRemaining_Solution(self, n, m):
        if n <= 0 or m <= 0:
            return -1 #该返回值在题目中有说
        boys = [i for i in range(n)]
        while len(boys) > 1:
            ix = (m - 1) % len(boys)
            boys = boys[ix+1:] + boys[:ix]
        return boys[0]

递归法

原问题标记为函数f(n, m)，表示n个小朋友序号为0, 1, ..., n-1，从0位置开始报0，报出m-1的出列，从下一个继续报0，最后剩下的小朋友的序号。该问题的首个出列序号可以按公式(m-1)%n来获得。

设想序列为0, 1, ..., n-1的首个小朋友（序号是m-1）出列后，剩下长度为n-1的序列标记为m, m+1, ..., n-2, n-1, 0, 1, 2, .., m-3, m-2，接下来仍然从第0位置开始报0，最后剩下的小朋友的序号。该问题的小朋友序列不是问题f(n-1, m)的0, 1, ..., n-2，因为其首个出列序号不能按公式(m-1)%(n-1)来计算。而是一个新问题，标记为g(n-1, m)，而且有f(n, m)=g(n-1, m)。

那么，如果能将g(n-1, m)用f(n-1, m)来表示，则可以用递归求解原问题了。

再看f(n-1, m)与g(n-1, m)的输入序列的对比：

x 0 1 ... n-m-1 n-m n-m+1 ... n-3 n-2
y m m+1 ... n-1 0 1 ... m-3 m-2

则有对应元素的映射关系y=(x+m)%n。

由于f(n-1, m)与g(n-1, m)的对应位置是相同的，所以二者的值可以套用上述映射关系，有g(n-1, m)=(f(n-1, m)+m)%n。 因此有递归公式f(n, m)=(f(n-1, m)+m)%n。

1
2
3
4
5
6
7
class Solution:
    def LastRemaining_Solution(self, n, m):
        if n <= 0 or m <= 0:
            return -1 
        if n == 1:
            return 0
        return (self.LastRemaining_Solution(n-1,m)+m)%n

注意栈溢出问题，实际测试中原始序列长度大于3700则会栈溢出。