数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究最大化“10”子序列，最多将一个0替换为1
在这个问题中，我们需要通过最多替换一个“0”字符为“1”来最大化给定二进制字符串中的“10”子序列。
我们可以依次将每个“0”替换为“1”，并在更新后的字符串中找到最大数量的“10”子序列。
问题陈述 - 我们给定一个名为 str1 的二进制字符串，其中仅包含 0 和 1 字符。我们可以最多将一个“0”替换为“1”，并且需要找到给定字符串中“10”子序列的最大数量。
示例
输入
str1 = "10110"
输出
4
解释
“10110”子字符串在 {0, 1}、{2, 4} 和 {3, 4} 索引处仅包含 3 个“10”子序列。
当我们将第一个索引处的“0”更新为“1”时，我们得到“11110”字符串，其中包含 4 个“10”子序列，分别位于 {0, 4}、{1, 4}、{2, 4} 和 {3, 4} 索引处。
输入
str1 = ‘110’
输出
2
解释
该字符串已经包含 2 个“10”子序列，因此我们不需要将任何“0”替换为“1”。
输入
str1 = "011010";
输出
7
解释
初始子字符串在 {1, 3}、{2, 3}、{1, 5}、{2, 5} 和 {4, 5} 索引处包含 5 个“10”子序列。
替换第 0 个索引处的“0”后，我们得到 7 个“10”子序列，分别位于 {0, 3}、{1, 3}、{2, 3}、{0, 5}、{1, 5}、{2, 5} 和 {4, 5}。
如果我们替换第 3 个索引处的“0”，我们将得到 4 个“10”子序列。
如果我们替换第 5 个索引处的“0”，我们将得到 2 个“10”子序列。
因此，我们选择了第一个“0”，因为它在给定的二进制字符串中创建了最多的“10”子序列。
方法 1
当我们更改任何“0”为“1”时，我们会得到一些新的子序列，并丢失一些以前使用替换的“0”形成的子序列。
当我们用“1”替换“0”时，新形成的“10”子序列的数量与后缀零的数量相同，而丢失的子序列是前缀零的数量。
为了解决这个问题，我们将准备一个前缀 1 和后缀 0 的数组，并取后缀 0 和前缀 1 的最大减法值，即新形成的子序列。
算法
步骤 1 - 定义“suffixZeros”列表以存储二进制字符串每个字符的后缀零。此外，如果字符串的最后一个字符是“0”，则将列表的最后一个元素初始化为 1。否则，将其初始化为 0。
步骤 2 - 反向遍历字符串，并将前一个元素的后缀零的总和与 1 或 0 存储，具体取决于当前元素是否为 0。
步骤 3 - 此外，定义 prefixOnes 列表以存储每个字符串索引处的总前缀“1”。此外，将列表的第一个元素初始化为 1 或 0，具体取决于字符串的第一个字符是否为 1。
步骤 4 - 开始遍历字符串，并将前一个元素的前缀 1 的总和与 1 或 0 存储到当前前缀值，具体取决于当前元素是否为 1。
步骤 5 - 接下来，我们需要计算给定字符串中最初的“10”子序列。
步骤 5.1 - 在遍历字符串时，如果我们得到“1”，我们需要将下一个索引处的后缀零添加到“initialPairs”变量中，因为“1”可以与所有后面的“0”形成“10”子序列。
步骤 6 - 接下来，我们需要计算替换“0”为“1”后添加的子序列总数。
步骤 6.1 - 开始遍历字符串，如果第 p 个索引处的字符为“0”，请执行以下步骤。
步骤 6.2 - 如果 p 等于字符串长度 – 1，则将“add”变量更新为 0，因为当我们更新最后一个“0”时，我们无法形成新的“10”子序列。
步骤 6.3 - 否则，将“add”变量的值更新为下一个索引处的后缀零。
步骤 6.4 - 如果 p 等于 0，则将“remove”更新为 0，因为当我们将第一个索引处的“0”替换为“1”时，它不会影响其他子序列。
步骤 6.5 - 否则，将“remove”初始化为前一个索引处的前缀 1。
步骤 6.6 - 在“addPairs”存储中，add 和 remove 值的减法是净添加的子序列。
步骤 6.7 - 如果“addParis”值为最大值，则更新“newPairs”变量的值。
步骤 7 - 返回初始对和添加对的总和。
示例
以下是上述方法的程序 -
#include <stdio.h>
#include <string.h>
int maxSubSeq(char str[]) {
int str_len = strlen(str);
// To store suffix zeros
int suffixZeros[str_len + 1];
// Checking if its value is 0
suffixZeros[str_len - 1] = (str[str_len - 1] == '0') ? 1 : 0;
for (int p = str_len - 2; p >= 0; p--) {
suffixZeros[p] = suffixZeros[p + 1] + (str[p] == '0');
}
// To store prefix ones
int prefixOnes[str_len];
// Initializing prefixOnes[0]
prefixOnes[0] = (str[0] == '1') ? 1 : 0;
// Counting prefix ones
for (int p = 1; p < str_len; p++) {
prefixOnes[p] = prefixOnes[p - 1] + (str[p] == '1');
}
int initialPairs = 0;
for (int p = 0; p < str_len; p++) {
if (str[p] == '1')
// Calculating initial pairs. '1' can form the subsequence '10' with all suffix zeros.
initialPairs += suffixZeros[p + 1];
}
// New pairs
int newPairs = 0;
int add = 0, remove = 0;
// Traverse the string
for (int p = 0; p < str_len; p++) {
// As we need to replace '0' and find the maximum subsequences
if (str[p] == '0') {
if (p == str_len - 1) {
add = 0;
} else {
add = suffixZeros[p + 1];
}
if (p == 0) {
remove = 0;
} else {
remove = prefixOnes[p - 1];
}
// Total added pairs
int addPairs = add - remove;
// Finding the maximum new pairs
if (addPairs > newPairs) {
newPairs = addPairs;
}
}
}
// Maximum final pairs
return initialPairs + newPairs;
}
int main() {
char str1[] = "10110";
printf("The maximum subsequences we can form by replacing the 0 with 1 is - %d\n", maxSubSeq(str1));
return 0;
}
输出
The maximum subsequences we can form by replacing the 0 with 1 is - 4
#include <bits/stdc++.h>
using namespace std;
int maxSubSeq(string str) {
int str_len = str.length();
// To store suffix zeros
vector<int> suffixZeros(str_len + 1);
// Checking if its value is 0
suffixZeros[str_len - 1] = str[str_len - 1] == '0';
for (int p = str_len - 2; p >= 0; p--) {
suffixZeros[p] = suffixZeros[p + 1] + (str[p] == '0');
}
// To store prefix ones
vector<int> prefixOnes(str_len);
// Initializing prefixOnes[0]
prefixOnes[0] = (str[0] == '1');
// Coutning prefix ones
for (int p = 1; p < str_len; p++) {
prefixOnes[p] = prefixOnes[p - 1] + (str[p] == '1');
}
int initialPairs = 0;
for (int p = 0; p < str_len; p++) {
if (str[p] == '1')
// Calculating initial pairs. '1' can form the subsequence '10' with all suffix zeros.
initialPairs += suffixZeros[p + 1];
}
// New pairs
int newPairs = 0;
int add = 0, remove = 0;
// Traverse the string
for (int p = 0; p < str_len; p++) {
// As we need to replace '0' and find the maximum subsequences
if (str[p] == '0') {
if (p == str_len - 1) {
add = 0;
} else {
add = suffixZeros[p + 1];
}
if (p == 0) {
remove = 0;
} else {
remove = prefixOnes[p - 1];
}
// Total added pairs
int addPairs = add - remove;
// Finding maximum new pairs
newPairs = max(newPairs, addPairs);
}
}
// Maximum final pairs
return initialPairs + newPairs;
}
int main(){
string str1 = "10110";
cout << "The maximum subsequences we can form by replacing the 0 with 1 is - " << maxSubSeq(str1);
return 0;
}
输出
The maximum subsequences we can form by replacing the 0 with 1 is - 4
public class MaxSubsequences {
public static int maxSubSeq(String str) {
int str_len = str.length();
// To store suffix zeros
int[] suffixZeros = new int[str_len + 1];
// Checking if its value is 0
suffixZeros[str_len - 1] = (str.charAt(str_len - 1) == '0') ? 1 : 0;
for (int p = str_len - 2; p >= 0; p--) {
suffixZeros[p] = suffixZeros[p + 1] + (str.charAt(p) == '0' ? 1 : 0);
}
// To store prefix ones
int[] prefixOnes = new int[str_len];
// Initializing prefixOnes[0]
prefixOnes[0] = (str.charAt(0) == '1') ? 1 : 0;
// Counting prefix ones
for (int p = 1; p < str_len; p++) {
prefixOnes[p] = prefixOnes[p - 1] + (str.charAt(p) == '1' ? 1 : 0);
}
int initialPairs = 0;
for (int p = 0; p < str_len; p++) {
if (str.charAt(p) == '1')
// Calculating initial pairs. '1' can form the subsequence '10' with all suffix zeros.
initialPairs += suffixZeros[p + 1];
}
// New pairs
int newPairs = 0;
int add = 0, remove = 0;
// Traverse the string
for (int p = 0; p < str_len; p++) {
// As we need to replace '0' and find the maximum subsequences
if (str.charAt(p) == '0') {
if (p == str_len - 1) {
add = 0;
} else {
add = suffixZeros[p + 1];
}
if (p == 0) {
remove = 0;
} else {
remove = prefixOnes[p - 1];
}
// Total added pairs
int addPairs = add - remove;
// Finding maximum new pairs
if (addPairs > newPairs) {
newPairs = addPairs;
}
}
}
// Maximum final pairs
return initialPairs + newPairs;
}
public static void main(String[] args) {
String str1 = "10110";
System.out.println("The maximum subsequences we can form by replacing the 0 with 1 is - " + maxSubSeq(str1));
}
}
输出
The maximum subsequences we can form by replacing the 0 with 1 is - 4
def maxSubSeq(s):
str_len = len(s)
# To store suffix zeros
suffix_zeros = [0] * (str_len + 1)
# Checking if its value is 0
suffix_zeros[str_len - 1] = 1 if s[str_len - 1] == '0' else 0
for p in range(str_len - 2, -1, -1):
suffix_zeros[p] = suffix_zeros[p + 1] + (s[p] == '0')
# To store prefix ones
prefix_ones = [0] * str_len
# Initializing prefix_ones[0]
prefix_ones[0] = 1 if s[0] == '1' else 0
# Counting prefix ones
for p in range(1, str_len):
prefix_ones[p] = prefix_ones[p - 1] + (s[p] == '1')
initial_pairs = 0
for p in range(str_len):
if s[p] == '1':
# Calculating initial pairs. '1' can form the subsequence '10' with all suffix zeros.
initial_pairs += suffix_zeros[p + 1]
# New pairs
new_pairs = 0
add = 0
remove = 0
# Traverse the string
for p in range(str_len):
# As we need to replace '0' and find the maximum subsequences
if s[p] == '0':
if p == str_len - 1:
add = 0
else:
add = suffix_zeros[p + 1]
if p == 0:
remove = 0
else:
remove = prefix_ones[p - 1]
# Total added pairs
add_pairs = add - remove
# Finding the maximum new pairs
new_pairs = max(new_pairs, add_pairs)
# Maximum final pairs
return initial_pairs + new_pairs
str1 = "10110"
print("The maximum subsequences we can form by replacing the 0 with 1 is -", maxSubSeq(str1))
输出
The maximum subsequences we can form by replacing the 0 with 1 is - 4
时间复杂度 – O(N) 用于计算后缀零、前缀 1 以及通过最多将“0”替换为“1”来查找最大“10”子序列。
空间复杂度 – O(N) 用于存储前缀 1 和后缀 0。
通过解决上述问题，程序员学习了如何查找前缀和后缀数组。此外，我们还学习了如何通过试错法获得输出，因为我们用“1”替换每个“0”，并在给定字符串中找到最大“10”子序列。
100 次查看
