鑒于此網格：
grid = [[10,23,16,25,12],
[19,11,8,1,4],
[3,6,9,7,20],
[18,24,4,17,5],
[7,3,4,6,1]]
其奇數行之和與偶數行之和之間差異最大的序列是第 1 行到第 3 行的序列。這是因為(10 23 16 25 12) - (19 11 8 1 4) (3 6 9 7 20) = 88這是所有此類序列中最大差異的序列。
該序列應該有一個偶數行和一個奇數行，因此它必須至少有 2 行。最大行數取決于網格的大小。
問題是我需要它來處理O(log n) 時間復雜度。我的想法是使用遞回將網格劃分為 2 并從那里解決它。但是，它沒有按我的意愿作業。
這是我的整個代碼：
import math
class Sequence:
def __init__(self,grids):
self.grids = grids
self.calculate_max_difference()
def calculate_max_difference(self):
# Get the odd and even rows using list slicing
odd_rows = self.grids[::2]
even_rows = self.grids[1::2]
odd_sum = 0
even_sum = 0
for odd_lst in odd_rows:
odd_sum = sum(odd_lst)
for even_lst in even_rows:
even_sum = sum(even_lst)
self.diff = odd_sum - even_sum
def consecutive_seq(start,end,max,grids):
middle = math.ceil((start end)/2)
sequence = []
for row in range(end-start):
sequence.append(grids[start row])
seq_ins = Sequence(sequence)
if (end-start) <= 3 and (end-start) > 1:
return seq_ins.grids
upper_seq = consecutive_seq(start,middle,seq_ins.diff,seq_ins.grids)
lower_seq = consecutive_seq(middle 1,end,seq_ins.diff,seq_ins.grids)
greater_seq = upper_seq
if upper_seq.diff < lower_seq.diff:
greater_seq = lower_seq
if greater_seq.diff < max:
return seq_ins.grids
# Sample Input
grid = [[10,23,16,25,12],
[19,11,8,1,4],
[3,6,9,7,20],
[18,24,4,17,5],
[7,3,4,6,1]]
n = len(grid)
max_seq = consecutive_seq(0,n-1,0,grid)
print(max_seq)
我該怎么辦？
uj5u.com熱心網友回復：
首先，您實際上并不需要二維陣列。您可以對所有行求和，并且只將總和存盤在一維陣列中。所以例如
grid = [[10,23,16,25,12],
[19,11,8,1,4],
[3,6,9,7,20],
[18,24,4,17,5],
[7,3,4,6,1]]
變成
sums = [sum(row) for row in grid] # sums = [86, 43, 45, 68, 21]
一旦你有了總和，你必須簡單地反轉奇數索引的符號
[86, 43, 45, 68, 21] becomes => [86, -43, 45, -68, 21]
獲得這種格式的資料后，您可以使用演算法來查找時間復雜度為O(n)的連續子陣列中的最大和。您可能需要對其進行一些小調整以包含至少 2 個數字。
此外，如果您只關心差異，您將不得不再次運行演算法，但這次將偶數索引乘以-1.
我真的不認為你可以在O(log n)時間內解決這個問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/448948.html
上一篇：如何遞回讀取物件的屬性
下一篇：XML遞回節點添加