在二进制数组中查找需要替换为 1 的 0 的索引,以获得最长的连续 1 序列 - Python篇(续集)


假设我们有一个二进制数组。我们必须找到可以替换为 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

更新于:2020年8月25日

253 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告