卓越飞翔博客
本文的目的是实现一个程序，以找到最小步骤来根据给定条件确定最大 1 秒的子序列。
众所周知，包含以 null 结尾的字符的一维数组可以用来定义字符串。
给定一个长度为 K 的字符串 Str，其中 K 始终为偶数，并且包含字符“0”、“1”和“？”将字符串分为两个单独的字符串，我们将它们称为 Str1 和 Str2，每个字符串都将包含 Str 偶数值和 Str 奇数值处的字符。目标是确定预测两个字符串（Str1 或 Str2）中 1 的数量最多所需的最少步骤。一步为 Str1 或 Str2 选择一个字符。当字符为零时选择“0”，如果字符为一则选择“1”，如果字符为“1”则选择“？”如果它是一个 1 或 0 的字符。
问题陈述
实现一个程序，根据给定条件找到最小步骤来确定最大 1 秒的子序列
示例 1
Input: Str = “?10?0?”
Output: 4
说明
第 1 步 - 这里 Str[0] 是“？”
So select "0" as the character for Str1.
Which implies Str1=”0″, Str2=”″.
第 2 步 - 这里 Str[1] 是“1”
Select "1" as the character for Str2.
Which implies Str1=”0″, Str2=”1″.
第 3 步 - 这里 Str[2] 是“0”
Select "0" as the character for Str1.
Which implies Str1=”00″, Str2=”1″.
第 4 步 - 这里 Str[3] 是“？”
Select "1" as the character for Str2.
Which implies Str1=”00″, Str2=”11″.
无论剩余索引选择什么数字，Str2 在第 4 步之后都会有更多的 1。
示例 2
Input: Str = “1?0??0110”
Output: 4
说明
第 1 步 - 这里 Str[0] 是“1”
So select "1" as the character for Str1.
Which implies Str1=”1″, Str2=”″.
第 2 步 - 这里 Str[1] 是“?”
Select "1" as the character for Str2.
Which implies Str1=”1″, Str2=”1″.
第 3 步 - 这里 Str[2] 是“0”
Select "0" as the character for Str1.
Which implies Str1=”10″, Str2=”1″.
第 4 步 - 这里 Str[3] 是“？”
Select "1" as the character for Str2.
Which implies Str1=”10″, Str2=”11″.
第 5 步 - 这里 Str[4] 是“？”
Select "0" as the character for Str1.
Which implies Str1=”100″, Str2=”11″.
第 6 步 - 这里 Str[5] 是“0”
Select "0" as the character for Str2.
Which implies Str1=”100″, Str2=”111″.
第 7 步 - 这里 Str[6] 是“1”
Select "1" as the character for Str1.
Which implies Str1=”1001″, Str2=”111″.
无论剩余索引选择什么数字，Str2 在第 7 步之后都会有更多的 1。
解决方案
为了找到最小步骤来根据给定条件确定最大 1 秒的子序列，我们采用以下方法。
下面给出了解决该问题的方法，并根据给定条件找到最小步骤来确定最大为 1 秒的子序列。
目标是递归地解决问题并在考虑每种替代方案后得出解决方案。
术语“递归”只不过是函数调用自身的过程，无论是直接（即没有中介）还是间接调用自身。该等价函数被认为是递归函数。此外，还可以使用递归算法来相对轻松地解决各种问题。
算法
根据下面给出的给定条件找到确定最大 1 秒子序列的最小步骤的算法
第 1 步 - 开始
第 2 步 - 定义递归函数。
步骤 3 - 定义字符串 Str 、整数 i、整数 count1 和 count2，用于分别存储 Str1 和 Str2 中直到 i 的个数。
步骤 4 - 定义整数 n1 和 n2 来存储 Str1 和 Str2 中的可用位置
步骤 5 - 如果 i 等于 m，则 Str1 和 Str2 都已完全填充，现在可以肯定地预期答案。因此请回复 0。
第 6 步 - 如果 count1 超过 n2 和 count2 的乘积，则返回 0，因为即使在选择了 Str2 中的所有值之后，Str1 现在也将比 Str2 拥有更多值。
第 7 步 - 在测试基本实例后验证 i 是否等于偶数或奇数。如果i是偶数，Str1会选择这个索引；如果不是，则为 Str2。
第 8 步 - 假设当前字符是 '?'即 s[i] = '? ' 然后执行选择“1”和挑选“0”的两次递归调用，将 1 合并到两者中后返回两者中的最小值。
第 8 步 - 停止
由于上述原因，如果 count2 超过 n1 和 count1 的乘积，则返回 0。
由于填充后字符串中可访问位置的数量将减少一个位置，因此根据当前填充的字符串减少 n1 或 n2。
否则，拨打一个电话，然后添加一个电话即可获得答案。
对此查询的响应将由最终的递归调用提供。
示例：C++ 程序
这是上述编写的算法的 C 程序实现，用于根据给定条件查找最小步骤来确定最大 1 秒的子序列
// the C++ program of the above written algorithm
#include <bits/stdc++.h>
using namespace std;
// the function in order find the minimum number of the steps recursively needed by combining both the 2 strings
int minimumSteps(string& Str, int cnt1, int cnt2,int n1, int n2, int m,int i){
// check whetherthe current pointer reach //the end
if (i == m) {
return 0;
}
// the Condition which indicates here that one string does more ones than the other regardless of which number is opted for theindexes which is remaining
if (cnt1 > (n2 + cnt2)
|| cnt2 > (n1 + cnt1)) {
return 0;
}
int ch1 = 0;
int ch2 = 0;
// on condition that i is found to be even, then choose the character for 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
结论
同样，我们可以根据给定的条件找到确定最大为1s的子序列的最小步数
本文解决了根据给定条件获得确定最大 1 秒子序列的最少步骤的挑战。
这里提供了 C++ 编程代码以及根据给定条件找到确定最大 1 秒子序列的最小步骤的算法。
