leetcode403. Frog Jump

Soarkey 发布于2019-08-16 16:44 / 2164人阅读

摘要：石头的位置用整数数组来表示。广度优先遍历可以从起点开始，对从该点出发的所有可能步数进行遍历，并更新从该点可达的点的所有的可行步数。利用数据结构来记录该结果，其中的为的数，它的对应的是从该出发的所有的上一步的步长。

题目要求

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones" positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog"s last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

The number of stones is ≥ 2 and is < 1,100.
Each stone"s position will be a non-negative integer < 231.
The first stone"s position is always 0.
Example 1:

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

假设有一只青蛙需要过河，河中会有一些石子，青蛙必须踩在石头上才算成功。石头的位置用整数数组来表示。青蛙的行走规则为：假设上一次青蛙跳了k格，则当前青蛙只能跳k-1或k或k+1格，且青蛙只能向前跳，不能向后跳。

广度优先遍历

可以从起点开始，对从该点出发的所有可能步数进行遍历，并更新从该点可达的点的所有的可行步数。利用Map>数据结构来记录该结果，其中map的key为stone的unit数，它的value对应的是从该key出发的所有的上一步的步长。该遍历思路类似于广度优先遍历，即将该点出发遍历所有的可达点。代码如下：

    public boolean canCross(int[] stones) {
        if(stones.length < 2) return true;
        if(stones.length == 2 && stones[1] == 1) return true;
        if(stones.length >= 2 && stones[1] != 1) return false;
        Map> stoneJump = new HashMap<>();
        for(int i = 1 ; i());
        }
        stoneJump.get(1).add(1);
        int finalStone = stones[stones.length-1];
        boolean hasNext = false;
        for(int i = 1 ; i
深度优先遍历
和上一种思路的区别在于，这种方法会尽可能往远处遍历。即只要该点可以到达下一点，则会立刻尝试从一点到达终点。代码如下：
    public boolean canCross(int[] stones) {
        for(int i = 1 ; i i) return false;
        }
        return canCross2(stones, 1, 1);
    }
    
    public boolean canCross2(int[] stones, int idx, int lastStep) {
        if(idx == stones.length-1) return true;
        if(idx < 0 || lastStep <= 0) return false;
        for(int jump = lastStep + 1 ; jump >= lastStep -1 ; jump--) {
            if(canCross2(stones, Arrays.binarySearch(stones, stones[idx] + jump), jump)){
                return true;
            }
        }
        return false;
    }

云服务器 idc机房托管 Frog Jump jump.php Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74154.html

[LeetCode] 403. Frog Jump

Problem A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a li...

赵连江 2019-08-16 13:38 评论0 收藏0
[leetcode] 403. Frog Jump

摘要：还有一个石头可能由之前的多个石头到达，这又是可以优化的地方。当前结果可由之前的结果得出，且有重复的搜索方法，就需要用。 [链接描述]leetcode 题目。有点类似于jump game，只不过这里对步数有了隐形的要求，当前步数和之前步数有关。如果我们用brute force的方法来解，每一步有三种可能，一共n个石头，时间复杂度就是O(3^n)。这其中有很多步数是多余的，第i个石头...

mo0n1andin 2019-08-14 16:52 评论0 收藏0
leetcode45. Jump Game II

摘要：转换为广度优先算法即为我们只需要找到每一步的开始节点和结束下标，找到下一轮遍历的最大下标，如果该下标超过了数组长度，那么结束遍历，返回步数，否则将上一轮的最终节点加一作为起始节点，并将下一轮最大下标最为结束节点，继续遍历。题目要求 Given an array of non-negative integers, you are initially positioned at the ...

shiguibiao 2019-08-15 10:50 评论0 收藏0
LeetCode[45] Jump Game II

摘要：复杂度思路每次设置一个窗口，观察在这一步下能到达的最远距离，不断的移动这个窗口。计数，需要移动几次，才能覆盖到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

keelii 2019-08-14 15:02 评论0 收藏0
[LintCode/LeetCode] Jump Game I & II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0