最近我看到一個有競爭力的編碼問題，蠻力方法不符合時間復雜度，有沒有其他解決方案，
問題：
給出了一個以'a'開頭的擴展序列，我們應該按以下方式替換每個字符，
a=>ab
b=>cd
c=>cd
d=>ab
因為它在每次迭代中都會像這樣，
一種
抗體
A B C D
abcdcdab
abcdcdabcdababcd
....... 一個數字 n 將作為輸入，該函式應回傳第 n 個位置的字符。
我已經通過形成完整的字串并在 n.but 處回傳字符來嘗試蠻力方法，但超出了時間限制。
我嘗試了以下方法：
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])
uj5u.com熱心網友回復：
解決此類問題的方法是永遠不要實際生成所有字串。
這是一個直接通過替換樹下降的快速解決方案：
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))
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/474835.html
下一篇：Delta算子在sympy