e924 - pC. 括號配對
題目描述
題目要求判斷輸入字串中的各種括號（圓括號、方括號、小於大於括號、曲括號）是否正確配對。
解題思路
此題可以使用堆疊 (Stack) 的概念來解決。遍歷字串，遇到左括號時，將其推入堆疊；遇到右括號時，檢查堆疊頂部的左括號是否與其匹配。如果匹配，則將左括號從堆疊中彈出；如果不匹配，則判斷配對失敗。最後，如果堆疊為空，則表示所有括號都已正確配對；否則，表示配對失敗。程式碼中 d[0], d[1], d[2], d[3] 分別記錄了 (), {}, <>, [] 的數量，tmp 陣列模擬了堆疊，it 記錄了堆疊的頂端。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串的長度。因為需要遍歷字串一次。
- 空間複雜度: O(n)，在最壞情況下，如果輸入字串只包含左括號，則堆疊的大小將與字串的長度相同。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int main(){
int n,d[4]={0},it=0,tmp[1001]={0};
char a;
while(a=getchar_unlocked())
if(a=='\n')break;
bool ans=1;
while(a=getchar_unlocked()){
if(a==-1)break;
if(a=='\n'||a==-1){
if(d[0]||d[1]||d[2]||d[3])ans=0;
if(ans){
putchar_unlocked('Y');
putchar_unlocked('\n');
}
else{
putchar_unlocked('N');
putchar_unlocked('\n');
}
for(int i=0;i<1001;++i)
tmp[i]=0;
ans=1;
it=0;
d[0]=0;
d[1]=0;
d[2]=0;
d[3]=0;
}
else if(a=='('){
++d[0];
tmp[it]=-1;
++it;
}
else if(a=='{'){
++d[1];
tmp[it]=1;
++it;
}
else if(a=='<'){
++d[2];
tmp[it]=2;
++it;
}
else if(a=='['){
++d[3];
tmp[it]=3;
++it;
}
else if(a==')'){
--it;
if(!d[0]||it<0||tmp[it]!=-1)
ans=0;
tmp[it]=0;
--d[0];
}
else if(a=='}'){
--it;
if(!d[1]||it<0||tmp[it]!=1)
ans=0;
tmp[it]=0;
--d[1];
}
else if(a=='>'){
--it;
if(!d[2]||it<0||tmp[it]!=2)
ans=0;
tmp[it]=0;
--d[2];
}
else if(a==']'){
--it;
if(!d[3]||it<0||tmp[it]!=3)
ans=0;
tmp[it]=0;
--d[3];
}
}
}