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

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

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

 


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

更多相關文章
  • 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, 安全套接字層),因為原先互聯網上 ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...