Leetcode 20有效的括号疑惑(采用3个栈)

来源:1-5 大厂面试为什么总考算法?

甲骨文_0001

2022-10-14

老师,第20道题目今天我是面试到了,然后我用了3个栈, 分别存放"(", “[”, “{”, 但是碰到 "([)]"这个用例就挂了,
然后我到您github上看了答案,是只用了一个栈就够了,我也看明白了。呃,在面试中,我自己直观的方式是想用3个栈,如果是3个栈,可以做吗,哈哈哈。
图片描述

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack_0 = [];  // (
    let stack_1 = []; // [
    let stack_2 = []; // {

    for( let i = 0; i < s.length; i ++ ){
        let nowChar = s.charAt(i);
        if( nowChar == '(' ){
            stack_0.push(nowChar);
        }else if( nowChar == '[' ){
            stack_1.push(nowChar);
        }else if( nowChar == '{' ){
            stack_2.push(nowChar);
        }

        if( nowChar == ')' ){
            if( stack_0.length == 0 ){
                return false;
            }
            stack_0.pop();
        }else if( nowChar == ']' ){
            if( stack_1.length == 0 ){
                return false;
            }
            stack_1.pop();
        }else if( nowChar == '}' ){
            if( stack_2.length == 0 ){
                return false;
            }
            stack_2.pop();
        }

    } // for i

    if( stack_0.length > 0 || stack_1.length > 0 || stack_2.length > 0 ){
        return false;
    }
    return true;
};
写回答

1回答

liuyubobobo

2022-10-15

很多时候沿着一个错误的思路去想怎么用错误的思路“绕弯”得到正确的结果并没有必要。尤其是这个错误的思路并没有什么优势的时候(如果对于这个问题,经典的解法是使用三个栈,我们讨论一下使用一个栈是否有可能解决,如果不可能,为什么,会更有意义。)


关键是想明白:

1)错误的思路到底哪里错了?

2)正确的思路是怎么避免这种错误的。


继续加油!:)


0
1
甲骨文_0001
嗯嗯,我就不纠结了,当时时间仓促,脑子里直观想到了栈,然后就是3个类型的栈,现在想明白了,1个栈就能搞定的事情: )
2022-10-15
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程