跳转至

LeetCode: 390. 消除游戏

1、题目描述

给定一个从1 到 n 排序的整数列表。 首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。 第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。 我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。 返回长度为 n 的列表中,最后剩下的数字。

示例:

输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

输出:
6

2、解题思路

我们来找一下规律,

  • 首先,在第一轮中,奇数位置的全部都删掉,然后剩下的全部是偶数位置,而奇数位置的数字,二进制表示中,末尾一位都是1
  • 第二轮,反着删除,于是,能够被4整除的数字,都被删除了
  • 第三轮中,与第一轮一样,不过这一次看的是为位置,而不是数字,重复第一轮

当n=1,结果就是1

当n=2,结果就是2

当n=3,结果就是2

当n=4,结果就是2

当n=5,结果就是2

当n=6,结果就是4

根据前面的描述,每一次,每隔4个数字,我们看成一次,也就是说从前往后删除一轮,从后向前删除一轮,那么结果就是,每隔4个,保留的都是第二个数字

1 2 3 4 5 6 7 8
根据我们的规则,1,2,3,4中,保留第2个,然后是5,6,7,8中,保留第2个,也就是6
于是,我们就来找规律,首先,每一轮,数字肯定是偶数,因为第一次奇数就都被删掉了
然后剩下的数,会有两种情况,能被4整除,不能被4整除
首先看不能被4整除的情况
1 2 3 4 5 6
这时候,剩下的不是恰好第2个,而是第4个元素
如果是 
1 2 3 4 5 6 7 8
能够被4整除的情况下,剩下的就是2,6
发现了一个规律,能被4整除的话,剩下的数乘以4,要减去2才可以
不能被4整除,也就是说剩下的是4的倍数
再来看个例子,如果是
1 2 3 4 5 6 7 8 9 10
经过一轮,剩下的是 4,8


哈哈,规律很明显了,
假如能被4整除,剩下的数字,就是每4个数字中的第2个,是4的倍数-2
如果不能被4整除,那么,剩下的数字,就是从后向前,每4个数字中的第2个,这时候,正好是4的倍数
class Solution:
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n == 1:
            return 1
        if n <= 4:
            return 2

        if n % 2 != 0:
            n -= 1

        if n % 4 != 0:
            return 4 * self.lastRemaining(n // 4)
        else:
            return 4 * self.lastRemaining(n // 4) - 2