时间戳

首页 > 解决方案 > 为什么我的程序只能在迭代字符串而不是列表时成功处理大量数据？

python - 为什么我的程序只能在迭代字符串而不是列表时成功处理大量数据？

问题描述

我正在筛选 Hackerrank 上的问题——我偶然发现了一个令人困惑的障碍。以下是必须编程的游戏规则（“小黄人游戏”）： 给两个玩家相同的字符串。两个玩家都必须使用字符串的字母来制作子字符串。斯图尔特必须造以辅音开头的单词。凯文必须以元音开头的单词。当两个玩家都做出所有可能的子串时，游戏结束。

例如，在字符串 BOB 中，OB 将被视为以元音开头的有效单词/子字符串，因此将给 Kevin 一个分数。

在尝试这个程序时，我创建了以下程序：

def minion_game(string):

    v = ['A','E','I','O','U']
    c = [
            'B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'M' ,'N', 'P', 'Q', 'R', 'S', 
            'T', 'V', 'W', 'X', 'Y' 'Z'
        ]

    L = list(string)

    s = 0
    k = 0

    for i in range(len(L)):
        if L[i] in v:
            k += len(L) - i
        elif L[i] in c:
            s += len(L) - i

    if s > k:
        print(f"Stuart {s}")
    elif k > s:
        print(f"Kevin {k}")
    elif k == s:
        print("Draw")

该程序对大多数测试用例都有效，但是在输入字符串很大的测试用例中，程序会失败。例如，对于其中一个测试用例，预期的输出是 Stuart 406312，但由于某种原因，我创建的程序失败了。

然后我创建了以下程序，它适用于所有测试用例：

def minion_game(string):
    vowels = 'AEIOU'
    length = len(string)
    k, s = 0, 0

    for i in range(length):
        if string[i] in vowels:
            k += (length - i)
        else:
            s += (length - i)

    if k > s:
        print("Kevin", k)
    elif k < s:
        print("Stuart", s)
    else:
        print("Draw")

我的问题是——为什么我的第一个程序失败了一些测试用例，而我的第二个程序通过了所有测试用例？是因为我使用字符串而不是列表，为什么这会有所不同（除了效率）？

感谢您提前抽出时间。

标签： python

解决方案

Python 中的字符串搜索使用fastsearch它是Boyer-Moore-Horspool 算法和几个巧妙技巧的混合。查找成本O(1)。

O(n)如果是列表，您只需扫描它以查找项目，每次查找的成本都是如此。

推荐阅读