পাইথনে শেষ সূচকে পৌঁছানোর জন্য ন্যূনতম ধাপের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা আছে এবং আমরা বর্তমানে সংখ্যা[0] এ স্থাপন করেছি। প্রতিটি ধাপে, আমরা হয় বর্তমান সূচক i থেকে i + 1 বা i - 1 বা j যেখানে nums[i] ==nums[j] তে লাফ দিতে পারি। চূড়ান্ত সূচকে পৌঁছানোর জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[4, 8, 8, 5, 4, 6, 5], তাহলে আউটপুট হবে 3, কারণ আমরা সূচক 0 থেকে সূচক 4-এ যেতে পারি কারণ উভয়ের মানই 4। এবং তারপরে আমরা সূচক 3-এ ফিরে যাই। অবশেষে, আমরা সূচক 3 থেকে 6-এ যেতে পারি কারণ তাদের উভয়ের মানই 5।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

pos :=একটি খালি মানচিত্র
প্রতিটি সূচক i, এবং সংখ্যা n এর জন্য, করুন
- pos[n] এর শেষে i ঢোকান
n :=সংখ্যার আকার
visited :=n আকারের একটি তালিকা তৈরি করুন এবং এটি False দিয়ে পূরণ করুন
ভিজিট করেছেন[0] :=সত্য
যখন q খালি নয়, কর
- (u, d) :=q এর বাম উপাদান, এবং বাম উপাদান মুছুন
- যদি u n - 1 এর মত হয়, তাহলে
  - রিটার্ন d
- তালিকার প্রতিটি v-এর জন্য pos[nums[u]] এবং [u - 1, u + 1], do
  - যদি 0 <=v
  - পরিদর্শন করেছেন[v] :=সত্য
  - q এর শেষে জোড়া (v, d + 1) সন্নিবেশ করুন
pos[সংখ্যা[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]