成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode 394:字符串解碼 Decode String

鄒強(qiáng) / 2113人閱讀

摘要:用棧暫存的邏輯與遞歸基本一致,可以理解為用遞歸實(shí)現(xiàn)棧。沒有棧這種數(shù)據(jù)結(jié)構(gòu),可以用數(shù)組或雙端隊(duì)列可以只用一個(gè)棧以元組的形式重復(fù)次數(shù)和字符串,如利用棧初始化數(shù)據(jù)結(jié)構(gòu)遞歸字符串入棧刷新計(jì)算重復(fù)次數(shù)可直接操作字符串真的很方便。

題目:

給定一個(gè)經(jīng)過編碼的字符串,返回它解碼后的字符串。
Given an encoded string, return its decoded string.

編碼規(guī)則為: k[encoded_string],表示其中方括號內(nèi)部的 encoded_string 正好重復(fù) k 次。注意 k 保證為正整數(shù)。
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

你可以認(rèn)為輸入字符串總是有效的;輸入字符串中沒有額外的空格,且輸入的方括號總是符合格式要求的。
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

此外,你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字,所有的數(shù)字只表示重復(fù)的次數(shù) k ,例如不會出現(xiàn)像 3a2[4] 的輸入。
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won"t be input like 3a or 2[4].

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
解題思路:

? 這道題類似我們之前做過的一道題:有效的括號: https://mp.weixin.qq.com/s/Sm1S26EgR-dC75hrhVnZGQ

只不過""有效的括號"" [] 內(nèi)多了一些字符串需要操作。我們同樣可以用數(shù)據(jù)結(jié)構(gòu)棧來解題,,能用棧解決的題目大部分都可以用遞歸解決,兩者邏輯基本相同:

輸入:"3[a2[c]]"
初始化棧: 棧nums 存要重復(fù)的次數(shù)k,棧str 存字符串

遍歷字符串:
指針指向字符"3",為數(shù)字
num暫存數(shù)字3

繼續(xù)遍歷,遇到字符"["
循環(huán)次數(shù)num入棧nums,空字符串res入棧str
nums: 3        res: ""
num置為0,str置空

繼續(xù)遍歷,遇到字符"a",為字母
空字符串res拼接字母"a",res="a"

繼續(xù)遍歷,遇到字符"2",為數(shù)字
num暫存數(shù)字2

繼續(xù)遍歷遇到字符"["
num入棧nums,res入棧str
nums: 3 -> 2    str: "" -> "a"
num置為0,str置空

繼續(xù)遍歷,遇到字符"c",為字母
空字符串res拼接字母"c",res="c"

繼續(xù)遍歷遇到字符"]"
nums彈出棧頂元素:當(dāng)前字符串重復(fù)次數(shù)2
res = res*2 = "cc"
str彈出棧頂元素"a"與res拼接并入棧:
res = "a"+"cc"="acc"
str: "" -> "acc"

繼續(xù)遍歷遇到字符"]"
nums彈出棧頂元素:當(dāng)前字符串重復(fù)次數(shù)3
res = res*3 = "accaccacc"
str彈出棧頂元素空字符串""與res拼接并入棧:
res=""+"accaccacc"="accaccacc"
str: "accaccacc"

結(jié)束返回res

注意:

由于重復(fù)次數(shù)可能大于10,所以暫存數(shù)字時(shí)要適當(dāng)處理,如 num*10+當(dāng)前數(shù)字

在c++里可以直接修改拼接字符,但Java不支持運(yùn)算符重載,可以借助 StringBuilder 或 StringBuffer 類。

用棧暫存的邏輯與遞歸基本一致,可以理解為用遞歸實(shí)現(xiàn)棧。

python沒有棧這種數(shù)據(jù)結(jié)構(gòu),可以用 list() 數(shù)組或雙端隊(duì)列 deque()

python可以只用一個(gè)棧以元組的形式重復(fù)次數(shù)和字符串,如(num,res)

利用棧:

Java:

class Solution {
    public String decodeString(String s) {
        //初始化數(shù)據(jù)結(jié)構(gòu)
        Stack str = new Stack<>();
        Stack nums = new Stack<>();
        StringBuilder res = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {//遞歸字符串
            if (c == "[") {
                str.push(res);//入棧
                nums.push(num);
                num = 0;//刷新num、res
                res = new StringBuilder();
            } else if (c == "]") {
                StringBuilder tmp = new StringBuilder();
                for (int i = nums.pop(); i > 0; i--) tmp.append(res);//res*3
                res = str.pop().append(tmp);
            } else if (c >= "0" && c <= "9") num = num * 10 + (c - "0");//計(jì)算重復(fù)次數(shù)
            else res.append(c);
        }
        return res.toString();
    }
}

Python:

可直接操作字符串真的很方便。py里有現(xiàn)成的判斷字符串的方法:

isdigit() 是否為只包含數(shù)字的字符串

isalpha() 是否為只包含字母的字符串

class Solution:
    def decodeString(self, s: str) -> str:
        #初始化數(shù)據(jù)結(jié)構(gòu)
        stack, res, num = [], "", 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c.isalpha():
                res += c
            elif c == "[":
                #元組形式入棧
                stack.append((res, num))
                #刷新字符串和重復(fù)次數(shù)
                res, num = "", 0
            else:
                #如果c=="]",彈出字符串和重復(fù)次數(shù)
                last_str, this_num = stack.pop()
                res = last_str + this_num * res
        return res
利用遞歸:

Java:

將 s.length() 的值以參數(shù)傳遞,減少重復(fù)調(diào)用 length() 造成的時(shí)間損耗

class Solution {
    private int i = -1;//全局變量i,記錄字符數(shù)組指針位置
    
    public String decodeString(String s) {
        return dfs(s.toCharArray(), s.length()).toString();
    }
    //遞歸函數(shù)
    private StringBuilder dfs(char[] chars, int len) {
        int num = 0;
        StringBuilder str = new StringBuilder();
        while (++i < len) {
            if (chars[i] >= "0" && chars[i] <= "9")
                num = num * 10 + (chars[i] - "0");
            else if (chars[i] == "[") {
                StringBuilder tmp = dfs(chars, len);//遞歸調(diào)用
                while (--num >= 0) str.append(tmp);//重復(fù)字符串res=res*num
                num = 0;
            } else if (chars[i] == "]") return str;
            else str.append(chars[i]);
        }
        return str;
    }
}

Python:

class Solution:
    i = -1
    #遞歸函數(shù),可以直接操作字符串就無需再建一個(gè)dfs輔助函數(shù)
    def decodeString(self, s: str) -> str:
        res, num = "", 0
        while self.i < len(s) - 1:
            self.i += 1
            if s[self.i].isdigit():
                num = num * 10 + int(s[self.i])
            elif s[self.i].isalpha():
                res += s[self.i]
            elif s[self.i] == "[":
                #遞歸調(diào)用
                res += self.decodeString(s) * num
                num = 0
            elif s[self.i] == "]":
                return res
        return res

歡迎關(guān)注微.信公.眾號:愛寫B(tài)ug

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/76126.html

相關(guān)文章

  • leetcode394. Decode String

    摘要:利用棧我們可以存儲外圍層已持有的字符串以及應(yīng)當(dāng)展開的次數(shù)。用棧的思路來寫要求思路更加嚴(yán)謹(jǐn),以免出現(xiàn)邏輯錯(cuò)誤。這里需要額外注意的是,如果當(dāng)前該括號外圍存在父元素,則我們應(yīng)當(dāng)將父元素的計(jì)數(shù)和已有字符串壓入棧中。 題目要求 Given an encoded string, return its decoded string. The encoding rule is: k[encoded_...

    Ilikewhite 評論0 收藏0
  • leetcode-394-Decode String

    摘要:原題核心是理解題意,總結(jié)規(guī)律,屬于哪一類題目。完成從內(nèi)往外層層解決,需要保持字符串的記憶。再加上列表操作和字符串追加的小技巧。應(yīng)用棧的操作,保持一個(gè)字符串的狀態(tài),并可以從后往前進(jìn)行處理。動(dòng)態(tài)規(guī)劃也可以。正則解法棧隊(duì)列解法 原題: Given an encoded string, return its decoded string. The encoding rule is: k[enc...

    snifes 評論0 收藏0
  • LeetCode 394: DecodeString (Java)

    摘要:思路非常清晰,但是實(shí)現(xiàn)起來并不簡單。得注意細(xì)節(jié)及其處理方式,比如數(shù)字可能出現(xiàn)兩位及以上并列關(guān)系和包含關(guān)系如何巧妙區(qū)分。另外發(fā)現(xiàn)大循環(huán)用而不是可能更方便一些。 解碼題。編碼規(guī)則直接看例子(編碼后字符串->原字符串):2[b] -> bb3[a2[c]] -> 3[acc] -> accaccacc2[a2[b]ef]xy ->2[abbef]xy->abbefabbefxy 根據(jù)上面的結(jié)...

    ccj659 評論0 收藏0
  • [Leetcode] Encode and Decode Strings 符串解碼

    摘要:記錄長度法復(fù)雜度時(shí)間空間思路本題難點(diǎn)在于如何在合并后的字符串中,區(qū)分出原來的每一個(gè)子串。這里我采取的編碼方式,是將每個(gè)子串的長度先賦在前面,然后用一個(gè)隔開長度和子串本身。這樣我們先讀出長度,就知道該讀取多少個(gè)字符作為子串了。 Encode and Decode Strings Design an algorithm to encode a list of strings to a s...

    gself 評論0 收藏0
  • [Leetcode] Decode Ways 解碼方式

    摘要:最新更新請見動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路解碼是有規(guī)律的,所以我們可以嘗試動(dòng)態(tài)規(guī)劃。如果字符串的第位和第位不能組成有效二位數(shù)字,而且第位不是的話,說明我們是在第位的解碼方法上繼續(xù)解碼。 Decode Ways 最新更新請見:https://yanjia.me/zh/2019/02/... A message containing letters from A-Z is being en...

    animabear 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<