2019/04/10 10:10

压缩算法 - 腾讯2020校招

输入样例:
HG[3|B[2|CA]]F

输出样例:
HGBCACABCACABCACAF


思路：

k 记录 '|' 位置。替换结束后 left 回到 right 的位置开始新一轮替换。

代码（优化后）：

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
string str;
cin >> str;
stack<int> s;
for (int right = 0; right < str.length(); right++){
//遇到 '[' 或 '|' 时入栈
if (str[right] == '[' || str[right] == '|')
s.push(right);
if (str[right] == ']'){
//出栈
int k    = s.top(); s.pop();
int left = s.top(); s.pop();
int num = stoi(str.substr(left + 1, k- left));
string s1 = str.substr(k + 1, right - k - 1);
string s2;
for (int i = 0; i < num; i++)
s2 += s1;
str = str.replace(left, right - left + 1, s2);
//计算新的right的位置
right = left+s2.size()-1;
}
}
cout << str;
}


代码（优化前）：

#include <iostream>
#include <string>
using namespace std;

int main() {
string str;
cin >> str;
for (int right = 0; right < str.length(); right++)
{
if (str[right] == ']')
{
int k = 0;
int left = right;
for (; str[left] != '['; left--)
if (str[left] == '|')
k = left;
int num = stoi(str.substr(left + 1, k - left));
string s1 = str.substr(k + 1, right - k - 1);
string s2;
for (int i = 0; i < num; i++)
s2 += s1;
str = str.replace(left, right - left + 1, s2);
right = left;
}
}
cout << str;
}


0
0 收藏

0 评论
0 收藏
0