iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 14
2

直接來分享我的面試題目吧,此題目其實跟 LeetCode 20. Valid Parentheses 幾乎完全一樣。所以說真的要好好刷題才能找到工作啊!

Balanced Brackets

/**
 * A bracket is considered to be any one of the following characters:
 * ( )  { }  [ ]
 *
 * Two brackets are a matched pair if the opening bracket occurs to the left
 * of a closing bracket of the exact same type.
 *
 * A matching pair of brackets is not balanced if the enclosing set of brackets
 * are NOT matched.
 *
 * Implement a function called "" that returns a boolean value
 * indicating if the given string has all balanced brackets.
 *
 * Examples:
 * isBalanced("{[()]}") // true
 * isBalanced("{[(])}") // false
 */
console.log( isBalanced("{[()]}") );
console.log( isBalanced("{[(])}") );

function isBalanced(str){
   
}

Think

極限值/特殊狀況

再次強調問面試官問題真的很重要。這次經驗面試官也故意預先隱藏一些特殊狀況。我隨便問,他就把這些特殊狀況丟給我了

/**
 * Additional examples and edge cases:
 */
console.log( isBalanced("") ); // true
console.log( isBalanced("]") ); // false
console.log( isBalanced("{{[[(())]]}}") ); // true
console.log( isBalanced("[]{()()[[{}]]}") ); // true
console.log( isBalanced("a b [d] { (g) (h) i [-[ {;} ]-] }") ); // true
  • 符號沒有成對出現
  • 空值
  • 中間可能有除了 ( ) { } [ ] ,其他的符號

哪種資料結構解

  • 當初面試真的呆了,根本不知道有 Stack 這種資料結構。我還一直往 Regex 方向去,面試官說他還是第一次看到有人用 Regex 解 (其實根本方向錯了 T_T)

大概會怎麼解

現在了解了 Stack 的概念,發現題目真的沒有這麼難啊 !!!

  • 遇到 { [ ( 就放到 stack 裡

https://ithelp.ithome.com.tw/upload/images/20190915/20106426kdrz2eRE7m.jpg

  • 遇到 ) ] } 就去抓 stack 看有沒有相對應的 ( [ {
    • 若沒有就回傳 false
    • 若有就繼續檢查下一個

https://ithelp.ithome.com.tw/upload/images/20190915/20106426T9kh2lxbTV.jpg

用程式實踐

第一次的想法

function isBalanced(str){
  let listArr = str.split('')
  let current;
  let stack = [] //存 stack
  let stackIndex = 0;
  for(let i=0; i<listArr.length; i++){
    // console.log(stack)
    current = str[i]
	  // 若不是 Brackets 就不處理 
    if(current == '{' || current == '[' || current == '('){
      stack[stackIndex] = current; // 存到 stack
      stackIndex ++;
    }else if(current == '}' || current == ']' || current == ')'){
      // 遇到 Brackets 就要去找 stack top 有沒有相對應囉
			// 找到對應記得 pop 掉
      switch(current){
        case '}':
          if(stack[stack.length - 1] !== '{'){
            return false
          }
         
          break;
        case ']':
            if(stack[stack.length - 1] !== '['){
              return false
            }
          break;
        case ')':
            if(stack[stack.length - 1] !== '('){
              return false
            }
          break;
      }
      stack.pop()

    }
  }

以上不會過因為 stackIndex 一直在 +1 ,但後面又把值 pop 掉,所以有可能會出現 [undefined, "("] 之類狀況導致錯誤。另外還有一些部分可以改進

  • 不需要用 list.split('') 先做處裡,字串可以直接 for loop
  • 先 current == '}' || current == ']' || current == ')' 之後再判斷一次 是哪個符號很不必要
  • switch 效能其實是比 if 差的

改進程式

function isBalanced(str){
  let current, myStack = [];
  for(let i=0; i<str.length; i++){
    // 把 split 拿掉 string 本身就有 length 的屬性
    current = str[i]
    
    if(current === '{' || current === '[' || current === '('){
      // 直接用 array 原生 push 更簡潔
      myStack.push(current)
    }else if(current === '}'){
			// 就得判斷兩次重覆 所以拿掉剩判斷一次就好
      // pop 回傳移掉那個值, 然後會把 stack 最後面移掉
      if(myStack.pop() !== '{'){
        return false
      }
    }else if(current === ']'){
      if(myStack.pop() !== '['){
        return false
      }
    }else if(current === ')'){
      if(myStack.pop() !== '('){
        return false
      }
    }
  }
   return myStack.length === 0;  // [""] true
}

是不是簡潔很多呢,而且 Runtime faster than 82.86% 。所以在刷題以前要對資料結構跟語言本身相當了解才行 (例如,我若不知道 array.pop() 回傳的是被移掉那個值,我可能需要多好幾行程式碼去處理,處裡時同時又讓程式效能更差了 )

感嘆假如早一年準備說不定我已經在 Atlassian 上班了 (自以為可以XD)
明天要介紹得是 "先進先出" 的資料結構: 佇列 Queue

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

上一篇
堆疊 Stack
下一篇
佇列 Queue
系列文
前端工程師用 javaScript 學演算法32
1
alantsui
iT邦新手 5 級 ‧ 2019-09-15 11:40:01

哈,這題在上個SEM資料結構課的時候學過

hannahpun iT邦新手 5 級 ‧ 2019-09-15 13:08:40 檢舉

我對 SEM 黑人問號啊(非本科系哭哭)

alantsui iT邦新手 5 級 ‧ 2019-09-15 20:36:57 檢舉

SEM是semester(學期)的意思,不是術語

0
愷開
iT邦新手 5 級 ‧ 2019-09-16 09:34:13

稍微簡化了一下寫法,不過效能怎樣就不知道了。

function isBalanced(str) {
  const leftBrackets = ['{', '[', '('];
  const stack = [];
  const pairs = {
    '{': '}',
    '[': ']',
    '(': ')',
  };

  let current = '';
  for (let i = 0; i < str.length; i++) {
    current = str[i];
    if (leftBrackets.includes(current)) {
      stack.push(current);
    } else if (Object.values(pairs).includes(current)) {
      return current === pairs[stack.pop()];
    }
  }
  return stack.length === 0;
}
hannahpun iT邦新手 5 級 ‧ 2019-09-16 11:54:53 檢舉

這樣似乎找到第一次符合就會失敗了
例如 "[()" 應該要是 false 但這樣寫會傳 true
不過我沒想過用 pairs,的確是簡潔很多

0
rainbowrain
iT邦新手 4 級 ‧ 2020-02-21 15:52:57

runtime beats 96.01%

var isValid2 = function(s) {
    var stack = []
    var leftPair = {'(':0, '[':1,'{':2}
    var rightPair = {')':0, ']':1,'}':2}

    for(let i=0; i<s.length; i++){
      w = s[i]
      if (leftPair[w] >= 0){ // 遇到 (,[,{ 直接放進 stack
          stack.push(w)
      }
      else if (rightPair[w] >= 0){ // 遇到 ),],} 時要做一些檢查
      
        // 遇到 ),],} 時 stack 是空的就 false
        if (stack.length === 0) return false 
        
        // 檢查 stack 中的 top 跟進來的符號有沒有成對
        if (leftPair[stack[stack.length -1]] === rightPair[w]){
            stack.pop() // 符號有成對就 pop 出去
        }else{
            return false // 不成對就 false
        }
      }
    }
    // 全部檢查完 stack 還有剩就是 false, 清空就是 true
    return stack.length === 0;
};

我要留言

立即登入留言