पायथन में अंतिम सूचकांक तक पहुंचने के लिए न्यूनतम चरणों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और हमें वर्तमान में अंक [0] पर रखा गया है। प्रत्येक चरण पर, हम या तो वर्तमान इंडेक्स i से i + 1 या i-1 या j पर कूद सकते हैं जहां nums[i] ==nums[j]। हमें अंतिम अनुक्रमणिका तक पहुँचने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट nums =[4, 8, 8, 5, 4, 6, 5] की तरह है, तो आउटपुट 3 होगा, क्योंकि हम इंडेक्स 0 से इंडेक्स 4 पर जा सकते हैं क्योंकि उनके मान दोनों 4 हैं। और फिर हम इंडेक्स 3 पर वापस जाते हैं। अंत में, हम इंडेक्स 3 से 6 तक कूद सकते हैं क्योंकि उनके दोनों मान 5 हैं।

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

• स्थिति:=एक खाली नक्शा
• प्रत्येक अनुक्रमणिका i के लिए, और अंकों में n मान, करें
  • स्थिति के अंत में i डालें[n]
• n :=अंकों का आकार
• देखा गया :=आकार n की एक सूची बनाएं, और इसे गलत से भरें
• विज़िट किया[0] :=सच
• जबकि q खाली नहीं है, करें
  • (u, d) :=q का बायां तत्व, और बायां तत्व हटाएं
  • यदि आप n-1 के समान हैं, तो
    • वापसी d
  • सूचियों में प्रत्येक v के लिए pos[nums[u]] और [u - 1, u + 1], do
    • यदि 0 <=v
    • विज़िट किया[v] :=सच
    • q के अंत में जोड़ी (v, d + 1) डालें
• स्थिति हटाएं[nums[u]]

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

उदाहरण

class Solution:
   def solve(self, nums):
      from collections import defaultdict, deque
      pos = defaultdict(list)
      for i, n in enumerate(nums):
         pos[n].append(i)
      q = deque([(0, 0)])
      n = len(nums)
      visited = [False] * n
      visited[0] = True
      while q:
         u, d = q.popleft()
         if u == n - 1:
            return d
         for v in pos[nums[u]] + [u - 1, u + 1]:
            if 0 <= v < n and not visited[v]:
               visited[v] = True
               q.append((v, d + 1))
         del pos[nums[u]]
ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))

इनपुट

[4, 8, 8, 5, 4, 6, 5]

आउटपुट

3