বৃত্তাকার চক্রাকার তালিকায় কোন ফরোয়ার্ড পাথ আছে কি পাইথনে নেই তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বৃত্তাকার তালিকা আছে যাকে বলা হয় সংখ্যা। সুতরাং প্রথম এবং শেষ উপাদানগুলি হল প্রতিবেশী। তাই যেকোন সূচক থেকে শুরু করে বলি i, আমরা nums[i] ধাপ এগিয়ে নিয়ে যেতে পারি যদি nums[i] একটি ধনাত্মক মান হয়, অন্যথায় পিছনের দিকে যদি এটি একটি ঋণাত্মক মান হয়। আমাদের পরীক্ষা করতে হবে এমন একটি চক্র আছে যার দৈর্ঘ্য একের চেয়ে বেশি যে পথটি কেবল সামনে যায় বা কেবল পিছনে যায়৷

সুতরাং, যদি ইনপুটটি nums =[-1, 2, -1, 1, 2] এর মত হয়, তাহলে আউটপুটটি True হবে, কারণ একটি ফরোয়ার্ড পাথ আছে [1 -> 3 -> 4 -> 1]

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

• n :=সংখ্যার আকার
• যদি n 0 এর মত হয়, তাহলে
  • মিথ্যে ফেরত দিন
• seen :=n আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
• সংখ্যায় প্রতিটি উপাদান x এর জন্য x mod n পেয়ে সংখ্যাগুলি আপডেট করুন
• iter :=0
• আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
  • যদি nums[i] 0 এর মত হয়, তাহলে
    • পরবর্তী পুনরাবৃত্তির জন্য যান
  • iter :=iter + 1
  • pos :=সত্য
  • neg :=সত্য
  • curr :=i
  • নিম্নলিখিতটি বারবার করুন, করুন
    • যদি nums[curr] এবং দেখা [curr] আইটারের মতো হয়, তাহলে
      • সত্য ফেরান
    • যদি দেখা যায় [curr] অ-শূন্য হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
    • যদি nums[curr]> 0 হয়, তারপর
      • neg :=মিথ্যা
    • অন্যথায়,
      • pos :=মিথ্যা
    • যদি neg এবং pos উভয়ই মিথ্যা হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
    • দেখা হয়েছে [curr] :=iter
    • curr :=(curr + nums[curr] + n) মোড n
    • যদি nums[curr] 0 এর মত হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
• মিথ্যে ফেরত দিন

উদাহরণ

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

def solve(nums):
   n = len(nums)
   if n == 0:
      return False
   seen = [0]*n
   nums = [x % n for x in nums]
   iter = 0
   for i in range(n):
      if nums[i] == 0:
         continue
      iter += 1
      pos = True
      neg = True
      curr = i
      while True:
         if nums[curr] and seen[curr] == iter:
            return True
         if seen[curr] :
            break
         if nums[curr] > 0:
            neg = False
         else:
            pos = False
         if not neg and not pos:
            break
         seen[curr] = iter
         curr = (curr + nums[curr] + n) % n
         if nums[curr] == 0:
            break
   return False

nums = [-1, 2, -1, 1, 2]
print(solve(nums))

ইনপুট

[-1, 2, -1, 1, 2]

আউটপুট

True