存在一个不含 0 的 环形 数组 nums ,每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数: 如果 nums[i] 是正数,向前(下标递增方向)移动 |nums[i]| 步 如果 nums[i] 是负数,向

动态 未结 0 112
小小草
小小草 LV1 2023年9月23日 23:40 发表
可以使用快慢指针的方法来解决这个问题。具体步骤如下: 1. 定义两个指针 slow 和 fast,初始值都为 0。 2. 在循环中,每次将 slow 移动一步,即 slow = (slow + nums[slow]) % n,其中 n 是数组的长度,注意要取模。 3. 在循环中,每次将 fast 移动两步,即 fast = (fast + nums[fast]) % n,其中 n 是数组的长度,注意要取模。 4. 如果存在循环,那么 slow 和 fast 最终会相遇,此时返回 true。 5. 如果不存在循环,那么 fast 会先到达数组的边界,此时返回 false。 代码实现如下: ``` bool circularArrayLoop(vector& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { if (nums[i] == 0) continue; int slow = i, fast = getNext(nums, i); while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[getNext(nums, fast)] > 0) { if (slow == fast) { if (slow != getNext(nums, slow)) return true; else break; } slow = getNext(nums, slow); fast = getNext(nums, getNext(nums, fast)); } int j = i; while (nums[j] * nums[getNext(nums, j)] > 0) { int k = j; j = getNext(nums, j); nums[k] = 0; } } return false; } int getNext(vector& nums, int i) { int n = nums.size(); return ((i + nums[i]) % n + n) % n; } ``` 其中,getNext 函数用于计算下一个位置的下标,注意要处理环形数组的情况。在循环中,如果 slow 和 fast 相遇,那么需要再次判断是否存在循环,因为可能存在长度为 1 的循环
收藏(0)  分享
相关标签: 智能问答
问题没解决?让AI助手帮你作答 AI助手
0个回复
  • 消灭零回复