資料結構
網路
關係資料庫管理系統 (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.tw/cplusplus/cpp_strings.htm
https://tutorialspoint.tw/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
廣告