查找递增序列的第 n 个字符

Question

最近看到一道编程题，bruteforce方法不满足时间复杂度，请问还有其他解决办法吗，

问题：

给出一个以'a'开头的扩展序列，我们应该按以下方式替换每个字符，

a=>ab

b=>cd

c=>cd

d=>ab

每次迭代都会像这样，

一个

ab

abcd

abcdcdab

abcdcdabcdababcd

....... 一个数字 n 将作为输入给出，函数应该 return 第 n 个位置的字符。

我已经通过形成完整的字符串并在超过 n.but 时间限制时 returning char 尝试了蛮力方法。

我尝试了以下方法：

dictionary={
    'a':'ab',
    'b':'cd',
    'c':'cd',
    'd':'ab'
}

string="a"

n=128
while len(string)<n:
    new_string=''
    for i in string:
        new_string+=dictionary[i]
    string=new_string
print(string[n-1])

Answer 1

解决此类问题的方法永远不会实际生成所有字符串。

这是一个直接通过替换树下降的快速解决方案：

dictionary={
    'a':['a','b'],
    'b':['c','d'],
    'c':['c','d'],
    'd':['a','b']
}

def nth_char(n):
    # Determine how many levels of substitution are reqired
    # to produce the nth character.
    # Remember the size of the last level
    levels = 1
    totalchars = 1
    lastlevelsize = 1
    while totalchars < n:
        levels += 1
        lastlevelsize *= 2
        totalchars += lastlevelsize
        
    # position of the target char in the last level
    pos = (n-1) - (totalchars - lastlevelsize)
    
    # start at char 1, and find the path to the target char
    # through the levels
    current = 'a'
    while levels > 1:
        levels -= 1
        # next iteration, we'll go to the left or right subtree
        totalchars -= lastlevelsize
        # half of the last level size is the last level size in the next iteration
        lastlevelsize = lastlevelsize//2
        # is the target char a child of the left or right subtitution product?
        # each corresponds to a contiguous part of the last level
        if pos < lastlevelsize:
            #left - take the left part of the last level
            current = dictionary[current][0]
        else:
            #right - take the right part of the last level
            current = dictionary[current][1]
            pos -= lastlevelsize

    return current
    
print(nth_char(17))

查找递增序列的第 n 个字符

Find the nth character of an increasing sequence

python

algorithm

math

logic

data-structures