[已解决]Python：每日一题 350

zltzlt

今天的题目：

0, 1, ..., n-1 这 n 个数字排成一个圆圈。

从数字 0 开始，每次从这个圆圈里删除第 m 个数字。

求这个圆圈里剩下的最后一个数字。

示例 1：

输入：n = 5, m = 3
输出：3
解释：0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始，每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。

示例 2：

输入：n = 10, m = 17
输出：2

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-3-12 13:35:15

复杂度O（n）

1. def fun350(n,m):
   
2.     result = 0
   
3.     for index in range(1,n+1):
   
4.         result = (result + m)%index
   
5.     return result

复制代码

跳转到最佳答案楼层

风魔孤行者

1. def f(n,m):
   
2.     list1 = [i for i in range(n)]
   
3.     while len(list1) > 1:
   
4.         a = m-len(list1)
   
5.         while a>0:
   
6.             a -= len(list1)
   
7.         list1 = list1[a+len(list1):] + list1[:a+len(list1)-1]
   
8.     return list1[0]
   

复制代码

flamezyy

1. def f350(n,m):
   
2.     list_cir = list(range(n))
   
3.     while(n > 1):
   
4.         index_num = m % n - 1
   
5.         list_cir.pop(index_num)
   
6.         n -= 1
   
7.         if index_num == -1:
   
8.             continue
   
9.         else:
   
10.             list_cir = list_cir[index_num:] + list_cir[:index_num]
    
11.     return (list_cir.pop())

复制代码

zltzlt

风魔孤行者 发表于 2020-3-12 13:23

输入以下数据超时：

1. n = 70866, m = 116922

复制代码

xiaofan1228

1. n = int(input("Please input a positive range:"))
   
2. m = int(input("Please input period:"))
   
3. list1 = [i for i in range(n)]
   
4. record = []
   
5. 
   
6. while True:
   
7.     if m > len(list1):
   
8.         minStep = m % len(list1)
   
9.     else:
   
10.         minStep = m
    
11.    
    
12.     if len(list1) >= 3:
    
13.         a = list1.pop(minStep-1)
    
14.         record.append(a)
    
15.         print("Remove %d" %a)
    
16.         list1 = list1[minStep-1:] + list1[:minStep-1]
    
17.         print(list1)
    
18.     if len(list1) == 2:
    
19.         if m % 2:
    
20.             a = list1.pop(0)
    
21.             record.append(a)
    
22.             print('Final==>%d' %list1[0])
    
23.         if not m % 2:
    
24.             a = list1.pop(1)
    
25.             record.append(a)
    
26.             print('Final==>%d' %list1[0])
    
27. 
    
28.         break
    

复制代码

回来了，新手不太明白超时的定义。。。想着节省运算次数就可以避免超时？

更新：卧槽感受到了超时的快感。。。

简直了。。。

TJBEST

复杂度O（n）

1. def fun350(n,m):
   
2.     result = 0
   
3.     for index in range(1,n+1):
   
4.         result = (result + m)%index
   
5.     return result

复制代码

zltzlt

flamezyy 发表于 2020-3-12 13:32

输入以下数据超时：

1. n = 70866, m = 116922

复制代码

阴阳神万物主

难度评级：简单
要素分析：模拟，循环
感受：总感觉可以有公式直接算出剩下的数字，但是我没有探索出来。

1. def solve(n,m):
   
2.     temp = list(range(n))
   
3.     m -= 1
   
4.     i = 0
   
5.     while 1:
   
6.         try:
   
7.             temp[1]
   
8.             i += m
   
9.             i %= len(temp)
   
10.             temp.pop(i)
    
11.         except IndexError:
    
12.             return temp[0]
    
13. if __name__ == '__main__':
    
14.     print("示例1 输出：",solve(5,3))
    
15.     print("示例2 输出：",solve(10,17))
    

复制代码

kinkon

我也提供一种思路，先定义n = [i for i in range(n)]*m,从中删减或者直接计算，速度应该会快很多

fan1993423

kinkon 发表于 2020-3-12 14:37
我也提供一种思路，先定义n = *m,从中删减或者直接计算，速度应该会快很多

这个不行哦，就第一个列子的话，第三次循环就会把正确答案3去掉

kinkon

fan1993423 发表于 2020-3-12 14:49
这个不行哦，就第一个列子的话，第三次循环就会把正确答案3去掉

删不掉啊，n = [i for i in range(n)]*m，这里乘了m，也是可以算出来，现在上班，头脑有点乱

mdphd

1. m = int(input("请输入m的值："))
   
2. n = int(input("请输入n的值："))
   
3. x = 0
   
4. for i in range(1, n):
   
5.     x = (x + m) % (i + 1)
   
6. print(x)
   
7. 
   

复制代码

这样应该可以了

最后的魁拔

1. a,b=input().split()
   
2. c=[i for i in range(0,int(a))]
   
3. index= 0
   
4. while len(c)!=1:
   
5.     temp=c[:]
   
6.     for i in temp:
   
7.         index +=1
   
8.         if index == int(b):
   
9.             c.remove(i)
   
10.             index=0
    
11.         
    
12.             
    
13. print(c)

复制代码

catwine1990

1. def ysf(n,m):
   
2.      quit=[]
   
3.      lst=list((range(0,n)))
   
4.      count=1
   
5.      if  len(lst)> 1:
   
6.          for i in range(0,n):
   
7.               if  count==m:
   
8.                  quit.append(i)
   
9.                  del lst[i]
   
10.                  count=1
    
11.               else:
    
12.                   lst.append(lst.pop(i))
    
13.                   count+=1
    
14.        print('最后剩下的数字%d'%lst[0])  
    
15.        print('淘汰顺序为：'+quit)

复制代码

TJBEST

楼主，见6楼 已更改

whosyourdaddy

def func350(n,m):
    a = [i for i in range(0,n)]
    temp = 0
    while n!=1:
        temp = (temp + m)%n - 1
        a.pop(temp)
        if temp== -1:
            temp = 0
        n -=1
    return a[0]

fan1993423

1. def fun350(n,m):
   
2.     s=list(range(n))
   
3.     index=m%n-1
   
4.     s.pop(index)
   
5.     while len(s)>1:
   
6.         if index<0:index=0
   
7.         index+=m
   
8.         if index>len(s):
   
9.             index%=len(s)
   
10.         index-=1
    
11.         s.pop(index)
    
12.     return s[0]

复制代码

不知道对不对，先写一个

Herry2020

def zqq(n,m):
        list = [i for i in range(n)]
        length = len(list)
        k =m%length
        while True:
                list.pop(k-1)
                if k!=0:
                        list=list[k-1:n] + list[0:k-1]
                n-=1
                length = len(list)
                k =m%length
                if length == 1:
                        break
        result=list[0]
        print(result)

zqq(5,3)
zqq(10,17)

fan1993423

TJBEST 发表于 2020-3-12 16:26
楼主，见6楼 已更改

看来12楼的公式是对的了，我没找到公式，刚才测了一下，大数据能出来

zltzlt

TJBEST 发表于 2020-3-12 13:35
复杂度O（n）

88 ms