首页 > 代码库 > frog-jump

frog-jump

https://leetcode.com/problems/frog-jump/// 受以下网页启发,用递归可行// https://discuss.leetcode.com/topic/59337/easy-version-javapublic class Solution {    Map mp;    private int[] stones;    public boolean canCross(int[] s) {        stones = s;                if (stones[1] != 1) {            return false;        }        if (stones.length < 3) {            return true;        }        mp = new HashMap();        Set st = new HashSet();        st.add(1);        mp.put(1, st);        for (int i=2; i<stones.length; i++) {            Set newst = new HashSet();            boolean isNewst = false;                        for (int j=1; j<i; j++) {                Object obj = mp.get(j);                if (obj == null) {                    continue;                }                Set tmpst = (Set) obj;                int dist = stones[i] - stones[j];                                for (int k=-1; k<=1; k++) {                    if (tmpst.contains(dist+k)) {                        newst.add(dist);                        isNewst = true;                    }                }            }                        if (isNewst) {                mp.put(i, newst);            }        }                if (mp.get(stones.length-1) != null) {            return true;        }        else {            return false;        }    }    }/*// 以下解法复杂性太高public class Solution {    private int[] stones;    public boolean canCross(int[] s) {        stones = s;                if (stones[1] != 1) {            return false;        }        if (stones.length < 3) {            return true;        }        return impl(1, 1);    }        boolean impl(int pos, int step) {        if (pos == stones.length - 1) {            return true;        }        for (int i=pos+1; i<stones.length; i++) {            int dist = stones[i] - stones[pos];            if (dist >= step - 1 && dist <= step + 1) {                if (impl(i, dist)) {                    return true;                }            }        }        return false;    }}*/

 

frog-jump