Chương trình đếm danh sách con có độ dài k tối thiểu có thể được lật để biến tất cả các mục của danh sách thành 0 bằng Python

Giả sử chúng ta có một danh sách các số được gọi là num lưu trữ các số 0 và 1. Chúng tôi có một giá trị khác k.

Bây giờ hãy xem xét có một phép toán trong đó chúng ta lật một danh sách con có độ dài k sao cho tất cả các số 1 sẽ là số 0 và tất cả các số 0 sẽ là số 1. Chúng ta phải tìm số lượng thao tác tối thiểu cần thiết để thay đổi số thành tất cả các số từ 1 đến 0. Nếu chúng ta không thể thay đổi nó, hãy trả về -1.

Vì vậy, nếu đầu vào giống như nums =[1,1,1,0,0,1,1,1], k =3, thì đầu ra sẽ là 2, vì chúng ta có thể lật ba số đầu tiên thành số 0 và sau đó lật ba số cuối cùng thành số không.

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

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

• res:=0, đã lật:=0

• to_conv:=danh sách kích thước n và điền bằng 0

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • đã lật:=đã lật XOR to_conv [i]

  • cur:=nums [i]

  • cur:=cur XOR bị lật

  • nếu cur bằng 1 thì

    • đã lật:=đã lật XOR 1

    • res:=res + 1

    • nếu i + k - 1> =n, thì

      • trả về -1

    • nếu tôi + k

      • to_conv [i + k]:=1

• trả lại res

Ví dụ

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

class Solution:
   def solve(self, nums, k):
      n = len(nums)
      res = 0
      flipped = 0
      to_conv = [0] * n
      for i in range(n):
         flipped ^= to_conv[i]
         cur = nums[i]
         cur ^= flipped
         if cur == 1:
            flipped ^= 1
            res += 1
            if i + k - 1 >= n:
               return -1
            if i + k < n:
               to_conv[i + k] = 1
      return res
ob = Solution()
nums = [1,1,1,0,0,1,1,1]
k = 3
print(ob.solve(nums, k))

Đầu vào

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

Đầu ra

2