假設(shè)我們已知區(qū)間空間的總大小。假設(shè)我們還得到了一個(gè)元組數(shù)組，為我們提供了要求和的區(qū)間的開(kāi)始索引和結(jié)束索引以及一個(gè)值。完成所有求和后，我們想返回最大元素。我該如何有效地解決這個(gè)問(wèn)題？輸入格式：n = 間隔空間，間隔 = 包含起始索引、結(jié)束索引和要添加到每個(gè)元素的值的元組數(shù)組 Eg: Input: n = 5, intervals = [(1,2,100),(2,5,100),(3,4,100)] Output: 200 so array is initially [0,0,0,0,0] At each iteration the following modifications will be made: 1) [100,100,0,0,0] 2) [100,200,100,100,100] 3) [100,200,200,200,100] Thus the answer is 200.到目前為止我所想到的只是拼接數(shù)組并向拼接部分添加一個(gè)值的強(qiáng)力解決方案。我怎樣才能做得更好？任何幫助表示贊賞！
3 回答
溫溫醬
TA貢獻(xiàn)1752條經(jīng)驗(yàn) 獲得超4個(gè)贊
一種方法是將間隔分為開(kāi)始和結(jié)束，并根據(jù)您是否處于該間隔內(nèi)指定在總數(shù)中添加或減去多少。根據(jù)間隔在數(shù)軸上的位置對(duì)間隔進(jìn)行排序后，您可以遍歷它，根據(jù)您是否進(jìn)入或離開(kāi)間隔來(lái)添加或減去值。下面是一些執(zhí)行此操作的代碼：
def find_max_val(intervals):
operations = []
for i in intervals:
operations.append([i[0],i[2]])
operations.append([i[1]+1,-i[2]])
unique_ops = defaultdict(int)
for operation in operations:
unique_ops[operation[0]] += operation[1]
sorted_keys = sorted(unique_ops.keys())
print(unique_ops)
curr_val = unique_ops[sorted_keys[0]]
max_val = curr_val
for key in sorted_keys[1:]:
curr_val += unique_ops[key]
max_val = max(max_val, curr_val)
return max_val
intervals = [(1,2,100),(2,5,100),(3,4,100)]
print(find_max_val(intervals))
# Output: 200
暮色呼如
TA貢獻(xiàn)1853條經(jīng)驗(yàn) 獲得超9個(gè)贊
這是 3 個(gè)間隔的代碼。
n = int(input())
x = [0]*n
interval = []
for i in range(3):
s = int(input()) #start
e = int(input()) #end
v = int(input()) #value
#add value
for i in range (s-1, e):
x[i] += v
print(max(x))
元芳怎么了
TA貢獻(xiàn)1798條經(jīng)驗(yàn) 獲得超7個(gè)贊
您可以使用列表理解來(lái)完成很多工作。
n=5
intervals = [(1,2,100),(2,5,100),(3,4,100)]
intlst = [[r[2] if i>=r[0]-1 and i<=r[1]-1 else 0 for i in range(n)] for r in intervals]
lst = [0]*n #[0,0,0,0,0]
for ls in intlst:
lst = [lst[i]+ls[i] for i in range(n)]
print(lst)
print(max(lst))
輸出
[100, 200, 200, 200, 100]
200
添加回答
舉報(bào)
0/150
提交
取消