数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学根据给定条件确定具有最大1的子序列的最小步骤
本文旨在实现一个程序，根据给定条件查找确定具有最大1的子序列的最小步骤。
众所周知，可以用以空值结尾的包含字符的一维数组来定义字符串。
给定一个长度为K的字符串Str，其中K始终为偶数，并且包含字符“0”、“1”和“?”。将字符串分成两个单独的字符串，分别称为Str1和Str2，每个字符串都将包含Str的偶数值和奇数值的字符。目标是确定预测哪个字符串（Str1或Str2）将具有最大数量的1所需的最小步骤数。在单个步骤中选择Str1或Str2的一个字符。如果字符为零，则选择'0'；如果字符为一，则选择'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″.
无论为剩余索引选择什么数字，在步骤4之后，Str2都将具有更多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″.
无论为剩余索引选择什么数字，在步骤7之后，Str2都将具有更多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现在也将比Str2具有更多的1。
步骤7 − 在测试基本情况后，检查i是偶数还是奇数。如果i是偶数，则Str1将选择此索引；否则，Str2将选择此索引。
步骤8 − 假设当前字符为“?”，即s[i] = '?'，则执行选择'1'和选择'0'的两次递归调用，在两者中都加入1后返回两个值的较小值。
步骤8 − 停止
由于上述原因，如果count2超过n1和count1的乘积，则返回0。
由于填充后字符串中可用位置的数量将减少一个位置，因此根据当前正在填充的字符串减少n1或n2。
否则，进行一次调用，然后加一得到答案。
最终的递归调用将提供此问题的答案。
示例：C++程序
以下是上述根据给定条件查找确定具有最大1的子序列的最小步骤的算法的C++程序实现
// 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
结论
同样，我们可以根据给定条件找到确定具有最大1的子序列的最小步骤。
本文解决了根据给定条件获得确定具有最大1的子序列的最小步骤的挑战。
这里提供了C++编程代码以及根据给定条件查找确定具有最大1的子序列的最小步骤的算法。
70 次浏览
