C++ by Traversal


  • 0
    G
    class Solution {
    public:
        bool circularArrayLoop(vector<int>& nums) {
            int n = nums.size();
            vector<int> des(n,0);
            for(int i=0;i<n;i++){
                des[i]=((n+nums[i]%n+i%n)%n)%n;    //calculate the destination
            }
            set<int> fd;
            for(int i=0;i<n;i++){
                if(fd.count(i)!=0)continue;
                int k=i;
                vector<int> tmp;
                while(true){
                    fd.insert(k);
                    if(find(tmp.begin(),tmp.end(),k)!=tmp.end()){
                        if(tmp.back()!=k){
                            auto it = find(tmp.begin(),tmp.end(),k);
                            int tt = nums[(*it)]/abs(nums[(*it)]);
                            for(;it!=tmp.end();it++){
                                if(nums[(*it)]/abs(nums[(*it)])!=tt)break;   //calculate the direction,if not forward or backward, then break;
                            }
                            if(it==tmp.end())return true;
                            else break;
                        }else break;
                    }
                    tmp.push_back(k);
                    
                    k=des[k];
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.