Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में k बिट्स फ्लिप करके सबसे लंबे 1s के सेट की लंबाई खोजने का प्रोग्राम


मान लीजिए हमारे पास एक बाइनरी सूची है, जहां केवल 1s और 0s उपलब्ध हैं और हमारे पास एक संख्या k भी है। हम अधिकतम k 0s को 1s में बदल सकते हैं, हमें सभी 1s वाले सबसे लंबे सबलिस्ट की लंबाई ढूंढनी है।

उदाहरण के लिए, यदि इनपुट nums = [0, 1, 1, 0, 0, 1, 1] और k = 2 है, तो आउटपुट 6 होगा, क्योंकि हम बीच के दो 0s को 1s में बदल सकते हैं और सूची [0, 1, 1, 1, 1, 1, 1] बन जाती है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (स्लाइडिंग विंडो):

  • zeros := 0, ans := 0, j := 0
  • प्रत्येक इंडेक्स i और मान n के लिए nums में:
    • zeros += (1 if n == 0 else 0)
    • जब तक zeros > k:
      • zeros -= (1 if nums[j] == 0 else 0)
      • j += 1
    • यदि i-j+1 > ans:
      • ans := i-j+1
  • ans लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, nums, k):
        zeros = 0
        ans = 0
        j = 0
        for i, n in enumerate(nums):
            zeros += n == 0
            while zeros > k:
                zeros -= nums[j] == 0
                j += 1
            if i - j + 1 > ans:
                ans = i - j + 1
        return ans

ob = Solution()
nums = [0, 1, 1, 0, 0, 1, 1]
k = 2
print(ob.solve(nums, k))

इनपुट

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

आउटपुट

6

  1. - पायथन में मैट्रिक्स में सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, जहां 0 खाली सेल दर्शाता है और 1 दीवार दर्शाता है। हम पहली पंक्ति के किसी भी खाली सेल से शुरू कर सकते हैं और अंतिम पंक्ति के किसी भी खाली सेल पर समाप्त करना चाहते हैं। हम बाएं, दाएं या नीचे जा सकते हैं, हमें सबसे लंबा ऐसा पथ ढूंढना है जहां हम प्रत्येक सेल क

  1. - पायथन में लगातार बढ़ते हुए सबसे लंबे सबस्ट्रिंग की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है। इसमें अंग्रेजी अक्षर और साथ ही ? सिंबल होता है। प्रत्येक ? के लिए हमें या तो उसे हटाना होगा या किसी भी लोअरकेस अक्षर से बदलना होगा। हमें उस सबसे लंबे लगातार बढ़ते हुए सबस्ट्रिंग की लंबाई ढूंढनी है जो अक्षर a से शुरू होता है। उदाहरण के लिए, यदि इनपुट है s

  1. पायथन में n-ary ट्री में सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम पायथन में n-ary ट्री में सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक एज लिस्ट है जहां प्रत्येक आइटम (u, v) रखता है जो दर्शाता है कि u, v का पैरेंट है। हमें ट्री में सबसे लंबे पथ की लंबाई ढूंढनी है। पथ की लंबाई 1 + उस पथ में नोड्स की संख्या है। उदाहरण के लिए, यदि इनपुट है: तो आउटपुट 5 होगा, क्योंकि पथ [1, 4, 5, 7] है, कुल 4 नोड्स हैं, इसलिए पथ