经典150题 - 栈

20. 有效的括号

var isValid = function(s) {
    const map = new Map()
    map.set('(',')')
    map.set('[',']')
    map.set('{','}')
    const res = []
    for(let char of s) {
        if(map.has(char)) {
            res.push(char)
        } else if(char === map.get(res[res.length - 1])) {
            res.pop()
        } else {
            return false
        }
    }
    return res.length === 0
};

71. 简化路径

var simplifyPath = function(path) {
    let stack = path.split('/')
    let res = []
    for(let p of stack) {
        if(p === '..') {
            res.pop()
        } else if( p && p !== '.') {
            res.push(p)
        }
    }
    return '/'+res.join('/')
};

155. 最小栈

var MinStack = function() {
    this.stack = []
    this.MinStack = []
};
 
/** 
 * @param {number} value
 * @return {void}
 */
MinStack.prototype.push = function(value) {
    this.stack.push(value)
    let min = this.getMin()
    this.MinStack.push(min < value ? min : value)
};
 
/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.MinStack.pop()
    this.stack.pop()
};
 
/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};
 
/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.MinStack[this.MinStack.length - 1]
};

150. 逆波兰表达式求值

var evalRPN = function (tokens) {
    const stack = []
    const ops = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => ~~(a / b)  // 向零取整
    }
 
    for (const t of tokens) {
        if (t in ops) {
            const b = stack.pop()
            const a = stack.pop()
            stack.push(ops[t](a, b))
        } else {
            stack.push(Number(t))
        }
    }
 
    return stack[0]
};

224. 基本计算器

var calculate = function(s) {
    let result = 0
    let num = 0
    let sign = 1
    const stack = []
    
    for (const c of s) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + Number(c)
        } else if (c === '+' || c === '-') {
            result += sign * num
            num = 0
            sign = c === '+' ? 1 : -1
        } else if (c === '(') {
            stack.push(result)
            stack.push(sign)
            result = 0
            sign = 1
        } else if (c === ')') {
            result += sign * num
            num = 0
            result *= stack.pop()  // sign
            result += stack.pop()  // prev result
        }
    }
    
    return result + sign * num
}

相关笔记

• 栈与队列
• 回溯算法
• GRD 栈刷题