Chương trình kiểm tra chu trình tiến (forward cycle) trong danh sách vòng Python

Cho danh sách vòng nums (phần tử đầu và cuối là láng giềng). Từ chỉ số i, di chuyển nums[i] bước: tiến nếu dương, lùi nếu âm. Kiểm tra có chu trình độ dài > 1 chỉ đi tiến HOẶC chỉ đi lùi hay không.

Ví dụ: nums=[-1,2,-1,1,2] → True (chu trình tiến: 1→3→4→1).

Giải thuật (Fast/Slow pointer + đánh dấu vòng lặp)

1. Chuẩn hóa nums[i] = nums[i] % n
2. Duyệt từng vị trí chưa thăm, dùng biến iter đánh dấu vòng lặp hiện tại
3. Theo dõi hướng đi: nếu cả tiến và lùi đều xuất hiện → break
4. Nếu gặp nút đã đánh dấu trong vòng lặp hiện tại → tìm thấy chu trình hợp lệ

Ví dụ triển khai

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 = 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]))

Đầu vào

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

Đầu ra

True