处理内存不足的问题。动态规划

Question

我正在使用python解决一个问题，在这里我将一个重复的字符串"abc"存储在一个字符串中，每次每个字符都像"abcaabbccaaaabbbbcccccc......"一样加倍，我必须找到第n个字符。约束是 n<=10^9 ，现在当我尝试存储它时，它们是内存错误，因为字符串太大(我试图存储所有字符，直到字符重复 2^30 次(。有人帮助我解决这种情况的方法。

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

您可以使用更好的环形体来缩短此时间;我将把它作为进一步的练习。 如果您对算术有见地，则可以简单地从生成的块大小中计算出适当的字母。