DFS solution and Binary Search without extra space, beats 100%


  • 0
    public class Solution {
        public boolean canCross(int[] stones) {
            int len=stones.length;
            if(stones[len-1]>(len+1)*len/2+1) return false;
            if(stones[1]!=stones[0]+1) return false;
    
            return dfs(stones,1,1);
        }
        
        public boolean dfs(int[] stones, int prevSteps, int pos)
        {
            if(pos>=stones.length-1) return pos==stones.length-1;
            boolean isCross=false;
             int nextPos=0;
              if(!isCross)
              {
                  nextPos=Arrays.binarySearch(stones,pos,stones.length,prevSteps+stones[pos]+1);
                  if(nextPos>=0)
                  isCross=dp(stones,prevSteps+1,nextPos);
              }
              if(!isCross&&prevSteps>0)
             {
                  nextPos=Arrays.binarySearch(stones,pos,stones.length,prevSteps+stones[pos]);
                  if(nextPos>=0)
                  isCross=dp(stones,prevSteps,nextPos);
             }
             if(!isCross&&prevSteps>1)
             {
               nextPos=Arrays.binarySearch(stones,pos,stones.length,prevSteps-1+stones[pos]);
               if(nextPos>=0)
               isCross=dp(stones,prevSteps-1,nextPos);
             }
              return isCross;
        }
    }
    

    This is a Deep First Search version. Two parameters need pass to next element are the previous jump steps and current position. Binary search is used to quickly find the next position with k-1, k, k+1 steps.
    The tricky part is this line

      if(stones[len-1]>(len-1)*len/2) return false;
    

    Check the availability before doing the Dynamic programming.

    At the beginning, I got TLE in the following test case.

    [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30... 999999]

    I am trying to figure out the largest gap between the first element and the last element which can quickly get the result without doing further calculations.

    So lets assume each gap between two stones is increasing by k+1, which can promise the largest gap within the least length.
    1, 2, 4, 7,11,16 ...

    sum up the gaps
    1+ 2+3+4+5...n-1;= n*(n-1)/2;

    Stones[len-1] - stones[0]<= len*(len-1)/2
    if we can not promise this condition, we can directly return false;


Log in to reply
 

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