โปรแกรมนับรายการย่อยความยาว k ขั้นต่ำที่สามารถพลิกเพื่อให้รายการทั้งหมดของรายการเป็น 0 ใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums ที่เก็บ 0s และ 1s เรามีค่า k อีกค่าหนึ่ง

พิจารณาว่ามีการดำเนินการที่เราพลิกรายการย่อยที่มีความยาว k โดยที่ 1 ทั้งหมดจะเป็น 0 และ 0 ทั้งหมดจะเป็น 1 เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นในการเปลี่ยน nums เป็น 1s เป็น 0 ทั้งหมด หากเปลี่ยนไม่ได้ให้คืน -1

ดังนั้น หากอินพุตเป็น nums =[1,1,1,0,0,1,1,1] k =3 ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถพลิกตัวเลขสามตัวแรกเป็นศูนย์แล้ว พลิกตัวเลขสามตัวสุดท้ายเป็นศูนย์

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

n :=ขนาดของ nums
res :=0, พลิก :=0
to_conv :=รายการขนาด n และเติม 0
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
- พลิก :=พลิก XOR to_conv[i]
- cur :=nums[i]
- cur :=cur XOR พลิกแล้ว
- ถ้า cur เหมือนกับ 1 แล้ว
  - พลิก :=พลิก XOR 1
  - res :=res + 1
  - ถ้า i + k - 1>=n แล้ว
    - กลับ -1
  - ถ้า i + k
    - to_conv[i + k] :=1
ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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