python - 我应该怎么做才能减少代码的运行时间？

问题描述

这是一个 URI 在线判断问题（问题编号：1973）。

在圣卡塔琳娜州西部地区购买了许多相邻的农场后，Star 家族修建了一条单一的道路，依次经过所有农场。该序列的第一个农场被命名为 Star 1，第二个农场被命名为 Star 2，依此类推。然而，住在一号星的哥哥气急败坏，决定制作星际迷航，以从兄弟姐妹的礼节中偷羊。但他绝对是疯了。当经过农场 Star i 时，他只从该农场偷走一只羊（如果有的话），然后移动到 Star i + 1 或 Star i - 1，这取决于 Star i 中的羊数量是否分别为，奇数或偶数。如果没有他想去的星星，他就会停止他的跋涉。疯狂的兄弟在星际 1 中开始了他的星际迷航，从他自己的农场偷了一只羊。

输入

第一个输入行由一个整数 N (1 ≤ N ≤ 106) 组成，表示星星的数量。第二个输入行由 N 个整数组成，其中第 i 个整数 Xi (1 ≤ Xi ≤ 106) 表示 Star i 中的初始绵羊数量。

输出

输出一行，包含两个整数，第一个代表被狂哥攻击的星星数量，第二个代表未被偷走的羊的总数。

我已经解决了这个问题，也给出了想要的输出，但是每次我提交它都说超过了时间限制。

#1st solution:
num_star = int(input())
sheep = list(map(int, input().split()))
star = set()
index = 0

while index != num_star:
    if sheep[index] == 0:
        break
    elif sheep[index] % 2 == 1:
        star.add(index)
        sheep[index] -= 1
        index += 1
    else:
        star.add(index)
        sheep[index] -= 1
        index -= 1
        if index == -1:
            break

print(len(star), sum(sheep))

#2nd solution
n = int(input())
x = list(map(int, input().split()))
i = 0
farm_visited = 0
while i in range(n):
    if x[i] == 0:
        if i >= farm_visited: farm_visited = i+1
        break
    elif (x[i]) % 2 == 1:
        if i >= farm_visited: farm_visited = i + 1
        x[i] -= 1
        i += 1
    else:
        if i >= farm_visited: farm_visited = i + 1
        x[i] -= 1
        i -= 1
print(farm_visited, sum(x))

标签： pythonpython-3.xalgorithm

如果您想自己解决，请不要阅读下文。

def madstar(s): # s is the list
    if all(e % 2 for e in s): # all Stars with odd numbers
        return (len(s), sum(s)-len(s)) # just one sheep stolen from each Star
    for i,e in enumerate(s):
        if e % 2 == 0: # even number found
            return (i+1, # Stars are numbered from 0, so i==0 -> 1 Star visited etc.
                    sum(s) - ( # stolen sheep
                           2*(i+1) # two for every visited Star 
                           - s[:i].count(1) # except visited Stars with initially only 1 sheep
                           - (1 if e>0 else 2) # and the final one, where it is either 0 or 1, but never 2
            ))

for test_list in [[1,3,5,7,11,13,17,19],
                  [1,3,5,7,11,13,16,19],
                  [1],
                  [3,0,2],
                  [0],
                  [2]]:
    print(test_list, '->', madstar(test_list))

python - 我应该怎么做才能减少代码的运行时间？

问题描述

解决方案

推荐阅读