查找要替换为 1 的 0 索引,以获取二进制数组中最长的连续 1 序列 - Python 中的 Set-2
假设我们有一个二进制数组。我们必须找到可以用 1 替换的 0 的位置,以获得最大数量的连续 1 序列。
因此,如果输入为 [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1],则输出将为 10,因此数组将为 [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]。
为了解决这个问题,我们将遵循以下步骤 −
i := 0,
n := A 的大小
count_left := 0, count_right := 0
max_i := -1, last_i := -1
count_max := 0
当 i < n 时,执行
如果 A[i] 与 1 相同,则
count_right := count_right + 1
否则,
如果 last_i 与 -1 不同,则
如果 count_right + count_left + 1 > count_max,则
count_max := count_left + count_right + 1
max_i := last_i
last_i := i
count_left := count_right
count_right := 0
i := i + 1
如果 last_i 不等于 -1,则
如果 count_left + count_right + 1 > count_max,然后
count_max := count_left + count_right + 1
max_i := last_i
返回 max_i
示例
让我们看看下面的实现以便更好地理解 −
def find_max_one_index(A): i = 0 n = len(A) count_left = 0 count_right = 0 max_i = -1 last_i = -1 count_max = 0 while i < n: if A[i] == 1: count_right += 1 else: if last_i != -1: if count_right + count_left + 1 > count_max: count_max = count_left + count_right + 1 max_i = last_i last_i = i count_left = count_right count_right = 0 i += 1 if last_i != -1: if count_left + count_right + 1 > count_max: count_max = count_left + count_right + 1 max_i = last_i return max_i A = [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1] print(find_max_one_index(A))
输入
[1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]
输出
10
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

