|
50 | 50 | */ |
51 | 51 | publicclass_403 { |
52 | 52 |
|
53 | | -/**Reference: https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations/2 |
54 | | - * and https://leetcode.com/articles/frog-jump/#approach-5-using-dynamic-programmingaccepted*/ |
55 | | -publicbooleancanCross(int[]stones) { |
56 | | -if (stones.length ==0) { |
57 | | -returntrue; |
58 | | - } |
59 | | -Map<Integer,Set<Integer>>map =newHashMap<>(stones.length); |
60 | | -map.put(0,newHashSet<>()); |
61 | | -map.get(0).add(1); |
62 | | -for (inti =1;i <stones.length;i++) { |
63 | | -map.put(stones[i],newHashSet<>()); |
64 | | - } |
| 53 | +publicstaticclassSolution1 { |
| 54 | +/** |
| 55 | + * Reference: https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations/2 |
| 56 | + * and https://leetcode.com/articles/frog-jump/#approach-5-using-dynamic-programmingaccepted |
| 57 | + */ |
| 58 | +publicbooleancanCross(int[]stones) { |
| 59 | +if (stones.length ==0) { |
| 60 | +returntrue; |
| 61 | + } |
| 62 | +Map<Integer,Set<Integer>>map =newHashMap<>(stones.length); |
| 63 | +map.put(0,newHashSet<>()); |
| 64 | +map.get(0).add(1); |
| 65 | +for (inti =1;i <stones.length;i++) { |
| 66 | +map.put(stones[i],newHashSet<>()); |
| 67 | + } |
65 | 68 |
|
66 | | -for (inti =0;i <stones.length;i++) { |
67 | | -intstone =stones[i]; |
68 | | -for (intstep :map.get(stone)) { |
69 | | -intreach =step +stone; |
70 | | -if (reach ==stones[stones.length -1]) { |
71 | | -returntrue; |
72 | | - } |
73 | | -Set<Integer>set =map.get(reach); |
74 | | -if (set !=null) { |
75 | | -set.add(step); |
76 | | -if (step -1 >0) { |
77 | | -set.add(step -1); |
| 69 | +for (inti =0;i <stones.length;i++) { |
| 70 | +intstone =stones[i]; |
| 71 | +for (intstep :map.get(stone)) { |
| 72 | +intreach =step +stone; |
| 73 | +if (reach ==stones[stones.length -1]) { |
| 74 | +returntrue; |
| 75 | + } |
| 76 | +Set<Integer>set =map.get(reach); |
| 77 | +if (set !=null) { |
| 78 | +set.add(step); |
| 79 | +if (step -1 >0) { |
| 80 | +set.add(step -1); |
| 81 | + } |
| 82 | +set.add(step +1); |
78 | 83 | } |
79 | | -set.add(step +1); |
80 | 84 | } |
81 | 85 | } |
| 86 | +returnfalse; |
82 | 87 | } |
83 | | -returnfalse; |
84 | 88 | } |
85 | | - |
86 | 89 | } |