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

Python में चलकर k बार कवर किए गए ब्लॉक्स की गिनती करने का प्रोग्राम

मान लीजिए हमारे पास दो सूचियाँ हैं जिन्हें walks और target कहा जाता है। शुरुआत में हम एक आयामी रेखा में स्थिति 0 पर हैं। अब |walks[i]| चले गए कदमों की संख्या दर्शाता है। और जब walk[i] धनात्मक होता है तो दाईं ओर चलना दर्शाता है, और ऋणात्मक बाईं ओर। जब हम चलते हैं, तो हम एक ब्लॉक आगे बढ़ते हैं, यानी अगला या पिछला पूर्णांक स्थान। हमें उन ब्लॉकों की संख्या ज्ञात करनी है जिन पर कम से कम target संख्या में बार चला गया है।

इसलिए, यदि इनपुट है walks = [3, -7, 2] target = 2, तो आउटपुट 5 होगा, निम्न आकृति से हम देख सकते हैं [0, 1], [1, 2], [2, 3], [-4, -3], [-3, -2] k = 2 बार कवर किए गए हैं।

हल करने का दृष्टिकोण

  • pos := 0
  • jumps := एक हैश मैप, जहां डिफ़ॉल्ट मान 0 होता है जब कुंजी मौजूद नहीं होती
  • walks में प्रत्येक dist के लिए, करें:
    • jumps[pos] := jumps[pos] + 1 यदि dist > 0 अन्यथा -1
    • jumps[pos + dist] := jumps[pos + dist] - 1 यदि dist > 0 अन्यथा -1
    • pos := pos + dist
  • lastpos := 0
  • level := 0
  • total := 0
  • jumps के क्रमबद्ध कुंजी-मान जोड़े में प्रत्येक स्थिति pos और मान val के लिए, करें:
    • यदि level >= target, तो:
      • total := total + pos - lastpos
    • level := level + val
    • lastpos := pos
  • total लौटाएं

उदाहरण

from collections import defaultdict

def solve(walks, target):
    pos = 0
    jumps = defaultdict(int)
    for dist in walks:
        jumps[pos] += 1 if dist > 0 else -1
        jumps[pos + dist] -= 1 if dist > 0 else -1
        pos += dist
    lastpos = level = total = 0
    for pos, val in sorted(jumps.items()):
        if level >= target:
            total += pos - lastpos
        level += val
        lastpos = pos
    return total

walks = [3, -7, 2]
target = 2
print(solve(walks, target))

इनपुट

[3, -7, 2], 2

आउटपुट

5
  1. Python में कितने क्यूब कटे हैं, यह खोजने का प्रोग्राम Python में कितने क्यूब कटे हैं, यह खोजने का प्रोग्राम

    मान लीजिए, a, b, और c आयामों के कई क्यूब्स हैं, और उनका उपयोग करके axbxc आयाम का एक नया बॉक्स बनाया जाता है। a, b, और c pairwise को-प्राइम हैं; gcd(a, b) = gcd(b,c) = gcd(c, a) = 1। हमें एक सिंगल स्लाइस के साथ बॉक्स को दो टुकड़ों में काटना है जैसा कि चित्र में दिखाया गया है। हमें यह पता करना है कि य

  1. Python Program कैसे चलाएं? Python Program कैसे चलाएं?

    Code लिखने के बाद, हमें code को execute करके output प्राप्त करने के लिए run करने की आवश्यकता होती है। Program चलाने पर, हम जांच सकते हैं कि लिखा गया code सही है और desired output produce करता है। Python program चलाना काफी आसान काम है। IDLE पर चलाएं IDLE पर python program चलाने के लिए, दिए गए steps क

  1. पायथन में ट्री को दो ट्री में विभाजित करने के तरीकों की गिनती का प्रोग्राम पायथन में ट्री को दो ट्री में विभाजित करने के तरीकों की गिनती का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें 0, 1 और 2 मान हैं। रूट में कम से कम एक 0 नोड और एक 1 नोड है। अब मान लीजिए एक ऑपरेशन है जहां हम ट्री में एक किनारा हटाते हैं और ट्री दो अलग-अलग ट्री बन जाता है। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम एक किनारा हटा सकते हैं जैसे कि दोनों ट्री में से को