পাইথনে সার্কুলার লিস্টে ফরওয়ার্ড সাইকেল আছে কিনা চেক করা

একটি সার্কুলার লিস্টে প্রতিটি উপাদান নির্দেশ করে কত স্টেপ ফরওয়ার্ড (পজিটিভ) বা ব্যাকওয়ার্ড (নেগেটিভ) যেতে হবে। লেন্থ ১ এর বড় একটি সাইকেল আছে কিনা যেটি শুধু ফরওয়ার্ড বা শুধু ব্যাকওয়ার্ড যেতে হয়।

ইনপুট উদাহরণ

nums = [-1, 2, -1, 1, 2]

আউটপুট: True (সাইকেল: 1 → 3 → 4 → 1, সব ফরওয়ার্ড)

অ্যালগরিদম

1. প্রতিটি ইনডেক্স থেকে ভিজিট ট্র্যাক করে সাইকেল ডিটেক্ট করুন।
2. seen অ্যারে দিয়ে করেন্ট ইটারেশনের ভিজিট মার্ক করুন।
3. যদি একই ইটারেশনে دوبارہ একই নোডে ফিরে আসা হয় এবং দিক পরিবর্তন হয়নি, তবে সাইকেল আছে।

পাইথন কোড

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

# টেস্ট
print(solve([-1, 2, -1, 1, 2]))  # True

ব্যাখ্যা

ফ্লয়েডের সাইকেল ডিটেকশনের ভেরিয়েন্ট। seen অ্যারে দিয়ে প্রতিটি ট্রাভার্সাল আলাদা ট্র্যাক করা হয়।