Dynamic Programming
, Bloomberg
Description:
A frog is crossing a river. The river is divided into some number of 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 can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1
unit.
If the frog's last jump was k
units, its next jump must be either k - 1
, k
, or k + 1
units. The frog can only jump in the forward direction.
Example 1:
Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: 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:
Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.
Constraints:
2 <= stones.length <= 2000
0 <= stones[i] <= 2^31 - 1
stones[0] == 0
Solution:
class Solution {
public boolean canCross(int[] stones) {
int n = stones.length;
// map{i, j}: the frog could jump j units from ith stone
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(i, new HashSet<>());
}
map.get(0).add(1);
for (int i = 1; i < n; i++) {
Set<Integer> jumpsFromI = map.get(i);
for (int j = 0; j < i; j++) {
int dis = stones[i] - stones[j];
if (map.get(j).contains(dis)) {
jumpsFromI.add(dis);
jumpsFromI.add(dis + 1);
jumpsFromI.add(dis - 1);
if (i == n - 1) return true;
}
}
}
return false;
}
}
class Solution {
public boolean canCross(int[] stones) {
int n = stones.length;
boolean[][] dp = new boolean[n][n + 1];
// dp[i][j]: whether the frog could jump j units from ith stone
dp[0][1] = true;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
int dis = stones[i] - stones[j];
/* important */
// if dis is lessor than zero, continue
// if dis is larger than i, continue
// if the frog cannot jump to i from j with dis unit, continue
if (dis < 0 || dis > i || !dp[j][dis]) continue;
dp[i][dis] = true;
if (dis > 0) dp[i][dis - 1] = true;
if (dis < n) dp[i][dis + 1] = true;
if (i == n - 1) return true;
}
}
return false;
}
}
Q1 Q2 BQ Group project比較OK Motivation What excites me? What is my motivation of doing that project. Good mo: excitation
Jan 9, 2022Description: You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where: horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut. Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 10^9 + 7. Solution:
Nov 23, 2021Description: A newly designed keypad was tested, where a tester pressed a sequence of n keys, one at a time. You are given a string keysPressed of length n, where keysPressed[i] was the ith key pressed in the testing sequence, and a sorted list releaseTimes, where releaseTimes[i] was the time the ith key was released. Both arrays are 0-indexed. The 0th key was pressed at the time 0, and every subsequent key was pressed at the exact time the previous key was released. The tester wants to know the key of the keypress that had the longest duration. The ith keypress had a duration of releaseTimes[i] - releaseTimes[i - 1], and the 0th keypress had a duration of releaseTimes[0]. Note that the same key could have been pressed multiple times during the test, and these multiple presses of the same key may not have had the same duration. Return the key of the keypress that had the longest duration. If there are multiple such keypresses, return the lexicographically largest key of the keypresses.
Nov 22, 2021or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up