給定n，一個表示二進制字串 a 長度的整數，它的開頭全是 '0'。
還給出了操作，一個字串陣列，每個字串代表這兩種型別之一的操作：
L : 用 0 找到最小的索引并將該索引處的字符替換為 1
C{index}：給定像 C0、C1 或 C50 等...，將索引處的字符（在命令中的 C 之后給出）替換為 0。
操作陣列示例：[L, L, C0, L , C3]
給出的時間限制是運行測驗用例的 3 秒。
我有12個案例通過，休息超時。（這是一個編碼考試的問題）
這是我的解決方案，請建議我可以進行哪些更改以通過所有測驗用例。
a = ""
for i in range(n):
a = a "0"
for x in operations:
if x == "L":
a = a.replace("0", "1", 1)
if "C" in x:
a = a[0:int(x[1:])] "0" a[int(x[1:]) 1:]
return a
超出時間限制的測驗用例是隱藏測驗用例，所以我不能在這里提供測驗用例。
感謝您的幫助。
uj5u.com熱心網友回復：
我認為有幾種方法可以用來提高代碼性能。第一個是@Mahrkeenerh 提到的，這將使用一個串列char而不是，str以便根據輸入索引替換值會更有效。第二種是使用heapq內置庫創建堆資料結構來存盤為零的索引串列（zero_indices在下面的代碼中）。使用此串列的好處是，zero_indices在使用常規 for 回圈搜索時，您可以獲得O(1) 時間復雜度而不是 O(n) 中的最小索引（更多詳細資訊請點擊此處）。所以當你得到L操作的時候，你只需要pop出最小的數inzero_indices并將索引值設定為'1'in alist即可。當你得到C<n>操作，您需要提取索引，將該索引分配到a串列中0并將新索引添加到zero_indices（性能將是O(logn)）。
總的來說，這種方法的性能將O(m(logn))取決于m操作次數和n字串長度。這比原始方法更有效，后者是O(mn)
import heapq
a = ['0'] * n
zero_indices = list(range(n))
for x in operations:
if x == "L":
# Pop the smallest index in zero_indices list O(1)
a[heapq.heappop(zero_indices)] = '1'
if "C" in x:
index = int(x[1:])
a[index] = '0'
# Insert new zero index into the list O(log(N))
heapq.heappush(zero_indices, index)
return "".join(a)
uj5u.com熱心網友回復：
簡單的答案，通過記住第一個 0 的位置：
def main(n, ops):
l = ["0"] * n
first_zero = 0
for op in ops:
if op[0] == "L":
l[first_zero] = "1"
first_zero = 1
# Find the next 0
for i, c in enumerate(l[first_zero:]):
if c == "0":
first_zero = i
break
else:
to_replace = int(op[1:])
l[to_replace] = "0"
first_zero = min(first_zero, to_replace)
return "".join(l)
n = 5
operations = ["L", "L", "C0", "L", "C3"]
print(main(n, operations))
# 11000
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/330972.html
下一篇：Python中的跳轉列印