e907 - 108 p9. 二進位制密碼驗證
題目描述
題目要求驗證一個二進位制字串是否符合特定的密碼規則。規則包括：字串長度、包含的 0 和 1 的數量、以及是否包含特定的子字串 "101"。如果字串不符合任何規則，則輸出 "0"；否則，輸出不符合的規則編號，以空格分隔。
解題思路
程式碼直接根據題目描述的規則進行驗證。首先，檢查字串中是否包含除了 0 和 1 以外的字符。然後，檢查字串長度是否在 8 到 12 之間。接著，檢查字串中 0 的數量是否至少為 2，以及 1 的數量是否至少為 3。最後，檢查字串中是否包含子字串 "101"。如果任何一個條件不滿足，則輸出相應的規則編號。如果所有條件都滿足，則輸出 "0"。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串的長度。程式碼需要遍歷字串一次來計算 0 和 1 的數量，以及檢查是否存在 "101" 子字串。
- 空間複雜度: O(1)。程式碼只使用了幾個整數變數和一個布林變數，空間使用量不隨字串長度變化。
程式碼
#include <iostream>
using namespace std;
int main(){
bool ans=0,f=0;
string a;
cin >> a;
int al=a.length(),zero=0,one=0;
for(int i=0;i<al;++i){
if(a[i]=='1')++one;
if(a[i]=='0')++zero;
}
if(one+zero!=al){
cout << "1 ";
ans=1;
}
if(al>12||al<8){
cout << "2 ";
ans=1;
}
if(zero<2){
cout << "3 ";
ans=1;
}
if(one<3){
cout << "4 ";
ans=1;
}
for(int i=0;i<al-2;++i){
if(a[i]=='1'&&a[i+1]=='0'&&a[i+2]=='1'){
f=1;
break;
}
}
if(f==0){
cout << "5 ";
ans=1;
}
if(ans==0)
cout << "0 ";
}