I am Mike
Published in

I am Mike

JavaScript 的 Leetcode 演算之路(一)

演算法對一個工程師來說是一個非常重要的技能,先撇開在工作上面的實務影響不管,光在求職的過程中,就有許多面試需要考試,而考的內容八九不離十是演算法考題,所以對於一個厲害的工程師來說,演算法尤其的重要,偏偏我的數學跟資料結構沒有這麼厲害,所以我也需要花點苦工來好好的學習,接下來我就會透過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: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true

簡單來講就是給你一串都是括號所組成的字串,你要判斷小括號、中括號、大括號是不是成對的,只要是字串內的括號都是成對的就回傳 true,如果有一個不是成對的就回傳 false,看看題目提供的 example 真是簡單明瞭XD

以下是 leetcode 幫我們準備好空白的 function

/**
* @param {string} str
* @return {boolean}
*/
const isValid = function(str) {
};

接下來讓我們來思考解題的思路

  1. 首先需要對字串去跑一個迴圈,遍歷每個字元出來。
  2. 在來我們需要先比對 " { "、" [ "、" ( " 這幾個開頭的括號。
  3. 把開頭括號先存進一個暫存的 Array 裡面。
  4. 當遇到 " } "、" ] "、" ) " 結尾括號的時候就先去把剛剛暫存的 Array 最後的那個括號取出來然後比較。
  5. 比較一錯就直接回傳 false,如果對了就繼續比較下去。
  6. 最後暫存 Array 長度為零的時候,就代表全部比較都成功,回傳 true。

比照上面的思考邏輯,以下是我的完成 code

送出後成功的解題!!!

這邊我用了一個 map object 去記錄括號的對應,當遇到結尾括號的時候就可以透過 Array.pop() 去比對這個 map object。

這時候問題來了,還能不能再優化 ?

魔鬼藏在細節裡,我們看這邊

if(arr.pop() !== map[item]){
return false;
}

這邊在做「比較」的時候,是用 String 來做判斷的,如果改成用 Number 來判斷的話,速度就會快一點,所以我們要來小小修改一下剛剛的程式。

整個速度就提升了不少~

好啦! 這次的解題就到這邊啦,接下來我會慢慢的分享一些關於其他題目的解題技巧,如果有更好的寫法請在下面留言給我知道,感謝。

這邊有我之前解其他題目的直播影片,有興趣的朋友也可以看一下。

最後

我有開設一個youtube的頻道,每個月不定時週六或日晚上直播跟技術或是經驗相關的分享,有興趣的朋友歡迎追蹤訂閱+小鈴鐺。

--

--

--

解決不了問題 就解決提出問題的人

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Mike

Mike

如果有一行code無法解決的bug,那就寫兩行!

More from Medium

Javascript Testing In a Nutshell

TypeScript vs JavaScript: What’s the Difference?

Mastering Asynchronous JavaScript

Lesser-known JavaScript features — Part 2