本文的目的是实现一个程序，以找到最小步骤来根据给定条件确定最大 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 拥有更多值。
由于上述原因，如果 count2 超过 n1 和 count1 的乘积，则返回 0。
第 7 步 – 在测试基本实例后验证 i 是否等于偶数或奇数。如果i是偶数，Str1会选择这个索引；如果不是，则为 Str2。
由于填充后字符串中可访问位置的数量将减少一个位置，因此根据当前填充的字符串减少 n1 或 n2。
第 8 步 – 假设当前字符是 ‘?’即 s[i] = ‘? ‘ 然后执行选择“1”和挑选“0”的两次递归调用，将 1 合并到两者中后返回两者中的最小值。
否则，拨打一个电话，然后添加一个电话即可获得答案。
对此查询的响应将由最终的递归调用提供。
第 8 步 – 停止
示例：C++ 程序
这是上述编写的算法的 C 程序实现，用于根据给定条件查找最小步骤来确定最大 1 秒的子序列
// the C++ program of the above written algorithm#include using namespace std;// the function in order find the minimum number of the steps recursively needed by combining both the 2 stringsint 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 秒子序列的最小步骤的算法。
以上就是根据给定条件确定具有最多1的子序列的最小步骤的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445133.html
微信扫一扫 
支付宝扫一扫 
