国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode394. Decode String

Ilikewhite / 2234人閱讀

摘要:利用棧我們可以存儲外圍層已持有的字符串以及應當展開的次數。用棧的思路來寫要求思路更加嚴謹,以免出現邏輯錯誤。這里需要額外注意的是,如果當前該括號外圍存在父元素,則我們應當將父元素的計數和已有字符串壓入棧中。

題目要求
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".

將一個字符串解碼,要求按照次數展開原字符串中的中括號。如3[a]2[bc]對應的字符串就是aaabcbc,即a展開3次,bc展開2次。注意,源字符串中的括號是允許嵌套的,且展開的字符中不會包含任何數字。

思路一:遞歸

其實遞歸的思路是很明顯的,一旦我們遇到一個左括號,我們就可以找到其對應的右括號,然后對括號中的內容遞歸的展開,再將返回結果給上層,根據上次的次數再次展開。
3[a2[c]]=>3[acc]=>accaccacc

遞歸這里需要注意的是如何找到當前括號對應的右括號。這里可以采用一個小技巧,即從當前括號位置開始,每遇到一個左括號計數就+1,遇到一個右括號計數就-1,當計數器第一次被減為0時,則該位置上的右括號就是我們所要找的對應的右括號。

代碼如下:

    public String decodeString2(String s) {
        if (s.length() == 0)
            return "";

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= "0" && c <= "9") {
                // 解析次數
                int digitStart = i++;
                while (s.charAt(i) >= "0" && s.charAt(i) <= "9")
                    i++;
                int num = Integer.parseInt(s.substring(digitStart, i));

                // 找到對應的右括號
                int strStart = i+1; // number must be followed by "["
                int count = 1; 
                i++;
                while (count != 0) {
                    if (s.charAt(i) == "[")
                        count++;
                    else if (s.charAt(i) == "]")
                        count--;
                    i++;
                }
                i--; 

                // 取子字符串
                String subStr = s.substring(strStart, i);

                // 將子字符串解碼
                String decodeStr = decodeString(subStr);

                // 將解碼的結果拼接到當前的字符串后面
                for (int j = 0; j < num; j++) {
                    sb.append(decodeStr);
                }

            } else {
                // 添加首元素
                sb.append(c);
            }

        }

        return sb.toString();
    }
思路二:棧

我們知道,有一些遞歸的思路是可以轉化為棧的,這里同樣如此。利用棧我們可以存儲外圍層已持有的字符串以及應當展開的次數。用棧的思路來寫要求思路更加嚴謹,以免出現邏輯錯誤。首先,我們會用兩個指針lft,rgt分別來記錄數字的起始位置和結束位置。同時,rgt還作為我們遍歷整個字符串的指針。rgt的情形有如下幾種可能:

rgt指向[

rgt指向]

rgt指向數字

rgt指向字母

下面我們來逐個分析各種場景:

1. rgt指向[

此時左括號的左側只會有一種情形,它的左邊一定是數字。
因此當我們遇到左括號時,我們應當記錄左括號左邊的數字,并將lft指針移動到左括號下一個位置。這里需要額外注意的是,如果當前該括號外圍存在父元素,則我們應當將父元素的計數和已有字符串壓入棧中。可以將這個操作理解為上下文切換。

2. rgt指向]

右括號意味著當前的字符展開序列遍歷完畢,因此我們需要做以下幾件事情:

將lft和rgt之間的內容append到當前上下文的字符串中

根據展開次數展開當前上下文的字符串

如果存在父元素,則從棧中彈出父元素,恢復父級上下文

將當前上文得到的結果append到父元素的字符串中

3. rgt指向字母

我們需要將rgt指向的字母添加到當前的上下文字符串中去。不要忘記將左指針移動到當前位置后面

4. rgt指向數字

數字將會在遇見[時提取出來,因此我們無需進行任何處理

一個具體的例子

假如現在輸入的字符串為3[a2[c]],我們有字符串棧s,計數棧c,指針lft,rgt,并用臨時變量tmp,number分別記錄當前上下文中計數和字符串。運行情況如下:

lft=0 rgt=0 : 不執行任何操作
lft=0 rgt=1 : 解析當前上下文應當展開的次數 number=3, lft=2
lft=2 rgt=2 : 將當前的字符添加到當前的上下文中去,tmp="a" lft=3
lft=3 rgt=3 : 不做任何處理
lft=3 rgt=4 : 將父級上下文壓入棧中,并解析當前上下文的展開次數 s:["a"] c:[3] lft=5 tmp="" number=2
lft=5 rgt=5 : 將當前的字符添加到當前的上下文中去,tmp="c" lft=6
lft=6 rgt=6 : 展開當前字符串,并恢復父級上下文, tmp="a"+"cc", number=3 s:[] c:[] lft=7
lft=7 rgt=7 : 展開當前字符串,= 此時沒有父級上下文,因此無需恢復。tmp="accaccacc" number=0

代碼如下:

    public String decodeString(String s) {
        Stack count = new Stack<>();
        Stack letters = new Stack<>();
        int lft = 0, rgt = -1;
        int number = 0;
        StringBuilder result = null;
        while(++rgt < s.length()) {
            char c = s.charAt(rgt);
            if(c == "[") {
                if(result != null) {
                    count.push(number);
                    letters.push(result);
                }
                result = new StringBuilder();
                number = Integer.valueOf(s.substring(lft, rgt));
                lft = rgt+1;
            }else if(c == "]") {
                result.append(s.substring(lft, rgt));                    
                StringBuilder tmp = new StringBuilder(result);
                for(int i = 0 ; i


想要了解更多開發技術,面試教程以及互聯網公司內推,歡迎關注我的微信公眾號!將會不定期的發放福利哦~

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/73254.html

相關文章

  • leetcode-394-Decode String

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

    snifes 評論0 收藏0
  • LeetCode 394:字符串解碼 Decode String

    摘要:用棧暫存的邏輯與遞歸基本一致,可以理解為用遞歸實現棧。沒有棧這種數據結構,可以用數組或雙端隊列可以只用一個棧以元組的形式重復次數和字符串,如利用棧初始化數據結構遞歸字符串入棧刷新計算重復次數可直接操作字符串真的很方便。 題目: 給定一個經過編碼的字符串,返回它解碼后的字符串。Given an encoded string, return its decoded string. 編碼規則...

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

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

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

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

    gself 評論0 收藏0
  • [LintCode/LeetCode] Decode Ways [String to Integer

    摘要:用將子字符串轉化為,參見和的區別然后用動規方法表示字符串的前位到包含方法的個數。最后返回對應字符串末位的動規結果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...

    andong777 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<