本文共 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/