5,3
3
2,3
1
有2个小朋友编号为0，1，第一次报数报到3的是0号小朋友，0号小朋友出圈，1号小朋友得到礼物
10,17
2
class Solution: def LastRemaining_Solution(self, n, m): if n==0: return -1 a=[] for i in range(n): a.append(i) while len(a)>1: for i in range(m): a.append(a.pop(0)) a.pop() return a.pop()
# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): # write code here if n==0: return -1 s=[] for i in range(n): s.append(i) while len(s)!=1: new_n=len(s) if m>new_n: s.pop(m%new_n-1) if m%new_n !=0: s=s[m%new_n-1:]+s[:m%new_n-1] else: s.pop(m-1) s=s[m-1:]+s[:m-1] return s[-1]
# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): # write code here if len(n)==0: return -1 kids = [i for i in range(n)] # kids:x 1 2 3 4 # cnt: 0 1 2 3 4 5 # i: 0 1 2 3 4 0(0) # 1 x 3 4 # 0 1 2 3 4 5 # 0(1) 1 2 3 0 1(2) # x 3 4 # 0 1 2 3 4 5 # 1(3) 2 0 1 2 0(1) # 3 4 # 0 1 2 3 4 5 # 0(3) 1 0 1 0 1(4) cnt=0 i=0 while True: if cnt<m-1: # 5 if i<n-1: # 4x 3x 2x 1 i+=1 else: i=0 cnt+=1 else: #cnt==m-1 kids.pop(i) n=len(kids) if n==1: return kids[0] cnt=0
# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): if n == 0: return -1 list1 = [i for i in range(n)] position = 0 while len(list1) > 1: position = (position + m - 1) % len(list1) list1.pop(position) return list1[0]
# -*- coding:utf-8 -*- class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # 链表法 def LastRemaining_Solution(self, n, m): if n<1: return -1 head = ListNode(0) root = head for i in range(1,n): head.next = ListNode(i) head = head.next head.next = root lian = root for i in range(1,n): for j in range(1,m-1): lian = lian.next lian.next = lian.next.next lian = lian.next return lian.val
class Solution: def LastRemaining_Solution(self, n, m): # write code here if n==0&nbs***bsp;m == 0: return -1 ChildNum = range(0,n) cur = 0 while len(ChildNum) > 1: cur = (cur + m -1)% len(ChildNum) ChildNum.remove(ChildNum[cur]) return ChildNum[0]此题关键部分在于：
1,cur = (cur + m -1)% len(ChildNum)
2,ChildNum.remove(ChildNum[cur])假设开始m比n小，那么每次进行上述1操作之后，cur都刚好指向我们要remove的那个数；到了后来，如果cur+m-1比len（ChildNum）大，取余操作之后，指针cur会回到第二轮循环之后的位置。
# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): # write code here childrens = [i for i in range(n)] index = 0 final = -1 while childrens: #k为当前离开的小朋友的下标 k = (index + (m - 1)) % n final = childrens.pop(k) #当循环结束时，final指向最后一个小朋友 n -= 1 index = k #当下标k的元素被删除时，后面的元素向前一步，所以index仍然从k下标开始从后面计算下一个要离开的小朋友 return final
# -*- coding:utf-8 -*- """ 1. 构建一个头尾相连的环向链表 2. 只剩一个节点的判据是p = p.next """ class LinkedListNode: def __init__(self,val): self.val = val self.next = None class Solution: def LastRemaining_Solution(self, n, m): if n <0 or m <= 0: return -1 start = LinkedListNode(0) start_backup = start for i in range(1,n): start.next = LinkedListNode(i) start = start.next start.next = start_backup # loop while start_backup != start_backup.next: for i in range(1,m-1): start_backup = start_backup.next start_backup.next = start_backup.next.next start_backup = start_backup.next return start_backup.val s = Solution() ans = s.LastRemaining_Solution(5,3) print(ans)
# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): # write code here if n<=0: return -1 if n == 1: return n arrayn = [] for i in range(n): #将n个孩子们存为list，刚好数字 arrayn.append(i) #大小对应孩子们的初始位置 index = 0 while n>1: if n<m: index = (m-1)%n else: index = m-1 arrayn.pop(index) arrayn = arrayn[index:] + arrayn[0:index] #每次将下一个孩子作为表头 n -= 1 return arrayn[0]
class node: def __init__(self,element,next): self.element=element self.next=next class createcirclu: #使用循环链表表示循环队列 def __init__(self): #只设定一个指针就够了，因为是循环的 self.tailer=None self.size=0 def encirclu(self,e): #将元素加入到循环队列中 newnode=node(e,None) if self.size==0: newnode.next=newnode else: newnode.next=self.tailer.next self.tailer.next=newnode self.tailer=newnode self.size+=1 def dequeue(self): #删除循环队列的首元素，并将其值返回 if self.size==0: return False #我们通过self.tailer找首元素的位置 oldhead=self.tailer.next if self.size==1: self.tailer=None else: self.tailer.next=oldhead.next self.size-=1 return oldhead.element def rotate(self,m): #self.tailer在哪，双向队列的头元素就在其下一个位置，然后我们让其进行m-1次变化，改变self.tailer #到合适的位置 for i in range(m-1): self.tailer=self.tailer.next class Solution: def LastRemaining_Solution(self, n, m): # write code here if m<1&nbs***bsp;n<1: return -1 c1=createcirclu() list1=[] for i in range(n): c1.encirclu(i) while(c1.size!=0): #双向队列元素个数不空，就继续循环 c1.rotate(m) #让此时的self.tailer的位置到达m-2位置，则头节点在m-1位置 a=c1.dequeue() #将此节点从队列中删除出去，并返回其值 list1.append(a) return list1[-1]本题采用的是双向链表表示双向队列的方法，具体细节看代码
#想了半天，终于想明白了，好兴奋 # -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): # write code here #n: 表示总共人数 #m:每次喊到第m个数字时，这个孩子出列 #1 2 3 4 5 #1 2 4 5 #4 5 2 #4 5 #5 #如果没有小朋友 返回-1 ''' if n < 1: return -1 childList = list(range(n)) #每个学生进行编号 cur = 0 while len(childList) > 1: for i in range(1,m): cur += 1 if cur == len(childList):#如果m>剩余孩子的总人数，游标==0 cur = 0 childList.remove(childList[cur]) if cur == len(childList): cur = 0 return childList[0] ''' #动态规划 ''' if n <1: return -1 #当只剩下一个孩子的时候，最后一个孩子的索引为0 last = 0#当n == 1时，不进入for循环，直接返回last = 0 for i in range(2,n+1): last = (last + m)%i return last ''' ''' if n < 1 : return -1 con = range(n) start = 0 target = 0 while con: k = (start + m -1)%n target = con[k] con.pop(k) n -= 1 start = k return target ''' if n < 1 or m < 1: return -1 #当只剩下一个孩子的时候，最后一个孩子的索引为0 value = 0 #当n = 1时，并不会进入循环，直接返回value = 1 for index in range(2,n+1): #从最后一个人==>有两个人时候value对应的索引 ==>有三个人时候value对应的索引 #。。。。===> 有n个人的时候value对应的索引（即找到最后剩下的那个孩子） preValue = (value+m)%index value = preValue return value
# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): # write code here # 利用list内容存放小朋友 data=[] for i in range(n): data.append(i) count=0 j=0 while j<len(data): count=count+1 if count==m: count=0 data=data[:j]+data[j+1:] j=j-1 if len(data)==1: return data[0] j=j+1 #删掉了一个数，从当前这个数的后一个数开始 if j==len(data): j=0 return -1
# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): # write code here if n<=0 or m<=0: return -1 l=[i for i in range(n)] index=-1 while n>1: for i in range(m): if index>=len(l)-1: index=0 else: index+=1 l.pop(index) index-=1 n-=1 return l[0]时间复杂度比较大，容易理解
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
if not n:
return -1
list01=[i for i in range(n)]
res=0
#人数大于2时,执行删除操作
while len(list01)>1:
#删除的元素的索引值和起始值以及剩余人数有关
res=(res+m-1)%len(list01)
#删除后下一个起始值更新为已删除元素的索引
list01.pop(res)
return list01[0]
]# -*- coding:utf-8 -*- class Solution: def LastRemaining_Solution(self, n, m): if not n: return -1 dp=[-1]*(n+1) dp[1]=0 for i in range(1,n+1): dp[i]=(m+dp[i-1])%i return dp[-1]
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
如果只求最后一个报数胜利者的话，我们可以用数学归纳法解决该问题，为了讨 论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人 继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新 的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解： 例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情 况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n。
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]。
递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。 因为实际生活中编号总是从1开始，我们输出f[n]+1。
class Solution { public: int LastRemaining_Solution(unsigned int n, unsigned int m) { if(n==0) return -1; if(n==1) return 0; else return (LastRemaining_Solution(n-1,m)+m)%n; } };