本文共 1349 字,大约阅读时间需要 4 分钟。
用一个HashMap<Integer, HashSet<Integer>>记录位置index处前一步step是k时都失败的k的cache
public class Solution { public boolean canCross(int[] stones) { if (stones == null || stones[1] - stones[0] != 1) { return false; } HashMap> map = new HashMap(); return canCross(stones, 1, 1, map); } private boolean canCross(int[] stones, int index, int step, HashMap > map) { if (index == stones.length - 1) { return true; } else if (step <= 0 || map.getOrDefault(index, new HashSet()).contains(step)) { return false; } boolean ret = false; for (int i = index + 1; i < stones.length; i++) { if (stones[index] + step == stones[i]) { ret |= canCross(stones, i, step, map); } else if (stones[index] + step + 1 == stones[i]) { ret |= canCross(stones, i, step + 1, map); } else if (stones[index] + step - 1 == stones[i]) { ret |= canCross(stones, i, step - 1, map); } else if (stones[index] + step + 1 < stones[i]) { break; } if (ret) { return true; } } HashSet set = map.getOrDefault(index, new HashSet()); set.add(step); map.put(index, set); return false; }}
转载地址:http://hxhld.baihongyu.com/