পাইথনে বিভিন্ন সমতা সহ একটি মান পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম জাম্পগুলি খুঁজে বের করার প্রোগ্রাম

ধরুন, আমাদের সংখ্যার একটি তালিকা দেওয়া হয়েছে যাকে বলা হয় সংখ্যা। এখানে আমরা সূচী i + সংখ্যা[i] বা i − সংখ্যা [i] থেকে সূচীতে যেতে পারি যদি তালিকায় মান থাকে। তাই ইনপুটের ক্রম অপরিবর্তিত রেখে ভিন্ন সমতা সহ অন্য মান পৌঁছানোর জন্য আমাদের কমপক্ষে কতগুলি জাম্প প্রয়োজন তা খুঁজে বের করতে হবে। যদি আমরা ভিন্ন সমতা সহ অন্য সংখ্যায় পৌঁছাতে না পারি, তাহলে সেটি −1 সেট করা হয়।

সুতরাং, ইনপুট যদি সংখ্যার মত হয় =[7, 3, 4, 5, 6, 9, 6, 7], তাহলে আউটপুট হবে [−1, 1, 2, −1, −1, −1, 1 , −1]।

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

• একটি ফাংশন bfs() সংজ্ঞায়িত করুন। এর জন্য i

  লাগবে

  • q :=একটি জোড়া সহ একটি নতুন ডবল শেষ সারি (i, 0)

  • দেখা হয়েছে :=একটি নতুন সেট

  • q খালি না থাকার সময়, করুন

    • (j, d) :=q এর সবচেয়ে বাম উপাদান এবং q থেকে বাম আইটেমটি মুছে দিন

    • দেখায় j যোগ করুন

    • যদি (nums[i] + nums[j]) mod 2 non−zero হয়, তাহলে

      • d

        ফেরত দিন

    • প্রতিটি k এর জন্য [j + nums[j], j − nums[j]], do

      • যদি 0 <=k <সংখ্যার আকার এবং k দেখা না হয়, তাহলে

        • q

          এর ডান প্রান্তে (k, d + 1) সন্নিবেশ করুন

  • 10^10

    ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• উত্তর :=একটি নতুন তালিকা

• আমি 0 থেকে সংখ্যার আকারের মধ্যে, কর

  • দেখা হয়েছে :=একটি নতুন সেট

  • x :=bfs(i)

  • x <10^10 হলে উত্তরে x যোগ করুন অন্যথায় −1

    যোগ করুন

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

from collections import deque
class Solution:
   def solve(self, nums):
      def bfs(i):
         q = deque([(i, 0)])
         seen = set()
         while q:
            j, d = q.popleft()
            seen.add(j)
            if (nums[i] + nums[j]) % 2:
               return d
            for k in [j + nums[j], j − nums[j]]:
               if 0 <= k < len(nums) and k not in seen:
                  q.append((k, d + 1))
         return 10 ** 10
      ans = []
      for i in range(len(nums)):
         seen = set()
         x = bfs(i)
         ans.append(x if x < 10 ** 10 else −1)
      return ans
ob = Solution()
print(ob.solve([7, 3, 4, 5, 6, 9, 6, 7]))

ইনপুট

numbers = [7, 3, 4, 5, 6, 9, 6, 7]

আউটপুট

[−1, 1, 2, −1, −1, −1, 1, −1]