每日力扣：403. 青蛙过河

本文主要是介绍每日力扣：403. 青蛙过河，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

package com.sample.suncht.algo;import java.util.*;/*** 403. 青蛙过河* <p>* 一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。* <p>* 给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。* <p>* 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。* <p>* 请注意：* <p>* 石子的数量 ≥ 2 且 < 1100；* 每一个石子的位置序号都是一个非负整数，且其 < 231；* 第一个石子的位置永远是0。* 示例 1:* <p>* [0,1,3,5,6,8,12,17]* <p>* 总共有8个石子。* 第一个石子处于序号为0的单元格的位置, 第二个石子处于序号为1的单元格的位置,* 第三个石子在序号为3的单元格的位置， 以此定义整个数组...* 最后一个石子处于序号为17的单元格的位置。* <p>* 返回 true。即青蛙可以成功过河，按照如下方案跳跃：* 跳1个单位到第2块石子, 然后跳2个单位到第3块石子, 接着* 跳2个单位到第4块石子, 然后跳3个单位到第6块石子,* 跳4个单位到第7块石子, 最后，跳5个单位到第8个石子（即最后一块石子）。* 示例 2:* <p>* [0,1,2,3,4,8,9,11]* <p>* 返回 false。青蛙没有办法过河。* 这是因为第5和第6个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。* * * 执行用时 : 63 ms, 在Frog Jump的Java提交中击败了58.82% 的用户*/
public class CanCross403 {public boolean canCross(Integer[] stones) {if (stones == null || stones.length < 2) {return true;}if (stones.length == 2) {return stones[1] == 1;}int[] res = new int[1]; //判断是否达到了最后一个节点，如果达到了，说明青蛙可以过河Map<Integer, Boolean> map = new LinkedHashMap<Integer, Boolean>();allowJump(stones, 0, 0, map, res);return res[0] == 1;}private void allowJump(Integer[] stones, int pos, int jump, Map<Integer, Boolean> map, int[] res) {if (res[0] != 1 && pos >= stones.length - 1) {res[0] = 1;return;}//一开始使用"pos:jump:i"字符串作为缓存，但是其实只用“pos:jump”就可以了// 最后为了提高速度，改成整型位运算Integer mark = pos ^ (jump << 11);if (map.containsKey(mark)) {return;}for (int i = pos + 1; i < stones.length; i++) {int dist = stones[i] - stones[pos];//如果dist小于jump-1，需要继续执行if (dist < jump - 1) {continue;}if (dist <= jump + 1) {map.put(mark, true);if (res[0] != 1) { //如果青蛙已过河，则不需要再进行计算了allowJump(stones, i, dist, map, res);}} else {//如果dist大于jump+1，那么后面都一定是大于jump+1，则直接退出，不需要计算map.put(mark, false);return;}}}public static void main(String[] args) {List<AlgoHelper.InputParams<Integer[], Boolean>> datas = new ArrayList<>();datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 3, 5, 6, 8, 12, 17}, true));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 3, 5, 6, 8, 12}, true));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 2, 3, 4, 8, 9, 11}, false));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 4}, false));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 3, 4, 10}, false));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 2}, false));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1}, true));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 2}, true));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, true));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 2, 3, 4, 5, 6, 12}, false));datas.add(new AlgoHelper.InputParams<>(new Integer[]{0, 1, 3, 6, 10, 15, 16, 21}, true));AlgoHelper.assertResult(datas, new CanCross403()::canCross);}}

结果：