Vòng lặp mảng tròn trong C++

Cho mảng tròn nums chứa số nguyên dương và âm. Nếu nums[i] = k > 0 thì tiến tới trước k bước; nếu k < 0 thì lùi |k| bước. Mảng tròn: phần tử sau cuối là đầu, phần tử trước đầu là cuối. Kiểm tra xem có chu trình (cycle) hay không. Chu trình phải bắt đầu và kết thúc tại cùng chỉ số, độ dài > 1. Ví dụ: [2,-1,1,2,2] → true (chu trình 0→2→3→0 độ dài 3).

Giải thuật

• n := nums.size(); nếu n < 2 trả về false.
• Với mọi i: nums[i] %= n.
• Với mỗi i từ 0 đến n-1:
  • Nếu nums[i] == 0 bỏ qua.
  • slow = i, fast = i.
  • Khi nums[slow]*nums[fast] > 0 và nums[next(fast)]*nums[slow] > 0:
    • slow = next(slow), fast = next(next(fast)).
    • Nếu slow == fast:
      • Nếu slow == next(slow) thoát vòng lặp.
      • Trả về true.
  • x = nums[i], slow = i.
  • Khi nums[slow]*x > 0:
    • temp = next(slow), nums[slow] = 0, slow = temp.
• Trả về false.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int next(vector<int>& nums, int i) {
        int n = nums.size();
        return (n + nums[i] + i) % n;
    }
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;
        for (int i = 0; i < n; i++) nums[i] %= n;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            while (nums[slow] * nums[fast] > 0 && nums[next(nums, fast)] * nums[slow] > 0) {
                slow = next(nums, slow);
                fast = next(nums, next(nums, fast));
                if (slow == fast) {
                    if (slow == next(nums, slow)) break;
                    return true;
                }
            }
            int x = nums[i];
            slow = i;
            while (nums[slow] * x > 0) {
                int temp = next(nums, slow);
                nums[slow] = 0;
                slow = temp;
            }
        }
        return false;
    }
};

Đầu vào

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

Đầu ra

1