数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学C++ 中解码字符串
假设我们有一个编码的字符串；我们需要返回其解码后的字符串。编码规则为：k[encoded_string]，这表示方括号内的 encoded_string 被精确重复 k 次。我们可以假设原始数据不包含任何数字字符，并且数字仅用于重复次数 k。所以如果输入类似于“1[ba]2[na]”，那么输出将是“banana”。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个空栈，设置 i := 0
- 当 i < 字符串大小
- 如果 s[i] 是 ‘]’
- res := 从栈中删除元素，并仅获取方括号内的字符串。
- n := 0
- 当栈不为空，并且栈顶是数字字符时，则累加数字并形成实际整数 n
- 对于 j 范围从 1 到 n
- 对于 x 范围从 0 到 res 的大小
- 将 res[x] 插入到栈中
- 对于 x 范围从 0 到 res 的大小
- 否则将 s[i] 插入到栈中
- 将 i 增加 1
- 如果 s[i] 是 ‘]’
- ans := 一个空字符串
- 当栈不为空
- ans := 栈顶元素 + ans
- 从栈中弹出
- 返回 ans
示例（C++）
让我们看看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string decodeString(string s) {
stack <char> st;
int i = 0;
while(i<s.size()){
if(s[i] == ']'){
string res = "";
while(st.top()!='['){
res = st.top() + res;
st.pop();
}
st.pop();
int n = 0;
int x = 1;
while(!st.empty() && st.top()>='0' && st.top()<='9'){
n = n + (st.top()-'0')*x;
x*=10;
st.pop();
}
for(int j = 1; j <= n; j++){
for(int x = 0; x < res.size();x++){
st.push(res[x]);
}
}
}
else{
st.push(s[i]);
}
i++;
}
string ans ="";
while(!st.empty()){
ans = st.top() + ans;
st.pop();
}
return ans;
}
};
main(){
Solution ob;
cout << ob.decodeString("1[ba]2[na]");
}输入
"1[ba]2[na]"
输出
"banana"
更新于: 2020年4月28日
2K+ 浏览量
广告