数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的循环数组
假设我们有一个包含正数和负数的循环数组 nums。如果某个索引处的数字 k 为正数，则向前移动 k 步。否则，如果它是负数 (-k)，则向后移动 k 步。由于数组是循环的，我们可以假设最后一个元素的下一个元素是第一个元素，第一个元素的前一个元素是最后一个元素。我们必须检查 nums 中是否存在循环（或周期）。一个循环必须在同一个索引处开始和结束，并且循环的长度 > 1。因此，如果输入类似于 [2,-1,1,2,2]，则输出将为真，因为存在从索引 0 -> 2 -> 3 -> 0 长度为 3 的循环。
为了解决这个问题，我们将遵循以下步骤 -
n := nums 的大小
如果 n < 2，则返回 false
对于范围 0 到 n - 1 中的 i，nums[i] := nums[i] 模 n
对于范围 0 到 n – 1 中的 i
如果 nums[i] = 0，则跳过本次迭代 continue;
slow = i，fast = i;
当 nums[slow] * nums[fast] > 0 且 nums[fast 的下一个] * nums[slow] > 0 时
slow = slow 的下一个
fast := fast 的下一个的下一个
如果 slow = fast，则
如果 slow = slow 的下一个，则退出循环
返回 true
x := nums[i]
slow := i
当 nums[slow] * x > 0 时
temp := slow 的下一个
slow 的下一个 := 0
slow := temp
返回 false
让我们看看以下实现以获得更好的理解 -
示例
#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
更新于: 2020-04-30
3K+ 次浏览
广告