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

风辰小哥_5528

风辰小哥_5528

2023-09-13

1116人浏览

转载

根据给定条件确定具有最多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 秒的子序列。

目标是递归地解决问题并在考虑每种替代方案后得出解决方案。

Summarizer
Summarizer

一款基于AI的在线文本摘要工具,可将较长的文章和文字内容提炼为更加简洁的核心信息,方便快速阅读和理解。

下载

术语“递归”只不过是函数调用自身的过程,无论是直接(即没有中介)还是间接调用自身。该等价函数被认为是递归函数。此外,还可以使用递归算法来相对轻松地解决各种问题。

算法

根据下面给出的给定条件找到确定最大 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 <bits>
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 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">1

结论

同样,我们可以根据给定的条件找到确定最大为1s的子序列的最小步数

本文解决了根据给定条件获得确定最大 1 秒子序列的最少步骤的挑战。

这里提供了 C++ 编程代码以及根据给定条件找到确定最大 1 秒子序列的最小步骤的算法。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
c语言中null和NULL的区别
c语言中null和NULL的区别

c语言中null和NULL的区别是:null是C语言中的一个宏定义,通常用来表示一个空指针,可以用于初始化指针变量,或者在条件语句中判断指针是否为空;NULL是C语言中的一个预定义常量,通常用来表示一个空值,用于表示一个空的指针、空的指针数组或者空的结构体指针。

2023.09.22

569

3

java中null的用法
java中null的用法

在Java中,null表示一个引用类型的变量不指向任何对象。可以将null赋值给任何引用类型的变量,包括类、接口、数组、字符串等。想了解更多null的相关内容,可以阅读本专题下面的文章。

2024.03.01

1698

6

js 字符串转数组
js 字符串转数组

js字符串转数组的方法:1、使用“split()”方法;2、使用“Array.from()”方法;3、使用for循环遍历;4、使用“Array.split()”方法。本专题为大家提供js字符串转数组的相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.03

1938

5

js截取字符串的方法
js截取字符串的方法

js截取字符串的方法有substring()方法、substr()方法、slice()方法、split()方法和slice()方法。本专题为大家提供字符串相关的文章、下载、课程内容,供大家免费下载体验。

2023.09.04

3224

5

java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

2023.10.24

6424

49

字符串介绍
字符串介绍

字符串是一种数据类型,它可以是任何文本,包括字母、数字、符号等。字符串可以由不同的字符组成,例如空格、标点符号、数字等。在编程中,字符串通常用引号括起来,如单引号、双引号或反引号。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

2023.11.24

6629

6

java读取文件转成字符串的方法
java读取文件转成字符串的方法

Java8引入了新的文件I/O API,使用java.nio.file.Files类读取文件内容更加方便。对于较旧版本的Java,可以使用java.io.FileReader和java.io.BufferedReader来读取文件。在这些方法中,你需要将文件路径替换为你的实际文件路径,并且可能需要处理可能的IOException异常。想了解更多java的相关内容,可以阅读本专题下面的文章。

2024.03.22

8154

16

php中定义字符串的方式
php中定义字符串的方式

php中定义字符串的方式:单引号;双引号;heredoc语法等等。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

2024.04.29

12734

11

go语言字符串相关教程
go语言字符串相关教程

本专题整合了go语言字符串相关教程,阅读专题下面的文章了解更多详细内容。

2025.07.29

6619

17

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习