首页 > > 程序设计 > C/C++ >

Leetcode0457--Circular Array Loop

2018-07-20 05:47:51来源：博客园阅读 ()

【转载请注明】https://www.cnblogs.com/igoslly/p/9339478.html

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int index=0,size = nums.size(),step=0;
        // 处理index
        while(step<size){
            if(nums[index]>0){
                index = (index+nums[index])%size;
            }else if(nums[index]<0){
                index = (index-nums[index])%size;
            }
            // 判断index返回 0 
            if(index==0){
                return true;
            }
            step++;
        }
        return false;
    }
};

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int index=0,size = nums.size(),step=0;
        if(size<=1){
            return false;
        }
        while(step<size){
            // 修改元素值为0，设flag
            if(nums[index]==0){
                return true;
            }
            int temp= nums[index];
            nums[index]=0;
            // 进行index操作
            if(nums[index]>0){
                index = (index+temp)%size;
            }else if(nums[index]<0){
                index = (index-temp)%size;
            }
            step++;
        }
        return false;
    }
};

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int index=0,size = nums.size(),step=0;
        if(size<=1){
            return false;
        }
        while(step<=size){
            int temp= nums[index];
            int preindex=index;
            // 进行index操作
            if(nums[index]>0){
                if(index==(index+temp)%size){
                    return false;
                }
                index = (index+temp)%size;
            }else if(nums[index]<0){
                if(index==(index-temp)%size){
                    return false;
                }
                index = (index-temp)%size;
            }
            // 修改元素值为0，设flag
            if(nums[preindex]==0){
                return true;
            }
            nums[preindex]=0;
            step++;
        }
        return false;
    }
};

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int index=0,size = nums.size(),step=0;
        if(size<=1){
            return false;
        }
        for(int i=0;i<size;i++){
            if(nums[i]==0) continue;
            // two pointers
            int j=i,k = (i+nums[i]+size)%size;
            while(nums[i]*nums[k]>0 && nums[i]*nums[(k+nums[k]+size)%size]>0){
                if(j==k){
                    // check for loop with only one element
                    if(j = (j+nums[j]+size)%size) break;
                    return true;
                }
                j = (j+nums[j]+size)%size;
                k = (k+nums[k]+size)%size;
                k = (k+nums[k]+size)%size;
            }
            // loop not found
            j =i;
            int val = nums[i];
            while(nums[j]*val>0){
                int next = (j+nums[j]+size)%size;
                nums[j]=0;
                j=next;
            }
        }
        return false;
    }
};