新知一下
海量新知
6 0 8 4 0 8 4

​LeetCode刷题实战457:环形数组是否存在循环

程序IT圈 | 程序员编程技术 2021/12/03 14:28

今天和大家聊的问题叫做 环形数组是否存在循环 ,我们先来看题面:

https://leetcode-cn.com/problems/circular-array-loop/

新知达人, ​LeetCode刷题实战457:环形数组是否存在循环

新知达人, ​LeetCode刷题实战457:环形数组是否存在循环

示例

示例 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]] 应当不是全正就是全负。

解题

https://blog.csdn.net/xiji333/article/details/119496750

思路:用一个数组标记i ii是否走过,然后对每个位置做一次循环模拟即可。但是这样复杂度是O ( n 2 ) O(n^2)O(n 2  )的,事实上,对于上次遍历过的点,如果没有找到答案,那么这些点都是无解的,我们可以把它们剔除掉,这样可以把时间复杂度降低到O ( n ) O(n)O(n)。 不过为了区分上次遍历和当前遍历,需要新开一个数组。

class Solution {

public:

    bool circularArrayLoop(vector<int>& nums) {

        int n=nums.size();

        vector<bool> step(n);

        bool ans=0;

        for(int i=0;i<n&&!ans;i++)

        {

            if(step[i])

                continue;

            vector<bool> tmp(n);

            tmp[i]=1;

            int cur=i;

            bool neg=nums[cur]<0;

            while(1)

            {

                int nxt=((cur+nums[cur])%n+n)%n;

                if(nxt==cur||step[nxt])

                    break;

                if(tmp[nxt])

                    return 1;

                if(neg&&nums[nxt]>0)

                    break;

                if(!neg&&nums[nxt]<0)

                    break;

                tmp[nxt]=tmp[cur];

                cur=nxt;

            }

            for(int j=i+1;j<n;j++)

                step[j]=step[j]||tmp[j];

        }

        return ans;

    }

};


更多“算法”相关内容

更多“算法”相关内容

新知精选

更多新知精选