在矩阵中搜索零的最大路径 [英] Searching for maximum path of zeroes in matrix

问题描述

给出一个10 x N的1和0的矩阵，例如:

Given an 10 x N matrix of 1's and 0s, such as:

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

注释:

• 列中的零始终位于两次连续的1之间.例如，不允许使用诸如1 1 1 0 1 0 1 1 1 1之类的列

• the zeroes in a column are always between two runs of consecutive 1s. for example, a column such as 1 1 1 0 1 0 1 1 1 1 is not permitted

每个列中必须至少有一个零间隔，即一个列，例如:不允许1 1 1 1 1 1 1 1 1 1

there must be at least a gap of one zero in each column, ie a column such as: 1 1 1 1 1 1 1 1 1 1 is not allowed

我想找到从左到右最长的连续零.在这种情况下，该值为4，对应于从顶部第5行的第二列开始的路径，

I want to find the longest consecutive streak of zeroes from left to right. In this case, that would be 4, which corresponds to the path starting in the second column of the 5th row from the top,

第二长的是3，有3个例子.

The second longest is 3 and there are 3 examples of that.

我对此有些困惑，特别是对于非常大的N(〜10M).我正在寻找使用正确的方法/数据结构或类似问题的建议，以及在那里使用的算法.对问题建模的另一种潜在方法是使用两个列表来表示问题:

I'm a bit stumped on this, especially for very large N (~10M). I am looking for suggestions for the right approach/data structure to use or a similar problem and the algorithm used there. Another potential way to model the problem is to represent the problem using two lists:

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

但仍然不确定如何提出有效的解决方案

but still not quite sure how to come up with an efficient solution

推荐答案

使用输出:

4

---

for l in m for k,g in itertools.groupby(l)-将为每个嵌套列表的1和0值的每个连续序列生成一个单独的组. (如[1,1], [0], [1,1], [0,0] ...)

---

for l in m for k,g in itertools.groupby(l) - will generate a separate group for each consecutive sequences of 1 and 0 values for each nested list. (like [1,1], [0], [1,1], [0,0] ...)

sum(1 for z in g if z == 0)-仅考虑0的序列，并使用sum函数计算其长度

sum(1 for z in g if z == 0) - considers only 0's sequences and counts its length using sum function

max(...)-获取零(0)个序列中的最大长度

max(...) - gets the maximum length among zero(0) sequences

这篇关于在矩阵中搜索零的最大路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！