Участник:Бушенкова Ксения/LeetCode Frog Jump — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
https://leetcode.com/problems/frog-jump/
 
https://leetcode.com/problems/frog-jump/
  
<code-js>
 
 
class Solution {
 
class Solution {
 
     public boolean canCross(int[] stones) {
 
     public boolean canCross(int[] stones) {
Строка 39: Строка 38:
 
     }
 
     }
 
}
 
}
</code-js>
 
  
 
[[Категория:На проверку]]
 
[[Категория:На проверку]]

Версия 15:20, 24 мая 2020

Бушенкова Ксения 17:14, 24 мая 2020 (MSK) https://leetcode.com/problems/frog-jump/

class Solution {

   public boolean canCross(int[] stones) {
       if (stones.length == 0) {
           return true;
       }
        //Initialize the map
       HashMap<Integer, HashSet<Integer>> map = new HashMap<>(stones.length);
       map.put(0, new HashSet<>());
       map.get(0).add(1);
       for (int i = 1; i < stones.length; i++) {
           map.put(stones[i], new HashSet<>() );
       }
       for (int i = 0; i < stones.length - 1; i++) {
           int stone = stones[i];
           // calculate the steps of each stone
           for (int step : map.get(stone)) {
               int reach = step + stone;
               if (reach == stones[stones.length - 1]) {
                   return true;
               }
               HashSet<Integer> set = map.get(reach);
               if (set != null) {
                   set.add(step);
                   if (step - 1 > 0) {
                       set.add(step - 1);
                   }
                   set.add(step + 1);
               }
           }
       }
       return false;
   }

}