पायथन में न्यूनतम k-लंबाई सबलिस्ट की संख्या गिनने का प्रोग्राम जिसे फ्लिप करके सूची के सभी आइटम 0 बनाए जा सकते हैं

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जिसमें 0 और 1 संग्रहीत हैं। हमारे पास एक मान k भी है। एक ऑपरेशन पर विचार करें जहां हम लंबाई k के एक सबलिस्ट को फ्लिप करते हैं ताकि सभी 1, 0 बन जाएं और सभी 0, 1 बन जाएं। हमें nums को सभी 0 में बदलने के लिए आवश्यक न्यूनतम ऑपरेशनों की संख्या ज्ञात करनी है। यदि हम इसे बदल नहीं सकते तो -1 वापस करें।

उदाहरण के लिए, nums = [1,1,1,0,0,1,1,1], k = 3 के लिए आउटपुट 2 होगा (पहले तीन और अंतिम तीन को फ्लिप करें)।

एल्गोरिदम (ग्रीडी विंडो फ्लिप)

• n := len(nums), res := 0, flipped := 0
• to_conv := आकार n की सूची 0 से भरी हुई
• i = 0 से n-1 तक:
  • flipped ^= to_conv[i]
  • cur = nums[i] ^ flipped
  • यदि cur == 1:
    • flipped ^= 1, res++
    • यदि i + k - 1 >= n, तो -1 वापस करें
    • यदि i + k < n, तो to_conv[i+k] = 1
• res वापस करें

उदाहरण

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] ^ 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

आउटपुट

2