根据给定条件确定最多"1"的子序列的最小步骤
本文的目标是实现一个程序，根据给定条件，找到确定最多"1"的子序列的最小步骤。
众所周知，一个以空值结尾的包含字符的一维数组可以用来定义字符串。
给定一个长度为K的字符串Str，其中K始终为偶数，包含字符"0"、"1"和"?"。将字符串分成两个独立的字符串，分别称为Str1和Str2，每个字符串都包含Str偶数和奇数处的字符。目标是确定预测Str1和Str2中哪个字符串包含最多"1"所需的最少步骤。一步为Str1或Str2选择一个字符。当字符为零时，选择"0";当字符为一时，选择"1";当字符为一或零时，选择"?"。
问题描述
编写一个程序，根据给定条件，找出包含最多 1 的子序列的最小步骤。
示例 1
输入:Str = "?10?0?"
输出:4
解释
步骤 1 − 这里 Str[0] 为 "?
因此，选择"0"作为 Str1 的字符。 这意味着 Str1="0″，Str2="″。
步骤 2 − 这里 Str[1] 为 "1"
选择"1"作为 Str2 的字符。 这意味着 Str1="0″，Str2="1″。
步骤 3 − 此处 Str[2] 为"0"
选择"0"作为 Str1 的字符。 这意味着 Str1="00″，Str2="1″。
步骤 4 − 此处 Str[3] 为"?"
选择"1"作为 Str2 的字符。 这意味着 Str1="00″，Str2="11″。
无论剩余索引选择什么数字，Str2 在步骤 4 之后都会包含更多 1。
示例 2
输入:Str = "1?0??0110"
输出:4
解释
步骤 1 − 这里 Str[0] 为 "1"
因此，选择 "1" 作为 Str1 的字符。 这意味着 Str1="1″，Str2="″。
步骤 2 − 这里 Str[1] 为 "?
选择"1"作为 Str2 的字符。 这意味着 Str1="1″，Str2="1″。
步骤 3 − 这里 Str[2] 为 "0"
选择"0"作为 Str1 的字符。 这意味着 Str1="10″，Str2="1″。
步骤 4 − 此处 Str[3] 为 "?
选择"1"作为 Str2 的字符。 这意味着 Str1="10″，Str2="11″。
步骤 5 − 此处 Str[4] 为 "?
选择"0"作为 Str1 的字符。 这意味着 Str1="100″，Str2="11″。
步骤 6 − 此处 Str[5] 为"0"
选择"0"作为 Str2 的字符。 这意味着 Str1="100″，Str2="111″。
步骤 7 − 此处 Str[6] 为"1"
选择"1"作为 Str1 的字符。 这意味着 Str1="1001″，Str2="111″。
无论剩余索引选择什么数字，Str2 在步骤 7 之后都会有更多 1。
解决方法
为了在给定条件下找到确定最多 1 的子序列的最小步骤，我们采用以下方法。
下面给出了解决这个问题的方法，以及在给定条件下找到确定最多 1 的子序列的最小步骤。
目标是递归地解决问题，并在考虑所有替代方案后找到解决方案。
"递归"一词只不过是一个函数调用自身的过程，无论是直接调用(即没有中介)还是间接调用。这个等效函数被认为是递归函数。递归算法还可以相对轻松地解决各种问题。
算法
根据以下给定条件，找到确定最多包含 1 的子序列的最小步骤的算法
步骤 1 - 开始
步骤 2 - 定义递归函数。
步骤 3 - 定义字符串 Str、整数 i、整数 count1 和 count2，分别用于在 Str1 和 Str2 中存储从 i 到 1 的个数。
步骤 4 - 定义整数 n1 和 n2，用于存储 Str1 和 Str2 中的可用位置。
步骤 5 - 如果 i等于 m，则 Str1 和 Str2 都已完全填充，现在可以确定地预测答案。因此返回 0。
步骤 6 - 如果 count1 超过 n2 与 count2 的乘积，则返回 0，因为即使 Str2 中的所有 1 都被选中，Str1 中的 1 仍然比 Str2 多。
步骤 7 - 在测试基本实例后，验证 i 是等于偶数还是奇数。如果 i 是偶数，Str1 将选择该索引;如果不是，则返回 Str2。
步骤 8 − 假设当前字符为 '?'，即 s[i] = '? ' 然后执行两次递归调用，一次选择"1"，一次取出"0"，并将 1 添加到两者中，返回两者中最小的值。
步骤 8 - 停止
出于上述原因，如果 count2 超过 n1 与 count1 的乘积，则返回 0。
由于填充后字符串中可访问位置的数量将减少一个位置，因此根据当前正在填充的字符串减少 n1 或 n2。
否则，进行一次递归调用，然后将结果加 1 得到答案。
此查询的响应将由最后一次递归调用提供。
示例:C++ 程序
以下是上述算法的 C 程序实现，该算法根据给定条件，找到确定最多包含 1 的子序列的最小步骤。
// 上述算法的 C++ 程序
#include <bits/stdc++.h>
using namespace std;
// 该函数通过组合两个字符串来找到递归所需的最少步骤数
int minimumSteps(string& Str, int cnt1, int cnt2,int n1, int n2, int m,int i){
// 检查当前指针是否到达 //末尾
if (i == m) {
return 0;
}
// 此条件指示，无论剩余的索引选择哪个数字，一个字符串的"1"数都比另一个字符串多
if (cnt1 > (n2 + cnt2)
|| cnt2 > (n1 + cnt1)) {
return 0;
}
int ch1 = 0;
int ch2 = 0;
// 如果 i 为偶数，则选择 Str 的字符
if (i % 2 == 0) {
if (Str[i] == '?') {
return min( 1 + minimumSteps(Str, i + 1, cnt1 + 1, cnt2, n1 - 1, n2, m), 1 + minimumSteps( Str, i + 1, cnt1, cnt2, n1 - 1, n2, m));
} else if (Str[i] == '1') {
ch1 = 1 + minimumSteps(Str, i + 1, cnt1 + 1, cnt2, n1 - 1, n2, m);
return ch1;
} else {
ch2 = 1 + minimumSteps(Str, i + 1, cnt1, cnt2, n1 - 1, n2, m);
return ch2;
}
}
else {
if (Str[i] == '?') {
return min(1 + minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m),1 + minimumSteps(Str, i + 1,cnt1, cnt2, n1, n2 - 1, m));
} else if (Str[i] == '1') {
ch1 = 1+ minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m);
return ch1;
} else {
ch2 = 1+ minimumSteps( Str, i + 1, cnt1, cnt2, n1, n2 - 1, m);
return ch2;
}
}
}
int main(){
string str = "?10?0?01";
int M = str.size();
cout << minimumSteps(str, 0, 0, 0, M / 2, M / 2, M);
return 0;
}
输出
1
结论
同样，我们可以根据给定条件，找到确定最多 1 的子序列的最小步骤
本文解决了根据给定条件，获取确定最多 1 的子序列的最小步骤这一难题。
本文提供了 C++ 编程代码以及根据给定条件，找到最多 1 的子序列的最小步骤的算法。
