python-leetcode-390-消除游戏

本文主要是介绍python-leetcode-390-消除游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

示例：

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

代码 1：

class Solution:def lastRemaining(self, num):if num == 0 or num == 1:return numelse:     num = [i for i in range(1, num+1)]while len(num) > 1:num0 = []num1 = []for i in range(len(num)):if i % 2 != 0:num0.append(num[i])num = num0 if len(num) == 1:breaknum.sort(reverse=True)  for i in range(len(num)):               if i % 2 != 0:num1.append(num[i])          num = num1               num.sort()return num[0]

哈哈哈，当num=1000000时，此做法会爆内存~

代码 2：

class Solution(object):def lastRemaining(self, n):""":type n: int:rtype: int"""if n == 1:return 1else:return 2*((n//2)+1-self.lastRemaining(n//2))

使用递归方法

这篇关于python-leetcode-390-消除游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---