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

資訊專欄INFORMATION COLUMN

【LintCode】Expression Expand 非遞歸stack完成DFS(String)

livem / 1636人閱讀

摘要:直接的方法不可取因為是每一層。層直接從取出實際上是將這個后應該得到。這個時候考慮逆向,建立一個,將出來的東西再一個順序,逆逆得順是一個很好用的操作符,判斷一個對象是否是一個類的實例。坑小心一點這種情況啊代碼

這道題真是超級棒的stack DFS樣板題啊,在這里給自己寫個小小的總結

思路:
想到stack并不難,這種嵌套式一般是DFS的思想,先走到最里面最小的那個括號,然后逐漸回到上一層→上一層。又∵非遞歸,“BFS queue, DFS stack”。想到用stack并不難
Stack non-recursion DFS template
要點是,處理完之后重新返回stack,才能夠回到上一層操作

這個題具體操作起來真是很多可圈可點的地方,主要是在于String的處理上

reverse
因為stack的順序,在這個題中需要每次將每層里的內容reverse。直接StringBuilder的reverse方法不可取:因為是reverse每一層。e.g. 3[ab]2[c]層直接從stack取出實際上是cc, ababab將這個reverse后應該得到abababcc。這個時候考慮逆向stack,建立一個stack buffer,將stack pop出來的東西再reverse一個順序,逆逆得順

instanceof
nstanceof是一個很好用的操作符,a instanceof A,判斷“一個對象是否是一個類的實例”。作為操作符instanceof不可以直接在最前面!取非(比如>=這種也是),而是用 a instanceof A == false之類的判斷

復制StringBuilder
add到底append幾次,怎么append:直接append add 是不可以的,因為add是在變的,必須要先將第一個add保存起來,類似于dummy node,預先保存queue size這種“錨定”。


小心一點0[peer], -3[aaa]這種情況啊!

代碼
public class Solution {

public String expressionExpand(String s) {
    Stack stack = new Stack<>();
    char[] arr = s.toCharArray();
    
    int num = 0;
    for(char c : arr){
       if(Character.isDigit(c)){
           num = num * 10 + c - "0";
       }
       else if(c == "["){
           stack.push(Integer.valueOf(num));
           num = 0;
       }
       else if(c == "]"){
           popStack(stack);
       }
       else{
           stack.push(c);
       }
    }
    popStack(stack);
    return stack.pop().toString();
}
private void popStack(Stack stack){
    StringBuilder add = new StringBuilder();
    int count;
    Stack buffer = new Stack();
    while(!stack.isEmpty() && stack.peek() instanceof Integer == false){
        buffer.push(stack.pop());
    }
    while(!buffer.isEmpty()){
        add.append(buffer.pop());
    }
    
    count = stack.isEmpty()? 1 : (Integer) stack.pop();
    StringBuilder part = new StringBuilder(add);
    if(count > 0){
        for(int i = 0; i < count - 1; i++)
            add.append(part);
        stack.push(add);// reput
    }
}

}

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

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

相關文章

  • [LintCode] Expression Tree Build

    Problem The structure of Expression Tree is a binary tree to evaluate certain expressions.All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an o...

    qpal 評論0 收藏0
  • 表達式類算法題小結

    摘要:將表達式轉換為逆波蘭式,然后求值轉換中綴表達式為逆波蘭式魯棒性檢測,表達式中沒有操作數計算逆波蘭式值參考 表達式類算法題小結 [TOC] 聲明 文章均為本人技術筆記,轉載請注明出處:[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/ 表達式分類 根據運算符與相關操作操作數的位置不同,將表達式分為前綴,中綴和后綴表...

    Heier 評論0 收藏0
  • [LintCode] Topological Sorting [BFS & DFS]

    摘要:當隊列非空時,拿出最后放入的元素。若減后入度為,則這個結點遍歷完成,放入結果數組和隊列。遞歸函數去遍歷的,繼續在中標記,使得所有點只遍歷一次。最深的點最先,根結點最后,加入結果數組的頭部處。 Problem Given an directed graph, a topological order of the graph nodes is defined as follow: For ...

    draveness 評論0 收藏0
  • js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現與遞歸實現)

    摘要:樹中結點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷,深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結構等中序遍歷可以實現表達式樹,在編譯器底層很有用后序遍歷可以用來實現計算目錄內的文件及其信息等。 樹的簡介 棧、隊列、鏈表等數據結構,都是順序數據結構。而樹是非順序數據結構。樹型結構是一類非常重要的非線性結構。直觀地,樹型結構是以分支關系定義的層次結...

    Yuanf 評論0 收藏0
  • [LintCode] Evaluate Reverse Polish Notation

    摘要:中的運算符,運算之后要出來,繼續遍歷數組。是放入新的數字,用轉換為均可。 Problem Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another ...

    luckyyulin 評論0 收藏0

發表評論

0條評論

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