塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-62圆圈中最后剩下的数字-python

《剑指offer》python实现系列,全目录

题目描述

0,1,…n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

第一想法:

1
2
3
4
5
6
7
8
        nlist = [i for i in range(0,n) ]
print(nlist)
count = 1
while len(nlist)>1:
count += 1
if count % m == 0:
nlist.pop('')
# 如何让链表变成环

剑指offer方法一:

约瑟夫环Josephuse问题

用环形链表模拟环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Node:
def __init__(self, value, next=None):
self.val = value
self.next = next

class Solution:
def LastRemaining_Solution(self, n, m):
if n<=0 or m<=0:
return -1
#构造环形链表
phead = cur = Node(0)
for i in range(1,n):
newnode = Node(i)
cur.next = newnode
cur = cur.next
cur.next = phead #构成环

cur = phead
while id(cur.next) != id(cur):#注意:通过id来判断是不是只剩下一个
for _ in range(m-1):
pre = cur
cur = cur.next
#删除第m个结点
pre.next = cur.next
cur = pre.next
return cur.val

Solution().LastRemaining_Solution(5,3)

缺点

许多结点重复遍历,而且需要额哇id辅助链表

剑指offer方法二:

利用约瑟夫环的公式

$$F ( n , m) = 0 $$ n=1

$$F ( n , m) = (f(n-1,m) + m) % n$$ n> 1

$F (n , m )$ 表示n个人报数,每报到m时杀掉的那个人,最终胜利者的编号

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def LastRemaining_Solution(self, n, m):
if n<=0 or m<=0:
return -1

last = 0
for i in range(2,n+1):
last = (last + m)%i

return last

Solution().LastRemaining_Solution(5,3)
if help:小手一抖点个广告 or 大手一挥资助一下