演算法對一個工程師來說是一個非常重要的技能,先撇開在工作上面的實務影響不管,光在求職的過程中,就有許多面試需要考試,而考的內容八九不離十是演算法考題,所以對於一個厲害的工程師來說,演算法尤其的重要,偏偏我的數學跟資料結構沒有這麼厲害,所以我也需要花點苦工來好好的學習,接下來我就會透過leetcode這個演算法考題的網站,學習演算法,把我寫好的題目來分享給大家,可以一起討論。
這次要解的題目是這個 20. Valid Parentheses(Easy)
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.An input string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order.Note that an empty string is also considered valid.Example 1: Input: "()" Output: trueExample 2: Input: "()[]{}" Output: trueExample 3: Input: "(]" Output: falseExample 4: Input: "([)]" Output: falseExample 5: Input: "{[]}" Output: true
簡單來講就是給你一串都是括號所組成的字串,你要判斷小括號、中括號、大括號是不是成對的,只要是字串內的括號都是成對的就回傳 true,如果有一個不是成對的就回傳 false,看看題目提供的 example 真是簡單明瞭XD
以下是 leetcode 幫我們準備好空白的 function
/** * @param {string} str * @return {boolean} */ const isValid = function(str) {};
接下來讓我們來思考解題的思路
- 首先需要對字串去跑一個迴圈,遍歷每個字元出來。
- 在來我們需要先比對 ” { “、” [ “、” ( ” 這幾個開頭的括號。
- 把開頭括號先存進一個暫存的 Array 裡面。
- 當遇到 ” } “、” ] “、” ) ” 結尾括號的時候就先去把剛剛暫存的 Array 最後的那個括號取出來然後比較。
- 比較一錯就直接回傳 false,如果對了就繼續比較下去。
- 最後暫存 Array 長度為零的時候,就代表全部比較都成功,回傳 true。
比照上面的思考邏輯,以下是我的完成 code
(此區域有程式碼無法顯示,請點按下方連結回到原文查看,不好意思。)
這邊我用了一個 map object 去記錄括號的對應,當遇到結尾括號的時候就可以透過 Array.pop() 去比對這個 map object。
這時候問題來了,還能不能再優化 ?
魔鬼藏在細節裡,我們看這邊
if(arr.pop() !== map){
return false;
}
這邊在做「比較」的時候,是用 String 來做判斷的,如果改成用 Number 來判斷的話,速度就會快一點,所以我們要來小小修改一下剛剛的程式。
(此區域有程式碼無法顯示,請點按下方連結回到原文查看,不好意思。)
![](https://miro.medium.com/max/1332/1*kgiwuVjBZnp_aS0OTuaI8g.jpeg)
整個速度就提升了不少~
好啦! 這次的解題就到這邊啦,接下來我會慢慢的分享一些關於其他題目的解題技巧,如果有更好的寫法請在下面留言給我知道,感謝。
這邊有我之前解其他題目的直播影片,有興趣的朋友也可以看一下。
最後
原文作者有開設一個youtube的頻道,每個月不定時週六或日晚上直播跟技術或是經驗相關的分享,有興趣的朋友歡迎追蹤訂閱+小鈴鐺。
好文轉自作者Mike–Javascript的Leetcode演算之路(一)
如果你喜歡他的文章,歡迎回到他的Medium看更多: )
希望能夠藉由這篇文章幫助到你。如果想要對JS本身有更多的瞭解,Udemy這裡開課囉!老師從基礎手把手的帶你,教你主流寫法提升 JS 開發能力!
如果你的入門還在單打獨鬥,歡迎來到快樂學程式找到志同道合的夥伴,你的自學之路不孤單。