当前位置:网站首页>LeetCode 403. Frog crossing the river daily
LeetCode 403. Frog crossing the river daily
2022-07-07 16:59:00 【@Little safflower】
Problem description
A frog wants to cross the river . Suppose the river is divided equally into cells , And there may be a stone in each cell ( Maybe not ). Frogs can jump on stones , But don't jump into the water .
Here's a list of the locations of the stones stones( Use cell number Ascending Express ), Please judge whether the frog can cross the river successfully ( That is, whether we can jump to the last stone at the last step ). At the beginning of the , The frog stands on the first stone by default , And it can be assumed that its first step can only jump 1 A unit of ( That is, only from cells 1 Jump to cell 2 ).
If the frog jumps last k A unit of , Then its next jump distance can only be chosen as k - 1、k or k + 1 A unit of . Attention, please. , Frogs can only move forward ( The direction of the destination ) jumping .
Example 1:
Input :stones = [0,1,3,5,6,8,12,17]
Output :true
explain : Frogs can cross the river successfully , Jump as follows : jump 1 Units to 2 Block stone , Then jump 2 Units to 3 Block stone , next jump 2 Units to 4 Block stone , Then jump 3 Units to 6 Block stone , jump 4 Units to 7 Block stone , Last , jump 5 Units to 8 A stone ( The last stone ).
Example 2:Input :stones = [0,1,2,3,4,8,9,11]
Output :false
explain : This is because of the 5 And the 6 The space between the stones is too big , There is no alternative for frogs to jump over .
Tips :
2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
stones In strict ascending ordersource : Power button (LeetCode)
link :https://leetcode.cn/problems/frog-jump
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Java
class Solution {
public boolean canCross(int[] stones) {
int n = stones.length;
boolean[][] dp = new boolean[n + 1][n + 1];
dp[0][0] = true;
for(int i = 1;i < n;i++){
for(int j = 0;j < i;j++){
// From j Stone to i The minimum step size of a stone is k
int k = stones[i] - stones[j];
// The first j The maximum step length of a stone is j + 1
if(k <= j + 1){
// Can it be in steps k The speed reaches the i A stone
dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
}
}
}
for(int i = 1;i <= n;i++){
if(dp[n - 1][i]) return true;
}
return false;
}
}
边栏推荐
- 水平垂直居中 方法 和兼容
- 3000 words speak through HTTP cache
- 蓝桥杯 决赛 异或变换 100分
- LeetCode 152. 乘积最大子数组 每日一题
- typescript ts基础知识之tsconfig.json配置选项
- skimage学习(1)
- 【Seaborn】组合图表:FacetGrid、JointGrid、PairGrid
- 整理几个重要的Android知识,高级Android开发面试题
- Three. JS series (2): API structure diagram-2
- LeetCode 152. Product maximum subarray daily question
猜你喜欢
随机推荐
Interface oriented programming
Ray and OBB intersection detection
typescript ts 基础知识之类型声明
两类更新丢失及解决办法
字节跳动高工面试,轻松入门flutter
谎牛计数(春季每日一题 53)
typescript ts基础知识之tsconfig.json配置选项
Personal notes of graphics (1)
Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
Sqlserver2014+: create indexes while creating tables
Have fun | latest progress of "spacecraft program" activities
LeetCode 312. 戳气球 每日一题
Pychart ide Download
【Seaborn】组合图表:FacetGrid、JointGrid、PairGrid
字节跳动Android面试,知识点总结+面试题解析
Opencv configuration 2019vs
DNS 系列(一):为什么更新了 DNS 记录不生效?
3000 words speak through HTTP cache
【DesignMode】外观模式 (facade patterns)
LeetCode 1626. The best team without contradiction