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

पायथन में सभी 1 को एक साथ ग्रुप करने के लिए न्यूनतम स्वैप्स


मान लीजिए हमारे पास एक बाइनरी ऐरे data है, हमें ऐरे में कहीं भी सभी 1 को एक साथ ग्रुप करने के लिए आवश्यक न्यूनतम स्वैप्स की संख्या ढूंढनी है। इसलिए यदि ऐरे [1,0,1,0,1,0,0,1,1,0,1] जैसा है, तो आउटपुट 3 होगा, जैसे संभावित समाधान [0,0,0,0,0,1,1,1,1,1,1]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • one := 0 सेट करें, n:= data ऐरे की लंबाई
  • आकार n का एक ऐरे summ बनाएं, और इसे 0 से भरें, summ[0] := data[0] सेट करें
  • one := one + data[0]
  • i को 1 से n - 1 तक रेंज में
    • summ[i] := summ[i - 1] + data[i]
    • one := one + data[i]
  • ans := one
  • left := 0, right := one - 1
  • जब तक right < n
    • यदि left 0 है, तो temp := summ[right], अन्यथा temp := summ[right] - summ[left - 1]
    • ans := ans और one - temp का न्यूनतम
    • right और left को 1 से बढ़ाएं
  • ans लौटाएं

उदाहरण (पायथन)

बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -

class Solution(object):
    def minSwaps(self, data):
        one = 0
        n = len(data)
        summ=[0 for i in range(n)]
        summ[0] = data[0]
        one += data[0]
        for i in range(1,n):
            summ[i] += summ[i-1]+data[i]
            one += data[i]
        ans = one
        left = 0
        right = one-1
        while right < n:
            if left == 0:
                temp = summ[right]
            else:
                temp = summ[right] - summ[left-1]
            ans = min(ans,one-temp)
            right+=1
            left+=1
        return ans

ob = Solution()
print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))

इनपुट

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

आउटपुट

3

  1. Python में सभी बिंदुओं को जोड़ने की न्यूनतम लागत खोजने का प्रोग्राम Python में सभी बिंदुओं को जोड़ने की न्यूनतम लागत खोजने का प्रोग्राम

    मान लीजिए हमारे पास points नामक एक ऐरे है जिसमें कुछ पॉइंट्स (x, y) के रूप में हैं। अब दो पॉइंट्स (xi, yi) और (xj, yj) को जोड़ने की लागत उनके बीच की मैनहट्टन दूरी है, सूत्र है |xi - xj| + |yi - yj|। हमें सभी पॉइंट्स को जोड़ने की न्यूनतम लागत ढूंढनी है। उदाहरण के लिए, यदि इनपुट है points = [(0,0),(

  1. Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें? Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें?

    डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में जिन वर्टेक्सेज़ का इन-डिग्री 0 है, उनसे सभी नोड्स पहुंचे जा सकते हैं। एल्गोरिदम सभी नोड्स का सेट बनाएं (0 से n-1)। सभी एजेज़ के डेस्टिनेशन नोड्स (v) का सेट बनाएं। सोर्स नोड्स = सभी नोड्स - डेस्टिनेशन नोड्स (यानी इन-डिग्री 0 वाले)। यही मिनिमम वर्टेक्स सेट है। उद

  1. Python से बाइनरी ग्रिड में मेजर डायगोनल के ऊपर ज़ीरोज़ के लिए मिनिमम स्वैप्स कैसे ढूंढें? Python से बाइनरी ग्रिड में मेजर डायगोनल के ऊपर ज़ीरोज़ के लिए मिनिमम स्वैप्स कैसे ढूंढें?

    n×n बाइनरी मैट्रिक्स में एडजेसेंट रो स्वैप्स से मेजर डायगोनल के ऊपर सभी एलिमेंट्स 0 करने के लिए मिनिमम स्वैप्स ढूंढें। एल्गोरिदम प्रत्येक रो के लिए राइटमोस्ट 1 की पोजीशन ढूंढें → m[i] = n - j - 1 (डायगोनल से दूरी)। ग्रीडी: i=0 से n-1, ऐसी रो ढूंढें जिसका = n-i-1 हो (यानी डायगोनल के ऊपर 1 न हो)। उसे