C++ 269 ms: How can I improve the code?


  • 0
    E
        bool canCross(vector<int>& stones) {
            if(stones.size()<2) return false;
            if(stones[0]!=0||stones[1]!=1) return false;
            if(stones.size()==2) return true;
            
            vector<set<int>> stepSize(stones.size());
            stepSize[1].insert(1);
            for(int i=1;i<stones.size();i++) {
                bool hasNextStep = false;
                int minStep = *stepSize[i].begin();
                int maxStep = *stepSize[i].rbegin();
                for(int j=i+1;j<stones.size();j++) {
                    int deltaStep = stones[j]-stones[i];
                    if(deltaStep<minStep-1) continue;
                    if(deltaStep>maxStep+1) break;
                    if( stepSize[i].find(deltaStep)==stepSize[i].end() && \
                        stepSize[i].find(deltaStep+1)==stepSize[i].end() && \
                        stepSize[i].find(deltaStep-1)==stepSize[i].end()) continue;
                    if(j==stones.size()-1) return true;
                    hasNextStep = true;
                    stepSize[j].insert(deltaStep);
                }
                
                if(!hasNextStep) return false;
            }
            
            return false;
        }
    

    BTW, if the test cases have been updated, will the previous submission solutions be tested and updated their runtime?


Log in to reply
 

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