C++ 根据给定条件确定具有最多1的子序列的最小步骤

本文的目的是实现一个程序，根据给定条件找到确定具有最多1的子序列的最小步骤。

我们都知道，一个含有字符的一维数组，以null终止，可以用于定义字符串。

给定长度为K的字符串Str，其中K始终为偶数，并且包含字符”0″，”1″和”?”。将字符串分为两个单独的字符串，称为Str1和Str2，每个字符串都包含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″.

无论选择剩下的索引号是什么，进行第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多。

由于上述原因，如果count2超过了n1和count1的乘积，则返回0。

步骤7 − 在测试基本情况后验证是否i等于偶数或奇数。如果i是偶数，则Str1将选择此索引；如果不是，则选择Str2。

由于填充后字符串中可访问的位置数将减少一个位置，因此根据当前正在填充的字符串减少n1或n2。

步骤8 − 假设当前字符为’？’，即s[i] = ‘？’，则执行选择’1’的两个递归调用和选择’0’的递归调用，并返回两者中最小值加上1。

否则，进行单次调用，然后加上1以得到答案。

最终递归调用将提供对该查询的响应。

步骤8 − 停止

示例：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;
}