假設我們已知區間空間的總大小。假設我們還得到了一個元組數組，為我們提供了要求和的區間的開始索引和結束索引以及一個值。完成所有求和后，我們想返回最大元素。我該如何有效地解決這個問題？輸入格式：n = 間隔空間，間隔 = 包含起始索引、結束索引和要添加到每個元素的值的元組數組 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.到目前為止我所想到的只是拼接數組并向拼接部分添加一個值的強力解決方案。我怎樣才能做得更好？任何幫助表示贊賞！
3 回答
溫溫醬
TA貢獻1752條經驗 獲得超4個贊
一種方法是將間隔分為開始和結束，并根據您是否處于該間隔內指定在總數中添加或減去多少。根據間隔在數軸上的位置對間隔進行排序后，您可以遍歷它，根據您是否進入或離開間隔來添加或減去值。下面是一些執行此操作的代碼：
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貢獻1853條經驗 獲得超9個贊
這是 3 個間隔的代碼。
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貢獻1798條經驗 獲得超7個贊
您可以使用列表理解來完成很多工作。
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
添加回答
舉報
0/150
提交
取消