首頁猿問從兩個數組增加序列

從兩個數組增加序列

Python

12345678_0001 2023-06-13 16:58:43

給定兩個相同長度 n 的整數列表 a 和 b。找到嚴格遞增的整數序列的計數，i[0] < i[1] < ... < i[n-1]使得min(a[i], b[i]) <= i[i] <= max(a[i], b[i])對于每個i。例子輸入：a= [1,3,1,6]b= [6,5,4,4]輸出：4這四個序列將是：[1,3,4,5][1,3,4,6][2,3,4,5][2,3,4,5]這是我試過的a=[1,3,1,6]b=[6,5,4,4]P=[]for i in range(len(a)): if i<len(a)-1: if max(a[i],b[i])>=max(a[i+1],b[i+1]): P.append([x for x in range(min(a[i],b[i]),min(max(a[i],b[i]),max(a[i+1],b[i+1])))]) else: P.append([x for x in range(min(a[i],b[i]),1+min(max(a[i],b[i]),max(a[i+1],b[i+1])))]) else: P.append([x for x in range(min(a[i],b[i]),max(a[i],b[i])+1)])for i in range(len(a)): if i<len(a)-1 and P[i+1][-1]<=P[i][-1]: P[i]=[x for x in range(P[i][0],P[i+1][-1])] if i>0 and P[i][0]<=P[i-1][0]: P[i]=[x for x in range(P[i-1][0]+1,1+P[i][-1])cnt=1for i in P: cnt*=len(i)print(cnt)我所做的是我采用了這個設置1 2 3 4 5 6 3 4 5 1 2 3 4 4 5 6 并將其減少到這個1 2 3 4 5 6 刪除所有不會進入序列的數字?，F在我要做的是，只需乘以每個行序列的 len。當有這樣的情況時，問題就出現了。1 2 3 3 4 4 5 5 6 現在長度的簡單乘法不成立。這就是我被困的地方。

查看完整描述

1 回答

斯蒂芬大帝

TA貢獻1827條經驗獲得超8個贊

這是一種適合遞歸解決方案的問題，因此這里有一個可能的替代實現。（抱歉，我還沒有嘗試掌握您的代碼，也許其他人會。）

def sequences(a, b, start_index=0, min_val=None):

"""

yields a sequence of lists of partial solutions to the original

problem for sublists going from start_index to the end of the list

subject to the constraint that the first value cannot be less than

min_val (if not None)

Example: with a=[3,4,5,6], b=[6,5,0,4], start_index=2, minval=4,

it is looking at the [5,6] and the [0,4] part, and it would yield

[4,5] [4,6] and [5,6]

If the start index is not already the last one, then it uses a

recursive call.

"""

limits = a[start_index], b[start_index]

lower = min(limits)

higher = max(limits)

if min_val is not None and min_val > lower:

lower = min_val # impose constraint

options = range(lower, higher + 1)

is_last = start_index == len(a) - 1

for val in options:

if is_last:

yield [val]

else:

# val followed by each of the lists from the recursive

# callback - passing min_val=val+1 imposes the constraint

# of strictly increasing numbers

for seq in sequences(a, b, start_index+1, min_val=val+1):

yield [val, *seq]

for seq in sequences([1,3,1,6], [6,5,4,4]):

print(seq)

這給出：

[1, 3, 4, 5]

[1, 3, 4, 6]

[2, 3, 4, 5]

[2, 3, 4, 6]

請注意，我并不是說上面的方法特別有效：遞歸函數可能會使用相同的參數被調用不止一次——例如，無論您是從 1,3 還是 2,3 開始，它都會進行相同的計算來工作了解接下來會發生什么——因此您可能希望在將其用于大型列表之前實施某種緩存。顯然，緩存有內存開銷，因此制定最佳整體策略來應對這一問題可能是一個相當困難的問題。

反對回復 2023-06-13

1 回答
0 關注
145 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

從兩個數組增加序列

從兩個數組增加序列

1 回答

添加回答