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

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है और हम वर्तमान में nums[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 हैं।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (BFS + मान से इंडेक्स मैपिंग):

pos := डिफॉल्टडिक्ट(सूची) - प्रत्येक मान के इंडेक्स स्टोर करें
प्रत्येक इंडेक्स i और मान n के लिए nums में: pos[n].append(i)
n := len(nums)
visited := [False]*n, visited[0] = True
q := deque([(0,0)]) (इंडेक्स, दूरी)
जब तक q खाली नहीं:
- (u,d) := q.popleft()
- यदि u == n-1: d लौटाएं
- प्रत्येक v के लिए pos[nums[u]] + [u-1, u+1] में:
  - यदि 0 <= v < n और not visited[v]:
    - visited[v] = True
    - q.append((v, d+1))
- del pos[nums[u]] (दोबारा प्रोसेस न हो)

उदाहरण कोड

from collections import defaultdict, deque

class Solution:
    def solve(self, nums):
        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]]
        return -1

ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))

इनपुट

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