环形数组循环
给定一个含有正整数和负整数的环形数组nums
,如果某个索引中的数k
为正数,则向前移动 k
个索引,相反如果是负数-k
,则向后移动k
个索引。因为数组是环形的,所以可以假设最后一个元素的下一个元素是第一个元素,而第一个元素的前一个元素是最后一个元素,确定nums
中是否存在循环或周期。循环必须在相同的索引处开始和结束并且循环长度>1
。此外,一个循环中的所有运动都必须沿着同一方向进行,换句话说,一个循环中不能同时包括向前的运动和向后的运动。
示例
输入:[2,-1,1,2,2]
输出:true
解释:存在循环,按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。
输入:[-1,2]
输出:false
解释:按索引 1 -> 1 -> 1 ... 的运动无法构成循环,因为循环的长度为 1 。根据定义,循环的长度必须大于 1 。
输入:[-2,1,-1,-2,-2]
输出:false
解释:按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环,因为按索引 1 -> 2 的运动是向前的运动,而按索引 2 -> 1 的运动是向后的运动。一个循环中的所有运动都必须沿着同一方向进行。
题解
/**
* @param {number[]} nums
* @return {boolean}
*/
var circularArrayLoop = function(nums) {
var n = nums.length;
var getNext = x => {
var nextIndex = (x+nums[x])%n;
return nextIndex >= 0 ? nextIndex : nextIndex+n;
};
for(let i=0;i<n;++i) {
if(nums[i] === 0) continue;
let slow = i;
let fast = getNext(i);
while(nums[slow]*nums[fast] > 0 && nums[fast] * nums[getNext(fast)] > 0){
if(slow === fast){
if(slow === getNext(slow)) break;
else return true;
}
slow = getNext(slow);
fast = getNext(getNext(fast));
}
let tmp = i;
let val = nums[tmp];
while(val * nums[tmp] > 0){
let k = getNext(tmp);
nums[tmp] = 0;
tmp = k;
}
}
return false;
};
思路
首先需要解释一下题意,以示例1
中[2,-1,1,2,2]
为例,最开始是索引0
值为2
,那么索引向前走2
步到索引2
值为1
,继续向前走1
步到达索引3
值为2
,再向前走2
步循环索引回到0
,所以这完成了一次循环,这里的起始点并不一定是索引0
,起始点可以为任意索引位置,其次就是限制条件循环的长度必须大于1
以及一个循环中的所有运动都必须沿着同一方向进行。
本题使用快慢指针来做,快指针每次走两步,慢指针每次走一步,如果能够达成循环那么快慢指针必定会相遇,当然在此处一步与两步指的是移动一个nums[i]
的步长,不是移动index+1
,首先定义一个n
为数组长度以及getNext
方法作为取得该点的下一步的索引值,之后遍历数组,根据定义,数组中不能存在0
元素,所以以0
为标记值进行剪枝,以慢指针指向i
,快指针指向下一步的索引,while
循环中第一个判断是保证慢指针与快指针指向的数组值符号相同,第二个判断是保证快指针指向的数组值与下一个快指针指向的数组值同号,保证一个循环中的所有运动都必须沿着同一方向进行,之后如果快慢指针相遇,则判断是否循环的长度为1
,若循环的长度为1
则不符合条件,便继续查找,否则就可以说明该数组中存在循环,之后便是slow
指针走一步,fast
指针走两部,最后需要剪枝,因为已经遍历过的元素不可能出现在循环当中,所以将以i
为索引开始的每一步都置0
,用以实现剪枝。
每日一题
https://github.com/WindrunnerMax/EveryDay
参考
https://leetcode-cn.com/problems/circular-array-loop