資料結構
網路
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+ 瀏覽量
廣告