मान लीजिए हमारे पास दो सूचियाँ हैं जिन्हें 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
- यदि level >= target, तो:
- 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