|
5 | 5 | import java.util.Map;
|
6 | 6 | import java.util.Set;
|
7 | 7 |
|
8 |
| -/** |
9 |
| - * 403. Frog Jump |
10 |
| - * |
11 |
| - * A frog is crossing a river. |
12 |
| - * The river is divided into x units and at each unit there may or may not exist a stone. |
13 |
| - * The frog can jump on a stone, but it must not jump into the water. |
14 |
| -
|
15 |
| - Given a list of stones' positions (in units) in sorted ascending order, |
16 |
| - determine if the frog is able to cross the river by landing on the last stone. |
17 |
| - Initially, the frog is on the first stone and assume the first jump must be 1 unit. |
18 |
| -
|
19 |
| - If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. |
20 |
| - Note that the frog can only jump in the forward direction. |
21 |
| -
|
22 |
| - Note: |
23 |
| -
|
24 |
| - The number of stones is ≥ 2 and is < 1,100. |
25 |
| - Each stone's position will be a non-negative integer < 231. |
26 |
| - The first stone's position is always 0. |
27 |
| -
|
28 |
| - Example 1: |
29 |
| -
|
30 |
| - [0,1,3,5,6,8,12,17] |
31 |
| -
|
32 |
| - There are a total of 8 stones. |
33 |
| - The first stone at the 0th unit, second stone at the 1st unit, |
34 |
| - third stone at the 3rd unit, and so on... |
35 |
| - The last stone at the 17th unit. |
36 |
| -
|
37 |
| - Return true. The frog can jump to the last stone by jumping |
38 |
| - 1 unit to the 2nd stone, then 2 units to the 3rd stone, then |
39 |
| - 2 units to the 4th stone, then 3 units to the 6th stone, |
40 |
| - 4 units to the 7th stone, and 5 units to the 8th stone. |
41 |
| -
|
42 |
| -
|
43 |
| - Example 2: |
44 |
| -
|
45 |
| - [0,1,2,3,4,8,9,11] |
46 |
| -
|
47 |
| - Return false. There is no way to jump to the last stone as |
48 |
| - the gap between the 5th and 6th stone is too large. |
49 |
| -
|
50 |
| - */ |
51 | 8 | public class _403 {
|
52 | 9 |
|
53 | 10 | public static class Solution1 {
|
|
0 commit comments