My code:
public class Solution {
public boolean canCross(int[] stones) {
if (stones == null || stones.length == 0) {
return false;
}
Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
map.put(0, new HashSet<Integer>());
map.get(0).add(1);
for (int i = 1; i < stones.length; i++) {
map.put(stones[i], new HashSet<Integer>());
}
for (int i = 0; i < stones.length; i++) {
int base = stones[i];
for (Integer step : map.get(stones[i])) {
int reach = base + step;
if (reach == stones[stones.length - 1]) {
return true;
}
if (map.containsKey(reach)) {
Set<Integer> set = map.get(reach);
set.add(step);
set.add(step + 1);
if (step - 1 > 0) {
set.add(step - 1);
}
}
}
}
return false;
}
}
reference:
https://discuss.leetcode.com/topic/59903/very-easy-to-understand-java-solution-with-explanations/2
没想出来。
感觉已经没有思考新题的能力了。。。
悲哀
Anyway, Good luck, Richardo! -- 10/21/2016
