搜索矩陣

Question

零的最大路徑鑑於1的和0，如一個10×N矩陣：

1 1 1 1 1 1 1 1 
1 1 0 1 1 0 0 1 
0 0 0 1 1 0 0 1 
0 0 0 1 1 0 0 0 
1 0 0 0 0 1 0 0 
1 0 1 1 1 1 1 1 
1 0 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 

筆記：

• 的零在柱總是在兩次連續的1s之間。例如，柱如1 1 1 0 1 0 1 1 1 1這樣不允許

• 必須有至少一個在每個柱一個零的間隙，即，柱如：1 1 1 1 1 1 1 1 1 1不允許

我想從左到右找到最長的零連續條紋。在這種情況下，這將是4，它對應於從頂部第五行第二列開始的路徑，

第二長的是3，並且有3個例子。

我對此有點難住，特別是對於非常大的N（〜10M）。我在尋找正確的方法/數據結構的使用建議或類似的問題以及在那裏使用的算法。建模的問題的另一種潛在的方法是使用兩個列表來表示問題：

L1 = [2, 2, 1, 4, 4, 1, 1, 3] 
L2 = [6, 3, 5, 5, 5, 5, 5, 5] 

，但仍然不太清楚如何拿出有效的解決方案

Answer 1

該解決方案使用itertools.groupby()，sum()和max()功能：

import itertools 

m = [ 
    [1, 1, 1, 1, 1, 1, 1, 1], 
    [1, 1, 0, 1, 1, 0, 0, 1], 
    [0, 0, 0, 1, 1, 0, 0, 1], 
    [0, 0, 0, 1, 1, 0, 0, 0], 
    [1, 0, 0, 0, 0, 1, 0, 0], 
    [1, 0, 1, 1, 1, 1, 1, 1], 
    [1, 0, 1, 1, 1, 1, 1, 1], 
    [1, 1, 1, 1, 1, 1, 1, 1], 
    [1, 1, 1, 1, 1, 1, 1, 1], 
    [1, 1, 1, 1, 1, 1, 1, 1] 
] 

max_zero_len = max(sum(1 for z in g if z == 0) 
        for l in m for k,g in itertools.groupby(l)) 

print(max_zero_len) 

輸出：

4 

---

for l in m for k,g in itertools.groupby(l) - 將爲每個嵌套列表的每個連續序列1和0生成一個單獨的組。 （像[1,1], [0], [1,1], [0,0] ...）

sum(1 for z in g if z == 0) - 僅考慮0的序列，並使用sum功能

max(...)計數其長度 - 得到之間爲零（0）最大長度序列