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

2023年 9月 13日 38.4k 0

根据给定条件确定具有最多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 拥有更多值。

  • 由于上述原因,如果 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 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

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论