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

पायथन में ठीक k अलग शब्दों वाली सबलिस्ट की संख्या खोजने का प्रोग्राम


मान लीजिए हमारे पास शब्दों की एक लिस्ट है और एक मान k है। हमें दी गई शब्दों की लिस्ट में उन सबलिस्ट की संख्या ढूंढनी है जिनमें ठीक k अलग शब्द हों।

उदाहरण के लिए, यदि इनपुट words = ["Kolkata", "Delhi", "Delhi", "Kolkata"], k = 2 है, तो आउटपुट 5 होगा, क्योंकि निम्नलिखित सबलिस्ट में 2 यूनिक शब्द हैं: ["Kolkata", "Delhi"], ["Delhi", "Kolkata"], ["Kolkata", "Delhi", "Delhi"], ["Delhi", "Delhi", "Kolkata"], ["Kolkata", "Delhi", "Delhi", "Kolkata"], लेकिन ["Delhi", "Delhi"] नहीं क्योंकि इसमें केवल एक यूनिक शब्द है।

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

इस समस्या को हल करने के लिए हम स्लाइडिंग विंडो तकनीक का उपयोग करेंगे:

  • work(words, k) फंक्शन परिभाषित करें:
    • n := words का आकार
    • यदि k == 0 है, तो 0 लौटाएं
    • cnt := एक नया मैप, ans := 0, l := 0
    • r को 0 से n-1 तक लूप चलाएं:
      • word := words[r]
      • यदि word, cnt में नहीं है, तो cnt[word] := 0
      • cnt[word] := cnt[word] + 1
      • जब तक cnt का आकार > k है:
        • cnt[words[l]] := cnt[words[l]] - 1
        • यदि cnt[words[l]] == 0 है, तो words[l] को cnt से हटाएं
        • l := l + 1
      • ans := ans + r - l + 1
    • ans लौटाएं
  • मुख्य मेथड से work(words, k) - work(words, k - 1) लौटाएं

पायथन कार्यान्वयन

class Solution:
    def solve(self, words, k):
        return self.work(words, k) - self.work(words, k - 1)
    def work(self, words, k):
        n = len(words)
        if k == 0:
            return 0
        cnt = dict()
        ans = 0
        l = 0
        for r in range(n):
            word = words[r]
            if word not in cnt:
                cnt[word] = 0
            cnt[word] += 1
            while len(cnt) > k:
                cnt[words[l]] -= 1
                if cnt[words[l]] == 0:
                    del cnt[words[l]]
                l += 1
            ans += r - l + 1
        return ans

ob = Solution()
words = ["Kolkata", "Delhi", "Delhi", "Kolkata"]
k = 2
print(ob.solve(words, k))

इनपुट

["Kolkata", "Delhi", "Delhi", "Kolkata"], 2

आउटपुट

5
  1. - पायथन में एक अद्वितीय वर्ण वाले सभी सबस्ट्रिंग्स की कुल संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास लोअरकेस अक्षरों की एक स्ट्रिंग s है, हमें उन सबस्ट्रिंग्स की कुल संख्या ढूंढनी है जिनमें एक अद्वितीय वर्ण है। उदाहरण के लिए, यदि इनपुट xxyy है, तो आउटपुट 6 होगा क्योंकि सबस्ट्रिंग्स हैं [x, x, xx, y, y, yy]। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: total := 0 previous

  1. - पायथन प्रोग्राम में अभाज्य संख्या खोजने के विभिन्न तरीके

    इस ट्यूटोरियल में, हम यह जांचने के विभिन्न तरीकों का पता लगाने जा रहे हैं कि दी गई संख्या अभाज्य है या नहीं। आइए बिना किसी देरी के शुरू करें। विधि-1 यह अभाज्य संख्या खोजने की एक सामान्य विधि है। यदि संख्या एक से कम या बराबर है, तो False लौटाएं। यदि संख्या किसी संख्या से विभाज्य है, तो फंक्शन False

  1. - Python प्रोग्राम में अभाज्य संख्या खोजने के विभिन्न तरीकों का विश्लेषण

    इस ट्यूटोरियल में, हम अभाज्य संख्या खोजने के विभिन्न तरीकों और प्रत्येक विधि के लिए आवश्यक समय को देखेंगे। हम निष्पादन समय की गणना के लिए time मॉड्यूल का उपयोग करेंगे।विधि-1यह अभाज्य संख्या खोजने की एक सामान्य विधि है।यदि संख्या एक से कम या बराबर है, तो False लौटाएं।यदि संख्या किसी संख्या से विभाज्य