[已解决]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）

def fun350(n,m):
    result = 0
    for index in range(1,n+1):
        result = (result + m)%index
    return result

跳转到最佳答案楼层

风魔孤行者

def f(n,m):
    list1 = [i for i in range(n)]
    while len(list1) > 1:
        a = m-len(list1)
        while a>0:
            a -= len(list1)
        list1 = list1[a+len(list1):] + list1[:a+len(list1)-1]
    return list1[0]

flamezyy

def f350(n,m):
    list_cir = list(range(n))
    while(n > 1):
        index_num = m % n - 1
        list_cir.pop(index_num)
        n -= 1
        if index_num == -1:
            continue
        else:
            list_cir = list_cir[index_num:] + list_cir[:index_num]
    return (list_cir.pop())

zltzlt

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

输入以下数据超时：

n = 70866, m = 116922

xiaofan1228

n = int(input("Please input a positive range:"))
m = int(input("Please input period:"))
list1 = [i for i in range(n)]
record = []

while True:
    if m > len(list1):
        minStep = m % len(list1)
    else:
        minStep = m
   
    if len(list1) >= 3:
        a = list1.pop(minStep-1)
        record.append(a)
        print("Remove %d" %a)
        list1 = list1[minStep-1:] + list1[:minStep-1]
        print(list1)
    if len(list1) == 2:
        if m % 2:
            a = list1.pop(0)
            record.append(a)
            print('Final==>%d' %list1[0])
        if not m % 2:
            a = list1.pop(1)
            record.append(a)
            print('Final==>%d' %list1[0])

        break

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

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

简直了。。。

TJBEST

复杂度O（n）

def fun350(n,m):
    result = 0
    for index in range(1,n+1):
        result = (result + m)%index
    return result

zltzlt

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

输入以下数据超时：

n = 70866, m = 116922

阴阳神万物主

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

def solve(n,m):
    temp = list(range(n))
    m -= 1
    i = 0
    while 1:
        try:
            temp[1]
            i += m
            i %= len(temp)
            temp.pop(i)
        except IndexError:
            return temp[0]
if __name__ == '__main__':
    print("示例1 输出：",solve(5,3))
    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

m = int(input("请输入m的值："))
n = int(input("请输入n的值："))
x = 0
for i in range(1, n):
    x = (x + m) % (i + 1)
print(x)

这样应该可以了

最后的魁拔

a,b=input().split()
c=[i for i in range(0,int(a))]
index= 0
while len(c)!=1:
    temp=c[:]
    for i in temp:
        index +=1
        if index == int(b):
            c.remove(i)
            index=0
        
            
print(c)

catwine1990

def ysf(n,m):
     quit=[]
     lst=list((range(0,n)))
     count=1
     if  len(lst)> 1:
         for i in range(0,n):
              if  count==m:
                 quit.append(i)
                 del lst[i]
                 count=1
              else:
                  lst.append(lst.pop(i))
                  count+=1
       print('最后剩下的数字%d'%lst[0])  
       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

def fun350(n,m):
    s=list(range(n))
    index=m%n-1
    s.pop(index)
    while len(s)>1:
        if index<0:index=0
        index+=m
        if index>len(s):
            index%=len(s)
        index-=1
        s.pop(index)
    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