首頁猿問從兩個(gè)數(shù)組增加序列

從兩個(gè)數(shù)組增加序列

Python

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

給定兩個(gè)相同長(zhǎng)度 n 的整數(shù)列表 a 和 b。找到嚴(yán)格遞增的整數(shù)序列的計(jì)數(shù)，i[0] < i[1] < ... < i[n-1]使得min(a[i], b[i]) <= i[i] <= max(a[i], b[i])對(duì)于每個(gè)i。例子輸入：a= [1,3,1,6]b= [6,5,4,4]輸出：4這四個(gè)序列將是：[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)我所做的是我采用了這個(gè)設(shè)置1 2 3 4 5 6 3 4 5 1 2 3 4 4 5 6 并將其減少到這個(gè)1 2 3 4 5 6 刪除所有不會(huì)進(jìn)入序列的數(shù)字?，F(xiàn)在我要做的是，只需乘以每個(gè)行序列的 len。當(dāng)有這樣的情況時(shí)，問題就出現(xiàn)了。1 2 3 3 4 4 5 5 6 現(xiàn)在長(zhǎng)度的簡(jiǎn)單乘法不成立。這就是我被困的地方。

查看完整描述

1 回答

斯蒂芬大帝

TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超8個(gè)贊

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

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]

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

反對(duì) 回復(fù) 2023-06-13