前端程式員學好演算法系列（五）堆疊

1.堆疊的基礎使用，js中陣列直接可以作為堆疊使用，堆疊遵循先進后出的原則，即js可以使用push()和pop() 比較容易的實作一個堆疊

20. 有效的括號
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串，判斷字串是否有效，

有效字串需滿足：

左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，

示例 1:
輸入: "()"
輸出: true


示例 2:
輸入: "()[]{}"
輸出: true

解題：

1.我們定義obj 對應括號的另一半
2.我們定義一個堆疊stack
3.回圈字串當字串為前括號時入堆疊

4.當s[i] 為后括號時我們先判斷stack.length是否為0，為0回傳false ，不為0我們取出堆疊頂的元素，借用obj進行比較不相等是回傳false
5.當遍歷結束后，如果stack.length為0時說明可以匹配

var isValid = function(s) {
    let obj = {'{':'}','[':']','(':')'}
    let stack = []
    for(let i = 0;i<s.length;i++){
        if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
            stack.push(s.charAt(i))
        } else {
            if(stack.length>0){
              let c = stack.pop()
              if(obj[c]!==s[i]){
                return false
              }
            }else{
                return false
            }  
        }
    }
    if(stack.length==0){
        return true
    } else {
        return false
    }
};

71. 簡化路徑
以 Unix 風格給出一個檔案的絕對路徑，你需要簡化它，或者換句話說，將其轉換為規范路徑，

在 Unix 風格的檔案系統中，一個點（.）表示當前目錄本身；此外，兩個點 （..） 表示將目錄切換到上一級（指向父目錄）；兩者都可以是復雜相對路徑的組成部分，更多資訊請參閱：Linux / Unix中的絕對路徑 vs 相對路徑

請注意，回傳的規范路徑必須始終以斜杠 / 開頭，并且兩個目錄名之間必須只有一個斜杠 /，最后一個目錄名（如果存在）不能以 / 結尾，此外，規范路徑必須是表示絕對路徑的最短字串，
示例 1：

輸入："/home/"
輸出："/home"

解釋：注意，最后一個目錄名后面沒有斜杠，
示例 2：

輸入："/../"
輸出："/"
解釋：從根目錄向上一級是不可行的，因為根是你可以到達的最高級，

解題：
1.我們用/ 把路徑拆分為陣列并去除空值
2.token[i] 為..時我們洗掉結尾的元素
3.token[i] 為.是不做處理 否則加入堆疊
4.回傳元素

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
      const stack = []
      let token = path.split('/').filter(a=>a)
      for(let i=0;i<token.length;i++){
           if(token[i]=='..'){
             stack.pop()
           } else if(token[i]=='.'){
           } else {
             stack.push(token[i])
           }
      }
      return '/'+stack.join('/')
};

145. 二叉樹的后序遍歷
給定一個二叉樹，回傳它的 后序 遍歷，

示例:

輸入: [1,null,2,3] 
1
\
2
/
3

輸出: [3,2,1]

解題一：

系統的遞回本身就是由堆疊實作的，我們先用遞回的方式求下解：
1.root為null時直接回傳null
2.定義儲存陣列的值result, 我們在pushRoot中遞回呼叫root.left 和root.right  在push node.val 的值，
3.回傳result

var postorderTraversal = function(root) {   
    var result = [];
    function pushRoot(node){
        if(node != null){
            if(node.left != null){
                pushRoot(node.left);
            }
            if(node.right != null){
                pushRoot(node.right);
            } 
            result.push(node.val);
        }
    }
    pushRoot(root);
    return result;
            
};

解題二.
1.root為null時直接回傳null

2.我們定義一個堆疊popo 里面默認存放node為root type為1為儲存的節點物件 type為2時代表存盤的節點值

3.如果堆疊中存在值 我們就取最尾部的值，如果該值存在left和right節點我們就取出來存入堆疊中
4.重點：我們后序遍歷的遍歷順序為 left right 取值val 入堆疊的順序就為 val right left 這一部分順后我在詳細說明下，

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    
    let res = []   
    if(root==null){
      return []
    }
    let popo = [{type:1,node:root}]
    while(popo.length){
        const { type, node }= popo.pop()
        if(type==2){
           res.push(node)
        } else {
            popo.push({type:2,node:node.val})
            if(node.right){
              popo.push({type:1,node:node.right})
            }
            if(node.left){
              popo.push({type:1,node:node.left})
            }
        }
    }
    return res
};

標籤：JavaScript

上一篇：前端程式員學好演算法系列（四）鏈表

下一篇：JS的時間格式化和時間戳轉換函式