数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查给定二进制字符串的末尾是否可以通过选择给定范围内的跳跃值来到达
二进制字符串是指只包含两种不同字符（0 和 1）的字符串。给定一个二进制字符串和两个整数 L 和 R。我们可以在长度为 ‘L’ 和 ‘R’（包括两者）之间进行跳跃，并且只能从字符串值为 ‘0’ 的索引处跳跃。我们必须从第零个索引开始，并找出我们是否可以到达最后一个索引。
示例
Input1: string str = “01001110010” int L = 2, R = 4 Output: Yes, we can reach the last index.
解释
我们可以从第零个索引跳跃三次，然后跳跃四次两次，这样我们就可以到达最终所需的索引。
Input2: string str = “01001110010” int L = 2, R = 3 Output: No, we cannot reach the last index.
解释
我们可以跳跃两次，每次跳跃 2 或 3 步。如果我们从第零个索引跳跃，我们将到达第 2 个或第 3 个索引，从那里我们只能到达值为 ‘1’ 的索引，并且无法再进行跳跃。
方法 1
思路
思路是应用动态规划的概念。我们可以维护一个数组，该数组指示某个位置是否可以到达。
如果我们可以到达某个位置，那么接下来 l 到 r 个位置也可以到达。
实现
我们将创建一个函数，该函数将字符串、左位置和右位置作为参数，并返回布尔值。
在函数中，我们将遍历数组，并使用嵌套循环遍历范围，并检查当前位置减去当前范围位置是否可达，然后我们也可以到达此位置。
最后，我们将返回 DP 数组的最后一个索引的状态，它表示最终答案。
示例
#include <bits/stdc++.h>
using namespace std;
// function to implement the DP concepts
bool check(string str, int l, int r){
int len = str.length(); // length of the string
vector<int>dp(len); // vector to store the states results
// Initiating the first index
dp[0] = str[0] == '0';
// traversing over the array
for(int i=1; i<len; i++ ){
for(int j = l; j <= r ; j++){
if(i-j < 0){
break;
}
if(str[i-j] == '1' || dp[i-j] == 0){
continue;
}
else{
dp[i] = 1;
break;
}
}
}
return dp[len-1];
}
int main(){
string str = "01001110010";
int l = 2, r = 4;
// calling the function
int res = check(str, l, r);
if(res > 0){
cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
}
else{
cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
}
}
输出
Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range
时间和空间复杂度
上述代码的时间复杂度为 O(N^2)，其中 N 是给定字符串的大小。我们使用嵌套循环，这使得时间复杂度为 N^2。
上述代码的空间复杂度为 O(N)，因为我们使用长度为 N 的数组来存储 DP 状态。
方法 2
此方法是前一个方法的改进版本，在这个方法中，我们将维护一个整数来获取我们可以进行的跳跃次数。在每个位置，如果跳跃是可能的，我们可以增加计数，如果在任何位置跳跃是不可能的，我们可以减少计数。
我们将存储 DP 数组中每个索引处的数据，并稍后使用它。
示例
#include <bits/stdc++.h>
using namespace std;
bool check(string str, int l, int r){
int len = str.length(); // length of the string
vector<int>dp(len); // vector to store the states results
// initiating the first index
dp[0] = str[0] == '0';
int count = 0; // variable to maintain the count of the jump
// traversing over the array
for(int i=1; i<len; i++ ){
if (i >= l) {
count += dp[i - l];
}
if (i > r) {
count -= dp[i -r- 1];
}
dp[i] = (count > 0) and (str[i] == '0');
}
return dp[len-1];
}
// main function
int main(){
string str = "01001110010";
int l = 2, r = 4;
// calling the function
int res = check(str, l, r);
if(res > 0){
cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
} else {
cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
}
}
输出
Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定字符串的大小。我们使用单个循环遍历字符串，这使得时间复杂度为线性。
上述代码的空间复杂度为 O(N)，因为我们使用长度为 N 的数组来存储 DP 状态。
结论
在本教程中，我们实现了一个代码，用于查找我们是否可以从第一个索引开始并从给定字符串包含 ‘0’ 的索引移动给定数量的索引来到达给定字符串的末尾。我们已经实现了具有 O(N^2) 和 O(N) 时间复杂度以及 O(N) 空间复杂度的动态规划方法。
44 次查看
