Ruoduan' Blog

这是我参与8月更文挑战的第8天，活动详情查看：8月更文挑战

本文题目全部来自 LeetCode

使用 Typescript

本篇文章全部收藏于专栏 3周攻克数据结构-LeetCode

本文所有代码和解题步骤将放置 GitHub仓库

DAY9

1. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()" 输出：true 示例 2：

输入：s = "()[]{}" 输出：true 示例 3：

输入：s = "(]" 输出：false 示例 4：

输入：s = "([)]" 输出：false 示例 5：

输入：s = "{[]}" 输出：true

方法1：栈匹配法

栈的特性：先进先出

1. 建立一个括号的映射: 括号左边 => 匹配右边
2. 遍历判断左边进栈
3. 判断右边 取栈- 判断是否匹配

function isValid(s: string): boolean {
   // 奇数直接 返回 false
   if (s.length % 2 !== 0) return false

   // 新建一个栈
   const stack = []
   // 映射 三个括号
   const map = {
       '(':')',
       '[':']',
       '{':'}',
   }

   for (let str of s) {
       // 是左括号的话 就进栈 判断
       if ( str in map ){
           stack.push(str)
           continue;
       }
       // 右括号的话，判断栈的最后一个是否匹配【完整的括号】
       if (map[stack.pop()] !== str) return false
   }

   return !stack.length
};

2. 用栈实现队列

你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：

输入：


["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
​
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false


提示：

1 <= x <= 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作

方法1：双栈实现

class MyQueue {
    // 进栈
    public stack: number[] = []
    // 出栈
    public stackOut: number[] = []

    // 吧进栈数据倒入到出栈
    inOut (): void {
        while (this.stack.length) {
            this.stackOut.push(this.stack.pop());
        }
    }

    push(x: number): void {
        this.stack.push(x)
    }

    pop(): number {
        if (!this.stackOut.length) {
            this.inOut();
        }
        return this.stackOut.pop();
    }

    peek(): number {
        if (!this.stackOut.length) {
            this.inOut();
        }
        return this.stackOut[this.stackOut.length - 1];
    }

    empty(): boolean {
        return this.stackOut.length === 0 && this.stack.length === 0;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

科普篇

图片均来自网络

栈：后进先出（LIFO-last in first out）:最后插入的元素最先出来。

队列：先进先出（FIFO-first in first out）:最先插入的元素最先出来。