壓縮演算法 - 騰訊2020校招
小Q想要給他的朋友發送一個神秘字串，但是他發現字串的過于長了，于是小Q發明了一種壓縮演算法對字串中重復的部分進行了壓縮
對于字串中連續的m個相同字串S將會壓縮為 [m | S ] (m為一個整數且1<=m<=100)，例如字串ABCABCABC將會被壓縮為[3|ABC]，現在小Q的同學收到了小Q發送過來的字串，你能幫助他進行解壓縮么？
輸入描述:
輸入第一行包含一個字串s，代表壓縮后的字串，
S的長度<=1000;
S僅包含大寫字母、[、]、|;
解壓后的字串長度不超過100000;
壓縮遞回層數不超過10層;
輸出描述:
輸出一個字串，代表解壓后的字串，
輸入樣例:
HG[3|B[2|CA]]F
輸出樣例:
HGBCACABCACABCACAF
思路：
由內向外替換，right 代表從左側第一個開始的 ']' 的位置, left 代表與當前 ']' 對應的 '[' 位置，
k 記錄 '|' 位置，替換結束后 left 回到 right 的位置開始新一輪替換，
優化：
經評論區dalao提醒，可以在遍歷時將 ' [ ' 和 ' |' 的位置分別入堆疊
當讀到 ' ] ' 時彈出，替換完畢后根據 left 的位置和串s2的長計算新的 right 的位置，省去了不必要的遍歷，感謝dalao，
代碼（優化后）：
#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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56828.html
標籤：C++
上一篇：結構體與鏈表
下一篇：結題報告