網(wǎng)站建設(shè)的基本情況,龍華民治網(wǎng)站建設(shè)公司,網(wǎng)站頁面構(gòu)成,射陽建設(shè)局網(wǎng)站題目#xff1a; 給定一個(gè)經(jīng)過編碼的字符串#xff0c;返回它解碼后的字符串。 編碼規(guī)則為: k[encoded_string]#xff0c;表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次。注意 k 保證為正整數(shù)。 你可以認(rèn)為輸入字符串總是有效的#xff1b;輸入字符串中沒有額外的空…題目給定一個(gè)經(jīng)過編碼的字符串返回它解碼后的字符串。編碼規(guī)則為: k[encoded_string]表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次。注意 k 保證為正整數(shù)。你可以認(rèn)為輸入字符串總是有效的輸入字符串中沒有額外的空格且輸入的方括號(hào)總是符合格式要求的。此外你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字所有的數(shù)字只表示重復(fù)的次數(shù) k 例如不會(huì)出現(xiàn)像 3a 或 2[4] 的輸入。測(cè)試用例保證輸出的長度不會(huì)超過 105。示例 1輸入s “3[a]2[bc]”輸出“aaabcbc”示例 2輸入s “3[a2[c]]”輸出“accaccacc”示例 3輸入s “2[abc]3[cd]ef”輸出“abcabccdcdcdef”示例 4輸入s “abc3[cd]xyz”輸出“abccdcdcdxyz”解析這道題的本質(zhì)在于使用兩個(gè)棧來模擬遞歸的過程遇到左括號(hào)時(shí)保存當(dāng)前狀態(tài)遇到右括號(hào)時(shí)恢復(fù)狀態(tài)并計(jì)算。第一階段準(zhǔn)備階段準(zhǔn)備兩個(gè)空棧一個(gè)用于存儲(chǔ)數(shù)字重復(fù)次數(shù)一個(gè)用于存儲(chǔ)字符串初始化當(dāng)前數(shù)字為0當(dāng)前結(jié)果字符串為空第二階段遍歷解析從左到右掃描字符串的每個(gè)字符根據(jù)字符類型采取不同操作當(dāng)遇到數(shù)字時(shí)將當(dāng)前數(shù)字左移一位相當(dāng)于十進(jìn)制乘以10然后加上新數(shù)字這樣可以正確處理多位數(shù)字如23表示23次重復(fù)當(dāng)遇到左括號(hào)[時(shí)這標(biāo)志著一個(gè)新的嵌套層開始將當(dāng)前已構(gòu)建的字符串壓入字符串棧保存將當(dāng)前累計(jì)的數(shù)字壓入數(shù)字棧保存關(guān)鍵操作清空當(dāng)前數(shù)字和當(dāng)前字符串為內(nèi)層嵌套做準(zhǔn)備當(dāng)遇到右括號(hào)]時(shí)這標(biāo)志著當(dāng)前嵌套層結(jié)束從數(shù)字棧頂彈出重復(fù)次數(shù)從字符串棧頂彈出之前保存的字符串將當(dāng)前字符串重復(fù)指定次數(shù)然后拼接到彈出的字符串后面這個(gè)結(jié)果成為新的當(dāng)前字符串當(dāng)遇到普通字母時(shí)直接追加到當(dāng)前字符串末尾第三階段狀態(tài)管理的關(guān)鍵這種算法的精妙之處在于狀態(tài)的保存與恢復(fù)每次進(jìn)入新的括號(hào)層級(jí)時(shí)把外層狀態(tài)存入棧中自己從空白開始每次退出當(dāng)前層級(jí)時(shí)從棧中取出外層狀態(tài)合并當(dāng)前結(jié)果這模仿了遞歸函數(shù)的調(diào)用和返回過程具體代碼/** * param {string} s * return {string} */vardecodeStringfunction(s){letnumstack[]letstrstack[]letnum0letresfor(leti0;is.length;i){if(!isNaN(s[i])){numnum*10Number(s[i])}elseif(s[i][){strstack.push(res)numstack.push(num)num0res}elseif(s[i]]){constmultinumstack.pop()resstrstack.pop()res.repeat(multi)}else{ress[i]}}returnres};