622. Frog Jump

下面的算法是超时的。

return helper(stones,0,0);
 }
 
 public boolean helper(int[] stones, int current, int k){
 
 if(current == stones.length-1){
 return true;
 }
 
 for(int i= k-1; i<=k+1; i++){

int nextStone = stones[current]+i;
 int nextIndex = Arrays.binarySearch(stones, current+1, stones.length, nextStone);
 if( nextIndex > 0 ){
 if(helper(stones, nextIndex, i)){
 return true;
 }
 }
 }
 
 return false;
 
 }

下面这个算法不超时。思路是用一个HashMap里面存着石头和其对应的能走的步伐的一个set。我们初涉第一个石头0的步伐只有一个1。然后初设每个其他石头是一个空的set。然后从第一个石头遍历,看它自己加上自己本来就有的set里的steps能去哪里。如果正好是最后一个石头,bingo!! 否则的话,给next stone里面的set加上当前步伐的-1,+1 和本身,如果小于0不加入。然后就完了,等着循环结束还没有bingo就回返false好了。主要是每个石头处理完了以后就等于给后面的石头铺好了路,很好,很简单的O(n)

HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
 HashSet<Integer> temp = new HashSet<Integer>();
 temp.add(1);
 map.put(stones[0], temp);
 
 for(int i=1; i<stones.length; i++){
 temp = new HashSet<Integer>();
 map.put(stones[i], temp);
 }
 
 for(int i=0; i<stones.length; i++){
 for(int step: map.get(stones[i])){
 int next = step+stones[i];
 if(next == stones[stones.length-1]){
 return true;
 }
 HashSet t = map.get(next);
 if(t!=null){
 if(step-1>0){
 t.add(step-1);
 }
 t.add(step);
 t.add(step+1);
 map.put(next, t);
 }

}
 }
 
 return false;

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.