亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

【LintCode】Expression Expand 非遞歸stack完成DFS（String）

livem / 1734人閱讀

摘要：直接的方法不可取因?yàn)槭敲恳粚?。層直接從取出?shí)際上是將這個(gè)后應(yīng)該得到。這個(gè)時(shí)候考慮逆向，建立一個(gè)，將出來的東西再一個(gè)順序，逆逆得順是一個(gè)很好用的操作符，判斷一個(gè)對(duì)象是否是一個(gè)類的實(shí)例。坑小心一點(diǎn)這種情況啊代碼

這道題真是超級(jí)棒的stack DFS樣板題啊，在這里給自己寫個(gè)小小的總結(jié)

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

這個(gè)題具體操作起來真是很多可圈可點(diǎn)的地方，主要是在于String的處理上

reverse
因?yàn)閟tack的順序，在這個(gè)題中需要每次將每層里的內(nèi)容reverse。直接StringBuilder的reverse方法不可取：因?yàn)槭莚everse每一層。e.g. 3[ab]2[c]層直接從stack取出實(shí)際上是cc, ababab將這個(gè)reverse后應(yīng)該得到abababcc。這個(gè)時(shí)候考慮逆向stack，建立一個(gè)stack buffer，將stack pop出來的東西再reverse一個(gè)順序，逆逆得順

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

復(fù)制StringBuilder
add到底append幾次，怎么append：直接append add 是不可以的，因?yàn)閍dd是在變的，必須要先將第一個(gè)add保存起來，類似于dummy node，預(yù)先保存queue size這種“錨定”。

坑
小心一點(diǎn)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
    }
}

}
           
               
                                           
                       
                 
            
                     
             
               

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

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

               

                      
               
              
              

                
相關(guān)文章

                
    
                             
                                                                                                    
  • 
                                                
    
                          
    [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
                                    
                                    評(píng)論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    表達(dá)式類算法題小結(jié)
    
                                                     
    摘要：將表達(dá)式轉(zhuǎn)換為逆波蘭式，然后求值轉(zhuǎn)換中綴表達(dá)式為逆波蘭式魯棒性檢測(cè)，表達(dá)式中沒有操作數(shù)計(jì)算逆波蘭式值參考

表達(dá)式類算法題小結(jié)
[TOC]
聲明
文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處：[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/
表達(dá)式分類
根據(jù)運(yùn)算符與相關(guān)操作操作數(shù)的位置不同，將表達(dá)式分為前綴，中綴和后綴表...
    
                                                   
                          
    
                                
    
                                    Heier
                                    
                                    評(píng)論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    [LintCode] Topological Sorting [BFS & DFS]
    
                                                     
    摘要：當(dāng)隊(duì)列非空時(shí)，拿出最后放入的元素。若減后入度為，則這個(gè)結(jié)點(diǎn)遍歷完成，放入結(jié)果數(shù)組和隊(duì)列。遞歸函數(shù)去遍歷的，繼續(xù)在中標(biāo)記，使得所有點(diǎn)只遍歷一次。最深的點(diǎn)最先，根結(jié)點(diǎn)最后，加入結(jié)果數(shù)組的頭部處。

Problem
Given an directed graph, a topological order of the graph nodes is defined as follow:
For ...
    
                                                   
                          
    
                                
    
                                    draveness
                                    
                                    評(píng)論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    js 中二叉樹的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))
    
                                                     
    摘要：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等中序遍歷可以實(shí)現(xiàn)表達(dá)式樹，在編譯器底層很有用后序遍歷可以用來實(shí)現(xiàn)計(jì)算目錄內(nèi)的文件及其信息等。

樹的簡介
棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu)，都是順序數(shù)據(jù)結(jié)構(gòu)。而樹是非順序數(shù)據(jù)結(jié)構(gòu)。樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)...
    
                                                   
                          
    
                                
    
                                    Yuanf
                                    
                                    評(píng)論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    [LintCode] Evaluate Reverse Polish Notation
    
                                                     
    摘要：中的運(yùn)算符，運(yùn)算之后要出來，繼續(xù)遍歷數(shù)組。是放入新的數(shù)字，用轉(zhuǎn)換為均可。

Problem
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another ...
    
                                                   
                          
    
                                
    
                                    luckyyulin
                                    
                                    評(píng)論0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                           
                

              

              
               

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

                   
               

              

                

                  
0條評(píng)論
   
                
 
                      

              

           
           

              
 
                

                   
              
  

                  
最新活動(dòng)
 
           
                             
              





                                
              

           

        
       
    
    
     

      
    

    
    

    
       
       

         
閱讀需要支付1元查看
  
         
     
       

      
  
    
    








        

            

              
              
            

             
        

    








<