python-3.x - 处理内存不足的问题。动态规划

Question

我正在使用 python 解决一个问题，这里我在一个字符串中存储了一个重复的字符串“abc”，每次每个字符都像“abcaabbccaaaabbbbbcccc ............”，我必须找到第 n 个字符。约束条件为 n<=10^9，现在当我尝试存储它时出现内存错误，因为字符串太大(我尝试存储所有字符直到字符重复 2^30 次)。CAn有人帮我解决这个问题。

t=' '
for i in range(0 , 30):
    t = t +'a'*(2**i)
    t = t +'b'*(2**i)
    t = t +'c'*(2**i)

Answer 1

显然，您不能以直接、蛮力的方式执行此操作。相反，您需要沿着虚拟字符串计数以找到给定索引出现的位置。我会详细说明这一点，以便您可以看到逻辑:

n = 314159265    # Pick a large value for illustration
rem = n

for i in range(0 , 30):
    size = 2**i
    # print(size, rem)
    rem -= size
    if rem <= 0:
        char = 'a'
        break
    rem -= size
    if rem <= 0:
        char = 'b'
        break
    rem -= size
    if rem <= 0:
        char = 'c'
        break

print("Character", n, "is", char)

输出:

Character 314159265 is b

您可以使用更好的循环体来缩短它；我将把它留作进一步练习。如果您对自己的算法有深入的了解，则可以根据生成的 block 大小简单地计算出合适的字母。