iT邦幫忙

2021 iThome 鐵人賽

DAY 2
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 2

【第二天 - Stack 介紹】

Q1. Stack 是什麼

  • 一種資料結構的概念,假設有一個容器是裝馬克杯的盒子 (這個盒子下面是封死的,無法拿東西)

    • 盒子
  • 現在第一步有小明、小美、小雅的馬克杯,依序被放入盒子中

    • 杯子放盒子
  • 課間小 Q&A: 你現在要從盒子中取出一個馬克杯,請問你會拿到誰的馬克杯 ?

  • ANS:盒子內的杯子排序預期是如下圖,所以你從盒子取,只能拿到最上面的杯子,也就是小雅的杯子

    • 杯子排列
  • 也就是說,這種 Stack 概念,最後放的杯子,會最先拿起來,最早放的杯子,會被墊在最下面,最後才能拿到,也就是「先進後出」「後進先出」的概念 ( 英文稱為 Last-In-First-Out )

Q2. 所以學會 Stack 概念可以做什麼 ?

  • 需要紀錄狀態,並且「先拿」「最後一個」狀態的時候,例如:
    • 瀏覽器的「回到上一頁」,他就跳到你上一步最後瀏覽的網頁
    • word 的 ctrl + Z 的復原鍵
    • 你要設計一隻會走迷宮的機器人,你希望他遇到分岔路,都能記錄狀態,當機器人走到死路,就回到上一次遇到的交叉路,最終就能找到出口
      • 迷宮圖

Lab. 明天要解的題目:20. Valid Parentheses

題目連結:https://leetcode.com/problems/valid-parentheses/
題目敘述:

  • 你需要判斷是不是正常括號表示方式

    • 例如 ( 就要用 ) 作為閉合,不能使用 } 跟 ]
  • 你需要判斷他是不是正常的方式閉合

    • 例如 ([)],這種閉合方式就會錯誤
  • 題目敘述

  • 測資的 Input/Output

    • 你會收到一個 s 變數的字串,s 會包含你要處理的字串
    • 最終你需要處理,s 字串是不是符合題目的規定,並回傳 True或False
  • I/O測資

  • 題目的條件

    • 變數 s 至少會有一個字元,最長為 10000
    • s 變數中只會出現有 ()[]{} 這樣的字元
      • 代表連空格都不會出現,所以你不能寫 ( ) [ ] { }
  • 題目限制

  • 看完題目,你要思考:

    • 如果 ([)] 是錯誤的,那什麼是正確的 ?
      • 你寫 ()[][()]([]) 是不是都可以 ?
    • 小學數學運算中,{}是大括號,[]是中括號,()是小括號,優先順序為小括號 > 中括號 > 大括號,那這一個題目,遇到 ([{}]) 這樣的情況,是不是也是可接受的 ?
  • 明天會分析該題 python 不同解法的優點,希望大家今天可以多先自己想一下這題 Stack 題如果是你,你的思考邏輯是什麼?


上一篇
【第一天 - Leetcode 介紹】
下一篇
【第三天 - Stack 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言