题目描述
存在一个不含 0 的 环形 数组 nums ,每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数:
因为数组是 环形 的,所以可以假设从最后一个元素向前移动一步会到达第一个元素,而第一个元素向后移动一步会到达最后一个元素。
数组中的 循环 由长度为 k 的下标序列 seq :
如果 nums 中存在循环,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [2,-1,1,2,2] 输出:true 解释:存在循环,按下标 0 -> 2 -> 3 -> 0 。循环长度为 3 。
示例 2:
输入:nums = [-1,2] 输出:false 解释:按下标 1 -> 1 -> 1 ... 的运动无法构成循环,因为循环的长度为 1 。根据定义,循环的长度必须大于 1 。
示例 3:
输入:nums = [-2,1,-1,-2,-2] 输出:false 解释:按下标 1 -> 2 -> 1 -> ... 的运动无法构成循环,因为 nums[1] 是正数,而 nums[2] 是负数。所有 nums[seq[j]] 应当不是全正就是全负。
提示:
进阶:你能设计一个时间复杂度为 O(n) 且额外空间复杂度为 O(1) 的算法吗?
链接:https://leetcode-cn.com/problems/circular-array-loop
这个题目描述的有点难以理解,下面做出解释:
针对示例1,[2,-1,1,2,2]:
所以,构成了一个循环,且满足题目要求的:沿途都是同向(全正或全负),且环数大于1
image-20210807123320639
针对示例2,[-1,2]:
下标1形成自循环,不满足题目要求环数大于1。
image-20210807124002343
针对示例3,[-2,1,-1,-2,-2]
下标1和下标2形成循环,但是不满足题目要求的沿途全正或全负的要求。
image-20210807124119154
以上图片来源:https://leetcode-cn.com/problems/circular-array-loop/solution/hua-tu-li-jie-ti-mu-by-6racious-i3habha-qsqv/
通常来说,遇到这种求环的问题,我们都可以使用快慢指针来解决,当快指针与慢指针相遇了,说明就形成了环,但是,本题需要附带几个额外的条件,即环数大于1,且沿途全是正数或全是负数。
class Solution {
public boolean circularArrayLoop(int[] nums) {
// 2,-1,1,2,2
// 0, 1,2,3,4
// 0,2,3构成循环
// 双指针法:从每一个节点开始出发,看快慢指针是否能相遇,相遇的话就构成了环
for (int i = 0; i < nums.length; i++) {
int slow = i;
int fast = next(nums, i);
// 快慢指针方向是否一致
// 快指针每次走两步,所以,要判断慢指针与快指针的下一次是否方向也一致
while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
if (slow == fast) {
if (slow != next(nums, slow)) {
return true;
} else {
break;
}
}
slow = next(nums, slow);
fast = next(nums, next(nums, fast));
}
}
return false;
}
private int next(int[] nums, int i) {
int n = nums.length;
// 考虑负值的情况,+n是把它转正
// 如果是正值的话,+n就超过n了,所以最后再%n一下
// 这里把正负情况考虑在一起了,当然也可以分开写
// 正值:(i + nums[i]) % n
// 负值:(i + nums[i]) % n + n
return ((i + nums[i]) % n + n) % n;
}
}
能过,运行结果较慢。
image-20210807121958652
上述方式,如果存在环,很快能结束,如果不存在环呢?
比如:[-2,1,-1,-2,-2],从下标0出发,实际上把下标[3,1,2]也遍历过了,且它们是不满足条件的,所以,是不是可以在遍历下标0出发的时候把它们标记一下,下次从下标[3,1,2]出发的时候直接判定它们不合格即可。
image-20210807124119154
可以的,我们只要在每次遍历完,把不合格的沿途节点都标记一下就可以,简单点就是把数组对应下标位置的值改为0,代码如下:
class Solution {
public boolean circularArrayLoop(int[] nums) {
// 2,-1,1,2,2
// 0, 1,2,3,4
// 0,2,3构成循环
// 双指针法:从每一个节点开始出发,看快慢指针是否能相遇,相遇的话就构成了环
for (int i = 0; i < nums.length; i++) {
int slow = i;
int fast = next(nums, i);
// 快慢指针方向是否一致
// 快指针每次走两步,所以,要判断慢指针与快指针的下一次是否方向也一致
while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
if (slow == fast) {
if (slow != next(nums, slow)) {
return true;
} else {
break;
}
}
slow = next(nums, slow);
fast = next(nums, next(nums, fast));
}
// 到这里表示从i出发无法构成环
// 方向相同的才需要标记,不要把反方向的标记了
int x = i;
while (nums[x] * nums[next(nums, x)] > 0) {
int tmp = next(nums, x);
nums[x] = 0;
x = tmp;
}
}
return false;
}
private int next(int[] nums, int i) {
int n = nums.length;
// 考虑负值的情况,+n是把它转正
// 如果是正值的话,+n就超过n了,所以最后再%n一下
// 这里把正负情况考虑在一起了,当然也可以分开写
// 正值:(i + nums[i]) % n
// 负值:(i + nums[i]) % n + n
return ((i + nums[i]) % n + n) % n;
}
}
运行时间立马就上去了。
image-20210807130540399
上面使用双指针来判断有没有环,那么,我们能不能只使用一个指针往前移,发现循环呢?
其实,也是可以的,不过稍微麻烦一些,比如[1,1,2],我们从下标0出发,其实是在下标1和下标2进入循环。
所以,我们不能只打简单的标记,我们这里考虑对于每一个出发的下标打不同的标记,通过题目可值nums[i]<=1000,所以,我们可以选取一个比1000大的数做为下标的基数,在这个基数的基础上加上出发的下标本身作为标记即可。
下面请看代码吧,加了详细的注释:
class Solution {
public boolean circularArrayLoop(int[] nums) {
int BASE = 100000;
for (int i = 0; i < nums.length; i++) {
// 已经标记过,说明从这个数出发不会有环,直接跳过
if (nums[i] >= BASE) {
continue;
}
// 不能简单的标记为0了
// 标记中带上从哪个下标出发的,用于后面判断是不是从这个下标出发形成的环
int tag = BASE + i;
// 方向
int dir = nums[i];
// 当前指针
int curr = i;
// 上一次的值
int last = -1;
// 需要在遍历的过程中就标记,否则像[-1,-2,-3,-4,-5]这个用例就死循环了
while (true) {
// 已经打过标记了,里面可以跳出循环了
if (nums[curr] >= BASE) {
// 判断是不是从下标i出发打的标记
// last % nums.length != 0用于判断是不是自循环
if (nums[curr] == tag && last % nums.length != 0) {
return true;
} else {
break;
}
}
// 未打过标记,且方向相同
if (dir * nums[curr] > 0) {
// 记录上一次的值,用于上面判断是不是自循环
last = nums[curr];
// 下一次的指针
int next = next(nums, curr);
// 更新当前指针的值为标记
nums[curr] = tag;
// 往后移
curr = next;
} else {
// 方向不同,则跳出循环
break;
}
}
}
return false;
}
private int next(int[] nums, int i) {
int n = nums.length;
// 考虑负值的情况,+n是把它转正
// 如果是正值的话,+n就超过n了,所以最后再%n一下
// 这里把正负情况考虑在一起了,当然也可以分开写
// 正值:(i + nums[i]) % n
// 负值:(i + nums[i]) % n + n
return ((i + nums[i]) % n + n) % n;
}
public static void main(String[] args) {
System.out.println(new Solution().circularArrayLoop(new int[] {-1,1,-2}));
System.out.println(new Solution().circularArrayLoop(new int[] {1,1,2}));
System.out.println(new Solution().circularArrayLoop(new int[] {2,-1,1,2,2}));
System.out.println(new Solution().circularArrayLoop(new int[] {-1,2}));
System.out.println(new Solution().circularArrayLoop(new int[] {-2,1,-1,-2,-2}));
System.out.println(new Solution().circularArrayLoop(new int[] {-1,-2,-3,-4,-5}));
}
}
整个逻辑比较复杂,同学们可以到自己的IDEA中把main()方法的测试用例跑一遍,就比较清晰了。
运行结果如下:
image-20210807143841616
方法三参考自:https://leetcode-cn.com/problems/circular-array-loop/solution/gong-shui-san-xie-yi-ti-shuang-jie-mo-ni-ag05/