मान लीजिए कि हमारे पास nums नामक संख्याओं की एक सूची है जो 0s और 1s संग्रहीत करती है। हमारे पास एक और मूल्य है k.
अब विचार करें कि एक ऑपरेशन है जहां हम लंबाई k की एक सबलिस्ट को फ्लिप करते हैं जैसे कि सभी 1s 0s होंगे और सभी 0s 1s होंगे। हमें संख्याओं को सभी 1s से 0s में बदलने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात करनी है। अगर हम इसे बदल नहीं सकते तो -1 लौटा दें।
इसलिए, यदि इनपुट nums =[1,1,1,0,0,1,1,1], k =3 जैसा है, तो आउटपुट 2 होगा, क्योंकि हम पहले तीन नंबरों को शून्य पर फ़्लिप कर सकते हैं और फिर अंतिम तीन संख्याओं को शून्य पर फ़्लिप करें।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=अंकों का आकार
-
रेस:=0, फ़्लिप किया गया:=0
-
to_conv :=आकार n की सूची और 0 से भरें
-
मेरे लिए 0 से n की सीमा में, करें
-
फ़्लिप किया गया :=फ़्लिप किया गया XOR to_conv[i]
-
वक्र:=अंक [i]
-
वक्र:=वक्र XOR फ़्लिप किया गया
-
अगर cur 1 के समान है, तो
-
फ़्लिप किया गया :=फ़्लिप किया गया XOR 1
-
रेस :=रेस + 1
-
अगर मैं + के -1>=n, तो
-
वापसी -1
-
-
अगर मैं + के <एन, तो
-
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
आउटपुट
2