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