leetcode_390

发表于   |   分类于

Elimination Game

题目戳这

题意

给定数字n，对有序序列1-n做如下操作：

从左往右开始隔一个划掉一个数字，也就是说从第一轮过后只剩下偶数项。

从右往左开始隔一个划掉一个数字。

重复上面连个步骤直到序列中只剩下一个数字，求这个数字是多少。

解法

找了好久的规律，还以为是有什么公式可归纳。。不过看了人家的解法发现就是去模拟这个过程，当然是高效的模拟。解题思路

大致说一下，就是用head来维护最后剩下的数字，step用来维护步长，因为每一次去除n/2个数字以后，步长都会加倍，比如1,2,3,4,5，步长为1，第一步以后剩下2,4，步长就为2了。然后什么时候改变head呢？就是当从左往右的时候，此时head肯定是会被去除的。这是第一种情况，还有一种情况就是当从右往左且此时的序列长度为奇数的时候，比如2,4,6，那么此时head=2是会被去除的。所以要在这两种情况下移动head。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """
        rm = n
        step = 1
        head = 1
        flag = 1
        while rm > 1:
            if flag or rm % 2 == 1:
                head += step
            
            step *= 2
            rm /= 2
            flag ^= 1
        
        return head