数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究青蛙跳跃回家所需的最小跳跃次数的 C++ 代码
假设我们有一个包含 n 位的二进制字符串 S 和另一个数字 d。在数轴上，一只青蛙想要从点 1 出发到达点 n。青蛙可以向右跳跃的距离不超过 d。对于从 1 到 n 的每个点，如果存在百合花，则标记为 1，否则标记为 0。青蛙只能跳跃到有百合花的点上。我们必须找到青蛙到达 n 所需的最小跳跃次数。如果不可能，则返回 -1。
因此，如果输入类似于 S = "10010101"；d = 4，则输出将为 2，因为从位置 1 开始，它跳到 4，然后在索引 8(n) 处。
步骤
为了解决这个问题，我们将遵循以下步骤 -
n := size of s x := 0 y := 0 while (x < n - 1 and y <= n), do: if s[x] is same as '1', then: x := x + d increase y by 1 Otherwise (decrease x by 1) if y >= n, then: return -1 Otherwise return y
示例
让我们看一下以下实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
int solve(string s, int d){
int n = s.size();
int x = 0, y = 0;
while (x < n - 1 && y <= n){
if (s[x] == '1')
x += d, ++y;
else
--x;
}
if (y >= n)
return -1;
else
return y;
}
int main(){
string S = "10010101";
int d = 4;
cout << solve(S, d) << endl;
}输入
"10010101", 4
输出
2
更新于: 2022-03-30
363 次查看
广告