LeetCode 394: DecodeString (Java)

ccj659 發布于2019-08-14 15:50 / 2185人閱讀

摘要：思路非常清晰，但是實現起來并不簡單。得注意細節及其處理方式，比如數字可能出現兩位及以上并列關系和包含關系如何巧妙區分。另外發現大循環用而不是可能更方便一些。

解碼題。
編碼規則直接看例子(編碼后字符串->原字符串)：
2[b] -> bb
3[a2[c]] -> 3[acc] -> accaccacc
2[a2[b]ef]xy ->2[abbef]xy->abbefabbefxy

根據上面的結構我們很容易想到用深搜算法：

先將"]" 之前的信息（要重復的部分及重復次數）壓到stack里，等到了"]"再一個一個推出還原。思路非常清晰，但是實現起來并不簡單。得注意細節及其處理方式，比如數字可能出現兩位及以上; 并列關系［］,［］和包含關系［［］］如何巧妙區分。另外發現大循環用while而不是for可能更方便一些。

下面是我在leetcode論壇上找到的比較好看的代碼（44%）：

public static String decodeString(String s) {
    Stack count = new Stack<>();
    Stack result = new Stack<>();//用Stack處理包含關系

    result.push("");
    int i = 0;

    while(i= "0" && a <= "9"){
            int p1 = i;
            while(Character.isDigit(s.charAt(i+1))) i++;
            count.push(Integer.parseInt(s.substring(p1,i+1)));
        } else if (a == "[") {
            result.push("");//用初始化空字符串處理并列關系
        } else if(a == "]") {
            String temp = new String(result.pop());
            StringBuilder sb = new StringBuilder();
            int nloop = count.pop();
            for(int j = 0; j < nloop;j++)
                sb.append(temp);
            result.push(result.pop()+sb.toString());
        } else {
            result.push(result.pop()+a);
        }
        i++;
    }
    return result.pop();
}

當然也可以用遞歸算法，但我感覺比較難想，這種算法比較直接，面試的時候想到比較實際。

Ref：Java short and easy-understanding solution using stack

云服務器 GPU云服務器 DecodeString LeetCode LeetCode_String leetcode_35_SearchIn

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

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

LeetCode 394：字符串解碼 Decode String

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

鄒強 2019-08-19 10:30 評論0 收藏0
leetcode-394-Decode String

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

snifes 2019-07-30 17:38 評論0 收藏0
leetcode394. Decode String

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

Ilikewhite 2019-08-16 15:04 評論0 收藏0
Decode String

摘要：題目鏈接的題，感覺還是分析下什么時候，什么時候，思路會比較快。里面不加循環的寫法。 Decode String 題目鏈接：https://leetcode.com/problems... stack的題，感覺還是分析下stack什么時候pop，什么時候push，思路會比較快。loop里面不加while循環的寫法。 public class Solution { public S...

ysl_unh 2019-08-14 17:22 評論0 收藏0
GoJS 繪圖 (五) ：定位面板與垂直面板（Panel）

摘要：雖然只有一個面板，也有許多不同類型的面板，每個都有其自己的目的是如何安排的元素。這些都是存在的各種面板組成位置面板最簡單的一種面板是。每個元素獲得其正常大小，無論其默認大小或指定或等價的和。垂直面板面板的所有面板元件的排列垂直從上到下。 Panel是負責任的大小和位置的所有元素。每個面板建立自己的坐標系。一個面板的元件的繪制順序表示建立這些元素的Z軸排序。雖然只有一個面板，也有許多不同...

PrototypeZ 2019-08-19 18:26 評論0 收藏0