原题链接:https://www.luogu.com.cn/problem/P1928
题意解读:要对形如xxx[Nxxx]xxx的字符串进行解码,[]内第一个数表示括号中字符串重复的次数,可以嵌套。
解题思路:
用递归进行处理,设函数decode(start,end)将下标从start到end之间字符串进行解码
递归过程如下:
遍历start~end的每一个字符
1、如果如果不是"[",直接输出
2、如果是"[",则一直找到与之配对的"]",并提取出"["之后的数字num
for 1...num
decode(num之后的字符下标,]之前的字符下标)
算法的关键在于利用三个指针i,j,k
i指针用来遍历整个字符串,j指针用来提出"["之后的整数,k指针用来找到与"["配对的"]"
具体实现见代码注释。
100分代码:
#include <bits/stdc++.h>
using namespace std;
string s;
void decode(int l, int r)
{
int match = 0;
for(int i = l; i <= r; i++) //遍历l~r之间每一个字符
{
if(s[i] != '[') //如果是"["则直接输出
{
cout << s[i];
continue;
}
match++; //用match来寻找与"["配对的"]"",遇到"["match++,遇到"]"match--,match==0则找到
int num = 0;
int j = i + 1; //j指针用来提取"["之后的整数
while(s[j] >= '0' && s[j] <= '9')
{
num = num * 10 + s[j] - '0';
j++; //循环结束后j的位置即是"[]"中第一个非数字字符的位置
}
int k = j - 1; //k指针用来寻找与"["配对的"]"
while(match)
{
char c = s[++k]; //循环结束后,k的位置即是配对的"]"的位置
if(c == '[') match++;
else if(c == ']') match--;
}
for(int i = 1; i <= num; i++) decode(j, k - 1);
i = k;
}
}
int main()
{
cin >> s;
decode(0, s.size() - 1);
return 0;
}
标签:end,递归,int,洛谷题,decode,num,P1928,指针,外星 From: https://www.cnblogs.com/jcwy/p/18018845