每日力扣：403. 青蛙过河

悠悠 2022-02-16 08:23 281阅读 0赞

package com.sample.suncht.algo;
 
 import java.util.*;
 
 /**
 * 403. 青蛙过河
 * 
 * 一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。
 * 
 * 给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。
 * 
 * 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
 * 
 * 请注意：
 * 
 * 石子的数量 ≥ 2 且 < 1100；
 * 每一个石子的位置序号都是一个非负整数，且其 < 231；
 * 第一个石子的位置永远是0。
 * 示例 1:
 * 
 * [0,1,3,5,6,8,12,17]
 * 
 * 总共有8个石子。
 * 第一个石子处于序号为0的单元格的位置, 第二个石子处于序号为1的单元格的位置,
 * 第三个石子在序号为3的单元格的位置， 以此定义整个数组...
 * 最后一个石子处于序号为17的单元格的位置。
 * 
 * 返回 true。即青蛙可以成功过河，按照如下方案跳跃：
 * 跳1个单位到第2块石子, 然后跳2个单位到第3块石子, 接着
 * 跳2个单位到第4块石子, 然后跳3个单位到第6块石子,
 * 跳4个单位到第7块石子, 最后，跳5个单位到第8个石子（即最后一块石子）。
 * 示例 2:
 * 
 * [0,1,2,3,4,8,9,11]
 * 
 * 返回 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);
 }
 
 }

结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bmN0_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bmN0_size_16_color_FFFFFF_t_70]: /images/20220216/1e119b37bfc64eefa322244a397e0d10.png