前端程式員學好演算法系列(五)棧和隊列

来源:https://www.cnblogs.com/kbnet/archive/2020/07/26/13382860.html
-Advertisement-
Play Games

1.棧的基礎使用,js中數組直接可以作為棧使用,棧遵循先進後出的原則,即js可以使用push()和pop() 比較容易的實現一個棧 20. 有效的括弧給定一個只包括 '(',')','{','}','[',']' 的字元串,判斷字元串是否有效。 有效字元串需滿足: 左括弧必須用相同類型的右括弧閉合。 ...


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
};

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1. ZABBIX備份 [[email protected] /]# mkdir -p /soft/zabbixback/zabbix-backup [[email protected] /]# cp /etc/zabbix/zabbix_server.c ...
  • 恩智浦半導體於2017年開始推出的i.MX RT系列重新定義了MCU,其第一款晶元i.MX RT1052,主頻高達600MHz,直接引爆眾多MCU開發者的神經。如今i.MX RT發佈已近三年,陸續推出了9款型號,細心的你會發生其實際上已經衍生為兩大陣營,分別是CM7內核的i.MX RT1xxx系列(... ...
  • 人這一輩子,真的是非常不容易:讀書時,被老師、同學嘲笑,工作時,被老闆、同事嘲笑,就連出去擼個串兒,還可能被朋友嘲笑…… 這些也就算了,畢竟大家還都是同類,都是活生生的人。但是,你如果被 Linux 終端給嘲笑了,你的內心會是什麼感受? 今天要介紹的,是一個非常有趣的 CLI 工具,這個工具可以實現 ...
  • 1.在linux系統下安裝跨系統傳輸文件工具 root用戶下 根目錄輸入 yum -y install lrzsz 2.把apache-jmeter-4.0zip包 用rz命令上傳到linux系統的根目錄下 解壓 3.配置jmeter環境變數 vim /etc/profile 添加 export P ...
  • 西北望鄉何處是,東南見月幾回圓。 月亮又慢悠悠的掛上了天空,趁著睡前夢囈,我就帶領各位可愛的讀者們探索MySql最後的子查詢部分。 說明:有些查詢結果出來結果截圖與題目要求不一樣會出現多餘的欄位是為了方便展示結果的可讀性。實際操作的讀者可以刪除SELECT後面多餘的欄位得到正確的結果。 #WHERE ...
  • Redis是什麼?redis是一款基於BSD協議,開源的非關係型資料庫(nosql資料庫),作者是義大利開發者Salvatore Sanfilippo在2009年發佈,使用C語言編寫;redis是基於記憶體存儲,而且是目前比較流行的鍵值資料庫(key-value database),它提供將記憶體通過... ...
  • MariaDB 資料庫管理系統是 MySQL 的一個分支,主要由開源社區在維護,採用 GPL 授權許可。開發這個分支的原因之一是:甲骨文公司收購了 MySQL 後,有將 MySQL 閉源的潛在風險,因此社區採用分支的方式來避開這個風險。MariaDB完全相容mysql,使用方法也是一樣的。 系統環境 ...
  • 參考:https://juejin.im/entry/58b93af3ac502e006c0820c9 1.常見的加密方式:Base64、MD5、AES、EDS、RSA HTTPS 以及SSL/TSL 什麼是SSL?SSL(Secure Sockets Layer, 安全套接字層),因為原先互聯網上 ...
一周排行
    -Advertisement-
    Play Games
  • 簡介 本文的初衷是希望幫助那些有其它平臺視覺演算法開發經驗的人能快速轉入Halcon平臺下,通過文中的示例開發者能快速瞭解一個Halcon項目開發的基本步驟,讓開發者能把精力完全集中到演算法的開發上面。 首先,你需要安裝Halcon,HALCON 18.11.0.1的安裝包會放在文章末尾。安裝包分開發和 ...
  • 本文是對Datawhale的動手學數據分析課程的學習總結,記錄了整體的學習過程、答案以及個人感想,代碼較為詳細。 ...
  • JZ7重建二叉樹 描述 給定節點數為 n 的二叉樹的前序遍歷和中序遍歷結果,請重建出該二叉樹並返回它的頭結點。 例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6} 提示: 1.vin.length == pre.length 2.pre 和 vin ...
  • 我們都知道在Java編程中多線程的同步使用synchronized關鍵字來標識,那麼這個關鍵字在JVM底層到底是如何實現的呢。 我們先來思考一下如果我們自己實現的一個鎖該怎麼做呢: 首先肯定要有個標記記錄對象是否已經上鎖,執行同步代碼之前判斷這個標誌,如果對象已經上鎖線程就阻塞等待鎖的釋放。 其次要 ...
  • 目錄 一.OpenGL 色階 1.Windows OpenGL ES 版本 2.Windows OpenGL 版本 二.OpenGL 色階 GLSL Shader 三.猜你喜歡 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> OpenGL ES 基礎 零基礎 Ope ...
  • 1. 查看Linux伺服器版本信息 # cat /etc/redhat-release CentOS Linux release 7.4.1708 (Core) 2. 禪道開源版安裝包下載 wget http://dl.cnezsoft.com/zentao/9.8.2/ZenTaoPMS.9.8. ...
  • Spring 框架可以為 Java 應用程式開發提供全面的基礎設施支持,它是現在非常流行的 Java 開源框架,對於一個 Java 開發人員來說,熟練掌握 Spring 是必不可少的。 ...
  • 前言 本篇是c++總結的第二篇,關於c++的對象模型,在構造、拷貝虛函數上重點分析,也包含了c++11class的新用法和特性,如有不當,還請指教! c++三大特性 訪問許可權 ​ 在c++中通過public、protected、private三個關鍵字來控製成員變數和成員函數的訪問許可權,它們分別表示 ...
  • 一.小結 1.使用二維數組來存儲表格 2.可以使用以下語法來聲明二維數組變數: 元素類型[ ] [ ]數組變數 3.可以使用以下語法來創建二維數組變數: new 元素類型 [行的個數][列的個數] 4.使用下麵的語法表示二維數組中的每個元素: 數組變數[行下標][列的個數] 5.可使用數組初始化語法 ...
  • typimg是一款為typora編輯器提供圖像自定義上傳服務的工具,該工具將在typora中輸入的網路圖片、本地圖片、剪貼板圖片/截圖上傳到博客園,支持在MacOS、Windiws、Linux三個平臺上運行。 ...