ধরুন আমাদের ধনাত্মক এবং ঋণাত্মক পূর্ণসংখ্যা মানের একটি বৃত্তাকার অ্যারে সংখ্যা রয়েছে। যদি একটি সূচকে একটি সংখ্যা k একটি ধনাত্মক সংখ্যা হয়, তাহলে k ধাপ এগিয়ে যান। অন্যথায়, যদি এটি নেতিবাচক হয় (-k), k ধাপগুলি পিছনে সরান। যেহেতু অ্যারেটি বৃত্তাকার, তাই আমরা ধরে নিতে পারি যে শেষ উপাদানটির পরবর্তী উপাদানটি প্রথম উপাদান এবং প্রথম উপাদানটির পূর্ববর্তী উপাদানটি শেষ উপাদান। সংখ্যায় একটি লুপ (বা একটি চক্র) আছে কিনা তা আমাদের পরীক্ষা করতে হবে। একটি চক্র অবশ্যই একই সূচক এবং চক্রের দৈর্ঘ্য> 1 এ শুরু এবং শেষ হতে হবে। তাই যদি ইনপুটটি [2,-1,1,2,2] এর মত হয়, তাহলে আউটপুটটি সত্য হবে, কারণ সূচক থেকে একটি চক্র রয়েছে 0 -> 2 -> 3 -> 3 দৈর্ঘ্যের 0।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=সংখ্যার আকার
-
যদি n <2, তাহলে মিথ্যা ফেরত দিন
-
0 থেকে n - 1 রেঞ্জের জন্য i, nums[i] :=nums[i] mod n
-
0 থেকে n – 1
রেঞ্জের i জন্য-
যদি nums[i] =0 হয়, তাহলে পরবর্তী পুনরাবৃত্তি চালিয়ে যান;
-
ধীর =i, দ্রুত =i;
-
যখন nums[ধীরে] * nums[দ্রুত]> 0 এবং nums[ফাস্টের পরবর্তী] * nums[ধীর]> 0
-
slow =ধীরের পরের
-
দ্রুত :=পরের রোজার পরের
-
যদি ধীর =দ্রুত, তাহলে
-
স্লো =স্লো এর পরের, তাহলে লুপ থেকে বেরিয়ে আসুন
-
প্রত্যাবর্তন সত্য
-
-
-
x :=সংখ্যা[i]
-
ধীর :=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]
আউটপুট
1
