青蛙跳跃回家所需的最小跳跃次数的 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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告