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

来源: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備份 [root@iZ2zeapnvuohe8p14289u6Z /]# mkdir -p /soft/zabbixback/zabbix-backup [root@iZ2zeapnvuohe8p14289u6Z /]# 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
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...