C++의 원형 배열 루프

<시간/>

양의 정수 값과 음의 정수 값으로 구성된 원형 배열 num이 있다고 가정합니다. 인덱스에 있는 숫자 k가 양수이면 k 단계 앞으로 이동합니다. 그렇지 않고 음수(-k)이면 k 단계 뒤로 이동합니다. 배열은 원형이므로 마지막 요소의 다음 요소가 첫 번째 요소이고 첫 번째 요소의 이전 요소가 마지막 요소라고 가정할 수 있습니다. 숫자에 루프(또는 순환)가 있는지 확인해야 합니다. 사이클은 동일한 인덱스에서 시작하고 끝나야 하고 사이클의 길이> 1입니다. 따라서 입력이 [2,-1,1,2,2]와 같으면 인덱스에서 사이클이 있으므로 출력은 true가 됩니다. 0 -> 2 -> 3 -> 길이 3의 0.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 크기
n <2이면 false를 반환합니다.
0 ~ n - 1 범위의 i에 대해 nums[i] :=nums[i] mod n
0 ~ n – 1 범위의 i에 대해
- nums[i] =0이면 다음 반복으로 이동합니다.
- 느린 =나, 빠른 =나;
- nums[slow] * nums[fast]> 0 및 nums[next of fast] * nums[slow]> 0
  - 느린 =느린 다음
  - fast :=fast 다음의 다음
  - 느린 =빠른 경우
    - 느린 경우 =다음 느린 경우 루프에서 나옵니다.
    - true를 반환
- x :=숫자[i]
- 느린 :=나는
- 동안 숫자[느림] * x> 0
  - temp :=다음으로 느림
  - 느린 다음 :=0
  - 느림 :=온도
거짓 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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;
         int 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;
   }
};
main(){
   vector<int> v = {2,-1,1,2,2};
   Solution ob;
   cout << (ob.circularArrayLoop(v));
}

입력

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