python - 使用嵌套的 for 循环和 if 语句将字符替换为整数

Question

我需要输出任何重复的字符来引用前一个字符。

例如:a(-1)rdv(-4)(-4)k 或 hel(-1)o

到目前为止，这是我的代码:

text= 'aardvark'
i=0
j=0
for i in range(len(text)-1):
    for j in range(i+1, len(text)):
        if text[j]==text[i]:
            sub= text[j]
            val2=text.find(sub, i+1, len(text))
            p=val2+1
            val=str(i-j)
            text= text[:val2] + val + text[p:] 
            break
print(text)

输出:a-1rdva-4k

无法识别第二个 'a'。而且我不确定如何在打印中包含括号。

Answer 1

通过在每次找到反向引用时就地更新文本，您会弄乱索引(文本每次都会变长)并且您永远无法正确处理最后一个字符。当您发现“当前”字符的第一次重复时，您停止检查，因此第 3 个 a永远不会被处理。这适用于输入字符串中的每 3 次重复。此外，如果您的输入文本包含任何 -他们最终将针对 -offset 进行测试的字符或数字你在他们之前插入的引用也是如此!

对于您的具体示例 aardvark ，一个有 8 个字符的字符串，会发生这样的事情:

• 你找到第二个a并设置 text至 a-1rdvark .文本现在有 9 个字符长，所以最后一个 r永远不会被检查(你最多循环到 i = 6)；如果您的测试字符串以双字母结尾，这将是一个问题。你跳出循环，所以 j for循环永远不会出现在第 3 个 a ，第二个 a已更换，无法再测试。

• 您的代码找到 - (不再重复)，1 (不再重复)然后 r (重复一次)，所以现在你替换 text与 a-1rdva-4k .现在你有一个 10 个字符的字符串，所以 - , 和 4永远不会被测试。这不再是大问题，但如果字符串的最后 3 个位置出现重复怎么办？

为输出构建一个新的对象(添加您以前从未见过的字母和反向引用)。这样你就不会导致你正在循环的文本增长，你会继续找到重复；对于括号，您可以使用更多的字符串连接。您需要在 i 之前扫描字符串的一部分，而不是之后，为了让它起作用，然后倒退!检测i - 1 , i - 2等，降为 0。自然地，这意味着您的 i然后循环应该达到全长:

output = ''

for i in range(len(text)):
    current = text[i]
    for j in range(i - 1, -1, -1):
        if text[j] == current:
            current = '(' + str(j - i) + ')'
            break  
    output = output + current

print(output)

我在这里将修复保持在最低限度，但理想情况下我还会进行一些更多更改:

• 将所有处理过的字符和引用添加到新的列表而不是字符串，然后使用str.join()之后将该列表加入到输出中。这比每次迭代都重建字符串要高效得多。

• 使用两个循环意味着您在遍历文本的同时再次检查字符串中的每个字符，因此算法所用的步骤数会随着输入的长度呈指数增长。在计算机科学中，我们讨论算法的时间复杂度，而您的是 O(N^2)(N 平方)指数 算法。包含 1000 个字母的文本将需要多达 100 万个步骤来处理!您可以使用字典 来跟踪您看到的字母的索引，而不是循环指数次数。如果 current 字符在字典中，则您可以轻松计算偏移量。字典查找需要常数时间 (O(1))，使得整个算法需要 线性 时间 (O(N))，这意味着该过程花费的时间与输入字符串的长度成正比.

• 使用 enumerate() 在循环中添加一个计数器，这样你就可以直接循环字符，不需要使用 range() .

• 您可以使用字符串格式来构建 "(<offset>)"字符串; Python 3.6 和更新版本有 formatted string literals , 其中f'...'字符串取 {}只是表达式的占位符。 f'({some - calculation + or * other})' will execute the expression and put the result in a string that has ( and ) characters in it too. For earlier Python versions, you can use the [ str.format() method](https://docs.python.org/3/library/stdtypes.html#str.format) to get the same result; the syntax then becomes '({})'.format(some - calculation + or * other)`。

放在一起，就变成了:

def add_backrefs(text):
    output = []
    seen = {}
    for i, character in enumerate(text):
        if character in seen:
            # add a back-reference, we have seen this already
            output.append(f'({seen[character] - i})')
        else:
            # add the literal character instead
            output.append(character)
        # record the position of this character for later reference
        seen[character] = i
    return ''.join(output)

演示:

>>> add_backrefs('aardvark')
'a(-1)rdv(-4)(-4)k'
>>> add_backrefs('hello')
'hel(-1)o'