मान लीजिए कि हमारे पास दो सूचियाँ हैं जिन्हें वॉक और टारगेट कहा जाता है। शुरुआत में हम एक-आयामी रेखा में स्थिति 0 पर हैं। अब |चलता है[i]| कदमों की संख्या का प्रतिनिधित्व करता है। और जब चलना [i] सकारात्मक होता है तो इंगित करता है कि चला गया दाएं, और बाएं के लिए नकारात्मक। जब हम चलते हैं, तो हम एक ब्लॉक को आगे बढ़ाते हैं, जो कि अगली या पिछली पूर्णांक स्थिति है। हमें उन ब्लॉकों की संख्या ज्ञात करनी है, जिन पर कम से कम लक्ष्य संख्या कितनी बार चली है।
इसलिए, यदि इनपुट वॉक =[3, -7, 2] लक्ष्य =2 की तरह है, तो आउटपुट 5 होगा, निम्नलिखित आकृति से, हम देख सकते हैं [0, 1], [1, 2], [2 , 3], [-4, -3], [-3, -2] k =2 बार ढके हुए हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- स्थिति:=0
- कूदता है:=एक हैश मैप, जहां कुंजी मौजूद न होने पर डिफ़ॉल्ट मान 0 होता है
- प्रत्येक जिले के पैदल चलने के लिए, करें
- कूदता है [स्थिति] :=कूदता है [स्थिति] + 1 अगर जिला> 0 अन्यथा -1
- कूदता है [स्थिति + जिला] :=कूदता है [स्थिति + जिला] - 1 अगर जिला> 0 अन्यथा -1
- स्थिति:=स्थिति + जिला
- अंतिम स्थिति :=0
- स्तर:=0
- कुल :=0
- प्रत्येक स्थिति स्थिति के लिए, और छलांग के क्रमबद्ध कुंजी-मूल्य जोड़े में मूल्य वैल, करते हैं
- यदि स्तर>=लक्ष्य, तो
- कुल :=कुल + स्थिति - अंतिम स्थिति
- स्तर :=स्तर + वैल
- अंतिम स्थिति :=स्थिति
- यदि स्तर>=लक्ष्य, तो
- कुल वापसी
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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