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

資訊專欄INFORMATION COLUMN

leetcode-394-Decode String

snifes / 1584人閱讀

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

原題：
 Given an encoded string, return it"s decoded string.
 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.
 You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
 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].
 Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
核心是理解題意，總結(jié)規(guī)律，屬于哪一類題目。 此題的規(guī)律在于 嵌套組合(數(shù)字+字母), 而且從dp的角度看，每消除一個(gè)底層【】，就會(huì)形成一個(gè)新的底層【】。
  所以規(guī)律是 解決 最里側(cè)的【】。如此往復(fù)。 
  完成從內(nèi)往外層層解決【】，需要保持字符串的記憶。stack可以完成。 再加上列表操作和字符串追加的小技巧。
  應(yīng)用：棧的操作，保持一個(gè)字符串的狀態(tài)，并可以從后往前進(jìn)行處理。
  記憶時(shí)間的先后順序， stack可以完成。 動(dòng)態(tài)規(guī)劃也可以。
  思考問題可以從前往后考慮解決辦法，也可以從后往前考慮，如果不能線性找到解決整體的辦法，就采用動(dòng)態(tài)規(guī)劃的思想，找到解決局部問題的方法。
正則解法：
import re
class Solution:
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        pattern=re.compile("(d+)[([a-zA-Z]+)]")
        while "[" in s:
            result_tmp=pattern.search(s)
            print(result_tmp.groups())
            # if result_tmp:
            #     for freq,dst in result_tmp.group():
            freq,dst = result_tmp.groups()
            dst_str=dst*int(freq)
            # print(dst)
            s=pattern.sub(dst_str,s)
            # print(dst,s)
        return s
if __name__=="__main__":
    s = "3[a]2[bc]"
    s = "3[a2[c]]"
    s="3[a]2[bc]"
    s="3[a]2[b4[F]c]"
    s="2[ab3[cd]]4[xy]"
    st=Solution()
    out=st.decodeString(s)
    print(out)

棧隊(duì)列解法：
class Solution:
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack=[[1,""]]
        final_str=""
        num=""
        for char_iter in s:
            if char_iter.isdigit():
                num+=char_iter
                # stack.append([char_iter,""])
            elif char_iter=="[":
                stack.append([int(num),""])
                num=""
            elif char_iter.isalpha():
                stack[-1][-1]+=char_iter
            elif char_iter=="]":
                # print(stack)
                freq_chars=stack.pop()
                # print(freq_chars)
                str_tmp=freq_chars[1]*int(freq_chars[0])
                stack[-1][-1]+=str_tmp
            else:
                stack[0][-1]+=str_tmp
        # print(final_str)
        # print(stack)
        return stack[0][1]


if __name__=="__main__":
    s = "3[a]2[bc]"
    s = "3[a2[c]]"
    s="3[a]2[bc]"
    s="3[a]2[b4[F]c]"
    s="2[ab3[cd]]4[xy]"
    s=""2[abc]3[cd]ef""
    s="100[leetcode]"
    st=Solution()
    out=st.decodeString(s)
    print(out)

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/42323.html

相關(guān)文章

  • leetcode394. Decode String

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

    Ilikewhite 評(píng)論0 收藏0

  • Python 字符串內(nèi)置方法

    摘要：字符串內(nèi)置方法作者博客返回字符串的第一個(gè)大寫字母。將序列中的元素字符串合并連接到一個(gè)字符串，作為分隔符。根據(jù)分隔符如果沒有提供默認(rèn)為空格分割并返回子串的列表如果給定了，則最多分為個(gè)子串。 Python 字符串內(nèi)置方法 作者博客：http://zzir.cn/ string.capitalize() 返回字符串的第一個(gè)大寫字母。 string.centr(width) 返回一個(gè)共 wid...

    tracymac7 評(píng)論0 收藏0

  • Java String類筆記

    摘要：這兩個(gè)操作符都是編譯器默認(rèn)引入了類，最后都調(diào)用方法返回對(duì)象，臨時(shí)對(duì)象被回收，因此效率極為低下 Java String類筆記 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處https://segmentfault.com/u/yzwall String的不可變性 String的不可變性 // String declaration public final class String ...

    Vicky 評(píng)論0 收藏0

  • 面試別再問我String了

    摘要：閱讀原文面試別再問我了字符串廣泛應(yīng)用在編程中，在中字符串屬于對(duì)象，提供了類來創(chuàng)建和操作字符串。測(cè)試此字符串是否以指定的后綴結(jié)束。當(dāng)執(zhí)行此句時(shí)，因?yàn)閷?duì)應(yīng)的實(shí)例已經(jīng)存在于字符串常量池中，所以會(huì)將此實(shí)例復(fù)制到會(huì)在堆中并返回引用地址。 閱讀原文：面試別再問我String了 字符串廣泛應(yīng)用 在Java 編程中，在 Java 中字符串屬于對(duì)象，Java 提供了 String 類來創(chuàng)建和操作字符串。...

    leon 評(píng)論0 收藏0

  • Java String、StringBuffer和StringBuilder類

    摘要：可以調(diào)用方法將其轉(zhuǎn)換為一個(gè)對(duì)象是線程安全的，則沒有實(shí)現(xiàn)線程安全功能，所以性能略高。通過串聯(lián)更方便將該對(duì)象與的對(duì)象進(jìn)行比較。追加字符串插入替換刪除反轉(zhuǎn)輸出輸出改變的長度，將只保留前面部分 String類是不可變類，即一旦一個(gè)String對(duì)象被創(chuàng)建以后，包括在這個(gè)對(duì)象中的字符序列是不可改變的，直至這個(gè)對(duì)象被銷毀 StringBuffer對(duì)象則代表一個(gè)字符序列可變的字符串，當(dāng)一個(gè)String...

    Jason 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

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