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

पायथन में दिशा स्ट्रिंग को संतुलित करने का प्रोग्राम ताकि प्रत्येक दिशा चौथाई बार आए

मान लीजिए हमारे पास चार दिशाओं "N", "S", "W" और "E" के साथ एक स्ट्रिंग s है जो क्रमशः उत्तर, दक्षिण, पश्चिम और पूर्व के लिए है। हमें सबसे छोटे सबस्ट्रिंग का आकार ढूंढना है जिसे हम अपडेट कर सकते हैं ताकि चार दिशाओं में से प्रत्येक n/4 बार आए, जहां n स्ट्रिंग s का आकार है।

इसलिए, यदि इनपुट है s = "NNSWWESN", तो आउटपुट होगा 1, यहां n 8 है, इसलिए 8/4 2 है, इसलिए यदि हम अंतिम N को E में बदलते हैं, तो सभी दिशाएं दो बार होंगी।

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

  • n := s का आकार
  • यदि n 0 है, तो:
    • 0 लौटाएं
  • quarter := floor(n / 4)
  • count := s में मौजूद प्रत्येक तत्व की आवृत्तियों वाली एक सूची
  • target := एक नया मैप
  • count में प्रत्येक जोड़े (dir, cnt) के लिए, करें:
    • यदि cnt > quarter, तो:
      • target[dir] := quarter - cnt
  • यदि target खाली है, तो:
    • 0 लौटाएं
  • left := 0
  • min_len := inf
  • s में प्रत्येक इंडेक्स right और दिशा dir के लिए, करें:
    • यदि dir target में है, तो:
      • target[dir] := target[dir] + 1
    • जब target के सभी मानों की सूची का न्यूनतम >= 0, करें:
      • min_len := min(min_len, right - left + 1)
      • यदि s[left] target में है, तो:
        • target[s[left]] := target[s[left]] - 1
        • left := left + 1
  • min_len लौटाएं

उदाहरण

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

from collections import Counter
def solve(s):
    n = len(s)
    if not n:
        return 0
    quarter = n // 4
    count = Counter(s)
    target = dict()
    for (dir, cnt) in count.items():
        if cnt > quarter:
            target[dir] = quarter - cnt
    if not target:
        return 0
    left, min_len = 0, float("inf")
    for right, dir in enumerate(s):
        if dir in target:
            target[dir] += 1
        while min(target.values()) >= 0:
            min_len = min(min_len, right - left + 1)
            if s[left] in target:
                target[s[left]] -= 1
                left += 1
    return min_len
s = "NNSWWESN"
print(solve(s))

इनपुट

"NNSWWESN"

आउटपुट

1
  1. पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग वॉयल पालिंड्रोम है या नहीं पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग वॉयल पालिंड्रोम है या नहीं

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक स्ट्रिंग दी गई है (जिसमें स्वर और व्यंजन दोनों अक्षर हैं), सभी व्यंजनों को हटाएं, फिर जांचें कि परिणामी स्ट्रिंग पालिंड्रोम है या नहीं। यहां हम पहले स्ट्रिंग में मौजूद सभी व्यंजनों को हटाते हैं। एक लूप से विभाजकों की गणना क

  1. पायथन प्रोग्राम: जांचें कि स्ट्रिंग खाली है या नहीं पायथन प्रोग्राम: जांचें कि स्ट्रिंग खाली है या नहीं

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट एक स्ट्रिंग इनपुट दिए जाने पर, हमें जांचना होगा कि स्ट्रिंग खाली है या नहीं। पायथन स्ट्रिंग्स प्रकृति में इम्यूटेबल होती हैं इसलिए किसी भी ऑपरेशन को करते समय स्ट्रिंग्स को संभालते समय

  1. पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग पैंग्राम है या नहीं पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग पैंग्राम है या नहीं

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट एक स्ट्रिंग इनपुट दिए जाने पर, हमें यह जांचने के लिए एक पायथन प्रोग्राम जनरेट करना होगा कि वह स्ट्रिंग पैंग्राम है या नहीं। एक पैंग्राम एक वाक्य/शब्दों की श्रृंखला है जिसमें अंग्रेजी