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

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

本文的目的是实现一个程序，以找到最小步骤来根据给定条件确定最大 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 拥有更多值。< /p>

由于上述原因，如果 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 <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;
}

登录后复制