数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究二进制字符串中最长非递减子序列
在这个问题中，我们需要找到给定字符串中最长的非递减子序列。
非递减的意思是字符应该相同或按降序排列。由于二进制字符串只包含“0”和“1”，因此结果字符串应该以“1”开头，以“0”结尾，或者以“0”或“1”开头和结尾。
为了解决这个问题，我们将计算字符串每个位置的前缀“1”和后缀“0”，并找到前缀“1”和后缀“0”的最大和。
问题陈述 - 我们给定一个二进制字符串str。我们需要找到给定字符串中最长的非递减子序列。
示例
Input – str = "010100"
Output – 4
解释
最长的非递减子序列是“1100”。
Input – str = "010110010"
Output – 6
解释
最长的非递减子序列是“111000”。
Input – str = ‘00000000’
Output – 8
解释
最长的非递减子序列是“00000000”，它等于给定的字符串。
方法一
在这种方法中，我们将为每个索引存储前缀“1”和后缀“0”的计数。之后，我们从两个数组的相同索引获取值，将它们相加，并找到最大和。
算法
步骤1 - 定义pre1s和suffix0s数组来存储前缀1和后缀0。并将所有数组元素初始化为0。
步骤2 - 使用for循环遍历字符串并计算每个索引的前缀1。如果i > 0，则将前一个元素的值添加到当前元素。
步骤3 - 如果当前字符是“1”，则将pre1s[i]的当前值加1。
步骤4 - 现在，计算给定字符串中的后缀0。从末尾开始遍历字符串。
步骤5 - 如果“i”的值不等于“n – 1”，则获取“i + 1”元素的值并将其添加到当前元素。
步骤6 - 如果当前元素是“0”，则将当前元素加1。
步骤7 - 现在，将“res”变量初始化为0。
步骤8 - 使用循环遍历“pre1s”和“suffix0s”。
步骤9 - 从“pre1s”和“suffix0s”数组的第i个索引获取值，并将它们相加。如果“sum”大于“res”变量的当前值，则将“res”变量的值更改为“sum”值。
步骤10 - 返回“res”变量的值。
示例
对于输入“010100”，前缀数组将为[0, 1, 1, 2, 2, 2]，后缀0数组将为[4, 3, 3, 2, 2, 1]。和数组将为[4, 4, 4, 4, 4, 3]，和数组中的最大值为4。所以答案将是4。
#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
// To store the prefix count of '1's and suffix count of '0's
int pre1s[n] = {0},
suffix0s[n] = {0};
for (int i = 0; i < n; i++){
// get the prefix count of '1's
if (i > 0){
pre1s[i] += pre1s[i - 1];
}
// If the current character is '1', then update the pre1s array by adding 1; else, keep it as it is.
if (str[i] == '1'){
pre1s[i] += 1;
}
}
// get suffix count of '0's
for (int i = n - 1; i >= 0; i--) {
// add the suffix count of '0's
if (i != n - 1)
suffix0s[i] += suffix0s[i + 1];
// If the current character is '0', then update the suffix0s array by adding 1; else, keep it as it is.
if (str[i] == '0')
suffix0s[i] += 1;
}
// to store the final result value
int res = 0;
// iterate over the pre1s[] and suffix0s[] array and find the maximum value of pre1s[i] + suffix0s[i]
for (int i = 0; i < n; i++){
res = max(res, pre1s[i] + suffix0s[i]);
}
// Return the result
return res;
}
// Driver Code
int main(){
string str = "010100";
int N = str.length();
cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
return 0;
}
输出
The length of the longest non-increasing subsequence in the given binary string is - 4
时间复杂度 - O(N)，因为我们需要初始化前缀1和后缀0数组。
空间复杂度 - O(N)，因为我们将前缀1和后缀0存储在数组中。
方法二
在这种方法中，我们将首先计算零的总数。之后，我们开始遍历字符串并继续计数“1”并在找到0时减少“0”。此外，我们在每次迭代中对零和一的计数求和，并找到最大的结果值。
算法
步骤1 - 定义“count1”、“count0”和“res”变量并将它们初始化为0，分别存储1、0和最终结果的计数。
步骤2 - 通过遍历字符串并将结果存储在“count0”变量中来计算零的总数。
步骤3 - 现在，使用循环迭代字符串。
步骤4 - 在循环中，如果当前字符是“1”，则将“count1”的值增加1，否则将“count0”的值减少1。
步骤5 - 此外，将“res”和“count0 + count1”中的最大值存储到“res”变量中。
步骤6 - 当循环终止时，返回“res”变量的值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
int count1 = 0, count0 = 0;
int res = 0;
// counting total zeros in the string
for (int i = 0; i < n; i++){
if (str[i] == '0')
count0++;
}
// counting 1s from left, subtracting zeros from total zeros and adding both counts.
for (int i = 0; i < n; i++){
if (str[i] == '1')
count1++;
else
count0--;
res = max(res, count1 + count0);
}
return res;
}
int main(){
string str = "010110010";
int N = str.length();
cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
return 0;
}
输出
The length of the longest non-increasing subsequence in the given binary string is - 6
时间复杂度 - O(N)，因为我们计算字符串中零的总数并遍历字符串以找到最长的子序列。
空间复杂度 - O(1)
结论
在这里，两种方法的时间复杂度相同，但空间复杂度不同。第二种方法使用常量空间，因为我们优化了代码，但第一种方法使用动态空间来存储前缀1和后缀0的总数。
211 次浏览
