首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。