数据结构
网络
关系型数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++青蛙跳跃
假设有一只青蛙正在过河。河被分成x个单位，每个单位可能有一块石头。青蛙可以跳到石头上，但不能跳到水里。这里我们有一个按升序排列的石头位置列表，我们必须检查青蛙是否能够通过落在最后一块石头上来过河。
当青蛙当前跳跃了k个单位时，它下一步跳跃必须是k-1、k或k+1个单位。青蛙只能向前跳。
因此，如果给定的数组是[0,1,3,4,5,7,9,10,12]，则答案将为true，因为青蛙可以跳跃1个单位到第二块石头，2个单位到第三块石头，然后再次跳跃2个单位到第四块石头，然后跳跃3个单位到第六块石头，4个单位到第七块石头，最后跳跃5个单位到第八块石头。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个名为visited的映射
- 定义一个函数canCross()，它将接收一个数组stones，pos初始化为0，k初始化为0，
- key := pos 或 (k左移11位)
- 如果visited中存在key，则：
- 返回visited[key]
- 对于初始化i := pos + 1，当i < stones的大小，更新（i增加1），执行：
- gap := stones[i] - stones[pos]
- 如果gap < k - 1，则：
- 忽略以下部分，跳到下一次迭代
- 如果gap > k + 1，则：
- visited[key] := false
- 返回false
- 如果调用函数canCross(stones, i, gap)的结果非零，则：
- visited[key] = true
- 返回true
- 如果(pos等于stones的大小 - 1)则visited[key] = true，否则为false
- 返回visited[key]
让我们看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
unordered_map < lli, int > visited;
bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
lli key = pos | k << 11;
if(visited.find(key) != visited.end())return visited[key];
for(int i = pos + 1; i < stones.size(); i++){
int gap = stones[i] - stones[pos];
if(gap < k - 1)continue;
if(gap > k + 1){
return visited[key] = false;
}
if(canCross(stones, i, gap))return visited[key] = true;
}
return visited[key] = (pos == stones.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {0,1,3,5,6,8,12,17};
cout << (ob.canCross(v));
}输入
0,1,3,5,6,8,12,17
输出
1
更新于：2020年6月1日
1K+ 浏览量
广告