PART 01:思路
我们知道最后的字符串一定是一个左右两边为括号的串,所以先找一波括号。
- 第一步,找左右括号。
接着在两个括号之间找出两个冒号,所以还要存下左右括号的下标。
- 第一步,找左右括号并存下下标。
- 第二步,找左右冒号。
最后在两个冒号之间找 \(|\) 字符,所以还要存下冒号的下标。
- 第一步,找左右括号并存下下标。
- 第二步,在左右括号之间找左右冒号并存下下标(这里可以搞一搞资源重复利用)。
- 第三步,找左右冒号之间的 \(|\) 符号,并记录有多少个 \(|\) ,最终答案则是4加上 \(|\) 的个数。
PART 02:算法
2.1:初始化+找左右括号
int length=0;
string a;
cin>>a;
length=a.length();
int left=-1;
int right=-1;
for(int i=0;i<length;i++){
if(a[i]=='['&&left==-1){
left=i;
}
if(a[i]==']'){
right=i;
}
}
要点1:之所以要使用 length 变量来表示字符串 a 的长度,是为了之后使用方便,不必反复用函数读取,好习惯。
要点2:由于字符串下标从0开始,变量必须先赋值为负数,-1 较为方便。
要点3A:为了避免存在多个左括号,一定要保留最先出现的左括号下标!
要点3B:右括号为了找出最后出现的一个,遇到一个变一个,因为 i 在逐渐增大。
2.2:第一处合法性判断
if(left==-1||right==-1){
cout<<"-1"<<endl;
return 0;
}
显然,如果 left 没有变化(即没有左括号)或者 right 没有变化(即没有右括号),这个串是非法的。
2.3:初始化+找左右冒号
int l=-1;
int r=-1;
int flag=0;
for(int i=left+1;i<right;i++){
if(a[i]==':'&&flag==1){
r=i;
}
if(a[i]==':'&&flag==0){
flag=1;
l=i;
}
要点1:flag 的作用在于确认是否是第一个冒号,如果是,执行第二个 if 中的内容(确定左下标并改变 flag);否则执行第一个 if 中的内容(确定右下标)。
要点2:利用 flag 我们也实现了找出最小下标的左冒号与最大下标的右冒号,使得串最长化。
要点3:观察循环初始化与条件,发现我们是在左右括号内进行搜找(所以要记下两个括号的下标)。
要点4:第二个 if 必须放在第一个 if 的后面,否则遇到第一个冒号时,改变了 flag 的值,导致另外一个 if 不恰当开始。
2.4:第二处合法性判断
if(l==-1||r==-1){
cout<<"-1"<<endl;
return 0;
}
显然的,当找不出左冒号(变量 l 无变化)或右冒号(变量 r 无变化)时,该串不合法。
2.5:找 \(|\) 符号
int cnt=0;
for(int i=l+1;i<r;i++){
if(a[i]=='|'){
cnt++;
}
}
用 cnt 记录两个冒号之中 \(|\) 符号的个数,循环区间为两个冒号之间。
程序最后,直接输出 cnt+4 即可。
PART 03:AC 代码
本题中各部分已经讲得很透彻,不给出完整代码。