資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告