数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：查找所有子串的MEX的最小和
假设我们有一个n位的二进制字符串S。令二进制字符串的操作MEX为在字符串中不出现的0、1或2中最小的数字。例如，MEX(001011)为2，因为0和1至少出现一次，MEX(1111)为0，因为0不存在且0最小。从给定的字符串S中，你应该将其切割成任意数量的子串，使得每个字符都恰好在一个子串中。可以将字符串切割成单个子串——整个字符串。我们必须找到所有子串片的MEX之和的最小值是多少？
问题类别
为了解决这个问题，我们需要操作字符串。编程语言中的字符串是存储在特定数组式数据类型中的字符流。几种语言将字符串指定为特定数据类型（例如Java、C++、Python）；而其他几种语言将字符串指定为字符数组（例如C）。字符串在编程中非常重要，因为它们通常是各种应用程序中首选的数据类型，并用作输入和输出的数据类型。有各种字符串操作，例如字符串搜索、子串生成、字符串剥离操作、字符串转换操作、字符串替换操作、字符串反转操作等等。查看下面的链接，了解如何在C/C++中使用字符串。
https://tutorialspoint.com/cplusplus/cpp_strings.htm
https://tutorialspoint.com/cprogramming/c_strings.htm
因此，如果我们问题的输入类似于S = "01"，则输出将为1，因为MEX(0)为1，MEX(1)为0，所以总和为1 + 0 = 1。
步骤
为了解决这个问题，我们将遵循以下步骤：
count := (1 if S[0] is 0, otherwise 0) for initialize i := 1, when S[i] is non-zero, update (increase i by 1), do: if S[i] is same as '0' and S[i] is not equal to S[i - 1], then: (increase count by 1) return minimum of count and 2
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int count = (S[0] == '0');
for (int i = 1; S[i]; i++)
if (S[i] == '0' && S[i] != S[i - 1])
count++;
return min(count, 2);
}
int main(){
string S = "01";
cout << solve(S) << endl;
}输入
"01"
输出
1
更新于：2022年4月8日
浏览量：224
广告