题目描述:每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF 作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!\^_\^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

Solutions

  刚开始尝试用平移的办法,考虑的情况太多,总是不能 AC,结果弄得有点儿烦了。一般来说解法不够优雅基本上都不太可能是可能的解法,目的是将数组弄成环的形式,这样的话方便循环遍历,那么可以利用引入链表的形式。

# -*- coding:utf-8 -*-
class LinkedList(object):
    """docstring for LinkedList"""
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n <=0 or m <= 0:
            return -1
        pHead = self.build_cicle(n)

        step = 0
        while pHead:
            step += 1
            if step == m:
                if pHead.next == pHead:
                    return pHead.val
                else:
                    pHead.val = pHead.next.val
                    pHead.next = pHead.next.next
                step = 0
            else:
                pHead = pHead.next

    def build_cicle(self, n):
        pHead = None
        pNode = None

        for i in range(n):
            if pNode is None:
                pHead = LinkedList(i)
                pNode = pHead 
            else:
                pNode.next = LinkedList(i)
                pNode = pNode.next
        pNode.next = pHead
        return pHead
# 运行时间:924ms
# 占用内存:5860k

  从运算时间来看,这样的慢速度很明显是不可以的,效率是 $O(mn)$。为了提速参考了经典约瑟夫环问题的解决,动态规划的方法。

  假设 0~n-1 的数中,已经排除了第 m-1 个数,那么下一轮的数字排序应该是,m, m+1, m+2, …, m-3, m-2,如果将这个数字序列重新映射成 0~n-2的话有:

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

  中间这些数的计算只需要对应到两头的数(左边的 m-2,右边的 n-2,然后看对应相隔多少),通过以上的对应关系我们可以得到如下的公式:

  于是问题就转化成动态规划的问题了,即 0~n-1 序列中最后剩下的数字等于(0~n-2序列中最后剩下的数字+m)%n,很明显当 n=1 时,只有一个数,那么剩下的数字就是 0.

  于是一激动就写下了如下的递归代码:

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n <= 0 or m <= 0:
            return -1
        if n == 1:
            return 0

        return (self.LastRemaining_Solution(n-1, m) + m) % n
# 4000,997
# maximum recursion depth exceeded

  很争气的报错了,迭代太深了,于是采用循环重写,即从 0 开始网上堆:

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n <= 0 or m <= 0:
            return -1
        res = 0
        for i in range(1, n+1):
            res = (res + m) % i
        return res
# 运行时间:29ms
# 占用内存:5728k

References

  1. 045. 圆圈中最后剩下的数字