2021 年 08 月 08 日

这是我参与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):最先插入的元素最先出来。

p1


© 2021, 滇ICP备19003866号本网站版权归本站作者Ruoduan所有原创文章遵循CC BY-SA 4.0授权许可,转载请注明出处