Tìm Chỉ mục của 0 được thay thế bằng 1 để có được chuỗi 1 liên tục dài nhất trong một mảng nhị phân - Set-2 trong Python

Giả sử chúng ta có một mảng nhị phân. Chúng ta phải tìm vị trí của 0 có thể thay thế bằng 1 để có được số dãy liên tục tối đa là 1s.

Vì vậy, nếu đầu vào là [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1], thì đầu ra sẽ là 10, vì vậy mảng sẽ là [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• i:=0,

• n:=kích thước của A

• count_left:=0, count_right:=0

• max_i:=-1, last_i:=-1

• count_max:=0

• trong khi tôi

  • nếu A [i] giống với 1 thì

    • count_right:=count_right + 1

  • nếu không,

    • nếu last_i không giống -1, thì

      • nếu count_right + count_left + 1> count_max thì

        • count_max:=count_left + count_right + 1

        • max_i:=last_i

    • last_i:=i

    • count_left:=count_right

    • count_right:=0

  • i:=i + 1

• nếu last_i không giống -1, thì

  • nếu count_left + count_right + 1> count_max thì

    • count_max:=count_left + count_right + 1

    • max_i:=last_i

• trả về max_i

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]

Đầu ra

10