leetcode:457. 环形数组是否存在循环

2023-12-17 22:44

本文主要是介绍leetcode:457. 环形数组是否存在循环,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  1. 环形数组是否存在循环
    存在一个不含 0 的 环形 数组 nums ,每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数:

如果 nums[i] 是正数,向前(下标递增方向)移动 |nums[i]| 步
如果 nums[i] 是负数,向后(下标递减方向)移动 |nums[i]| 步
因为数组是 环形 的,所以可以假设从最后一个元素向前移动一步会到达第一个元素,而第一个元素向后移动一步会到达最后一个元素。

数组中的 循环 由长度为 k 的下标序列 seq 标识:

遵循上述移动规则将导致一组重复下标序列 seq[0] -> seq[1] -> … -> seq[k - 1] -> seq[0] -> …
所有 nums[seq[j]] 应当不是 全正 就是 全负
k > 1
如果 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]] 应当不是全正就是全负。

提示:

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
nums[i] != 0

进阶:你能设计一个时间复杂度为 O(n) 且额外空间复杂度为 O(1) 的算法吗?

方法:快慢指针
思路:我们可以将环形数组理解为图中的 n 个点,nums[i]表示 i号点向 (i+nums[i])mod n 号点连有一条单向边。

注意到这张图中的每个点有且仅有一条出边,这样我们从某一个点出发,沿着单向边不断移动,最终必然会进入一个环中。而依据题目要求,我们要检查图中是否存在一个所有单向边方向一致的环。

具体地,我们检查每一个节点,令快慢指针从当前点出发,快指针每次移动两步,慢指针每次移动一步,期间每移动一次,我们都需要检查当前单向边的方向是否与初始方向是否一致,如果不一致,我们即可停止遍历,因为当前路径必然不满足条件。为了降低时间复杂度,我们可以标记每一个点是否访问过,过程中如果我们的下一个节点为已经访问过的节点,则可以停止遍历。

class Solution {
public:bool circularArrayLoop(vector<int>& nums) {int n = nums.size();// 将lambda表达式作为函数对象auto next_index = [&](int cur) {//保证返回值在 [0, n)return ((cur + nums[cur]) % n + n) % n;};// 依次检查各个节点for (int i = 0; i < n; i++) {if (0 == nums[i]) {continue;}int slow = i;int fast = next_index(i);// 判断非零且方向相同while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next_index(fast)] > 0) {if (slow == fast) {if (slow != next_index(slow)) {// 从这个节点开始,存在环,返回return true;} else {// 当nums[i]为n的整倍数时,i的后继节点即为i本身,此时循环长度k=1,不符合题目要求break;}}slow = next_index(slow);fast = next_index(next_index(fast));}// 从这个节点开始,不存在环,将遍历过的节点置为0,为下一次遍历做准备int add = i;while (nums[add] * nums[next_index(add)] > 0) {nums[add] = 0;add = next_index(add);}}return false;}
};

这篇关于leetcode:457. 环形数组是否存在循环的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/506135

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Java中的for循环高级用法

《Java中的for循环高级用法》本文系统解析Java中传统、增强型for循环、StreamAPI及并行流的实现原理与性能差异,并通过大量代码示例展示实际开发中的最佳实践,感兴趣的朋友一起看看吧... 目录前言一、基础篇:传统for循环1.1 标准语法结构1.2 典型应用场景二、进阶篇:增强型for循环2.

Python循环结构全面解析

《Python循环结构全面解析》循环中的代码会执行特定的次数,或者是执行到特定条件成立时结束循环,或者是针对某一集合中的所有项目都执行一次,这篇文章给大家介绍Python循环结构解析,感兴趣的朋友跟随... 目录for-in循环while循环循环控制语句break语句continue语句else子句嵌套的循

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序