Skip to main content

栈

用栈实现队列​

题号232. 用栈实现队列

思考

  1. 栈的特性是先入后出，队列的特性是先入先出
  2. 使用两个栈就能实现，一个入一个出，每当遇到要出的时候如果出栈为空就把入栈倒过去，否则就先清空出栈
方法一​
class MyQueue {
    private in
    private out
    constructor() {
        this.in =[]
        this.out = []
    }

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

    pop(): number {
        if(!this.out.length){
            while(this.in.length){
                this.out.push(this.in.pop())
            }
        }
        return this.out.pop()
    }

    peek(): number {
        if(!this.out.length){
            while(this.in.length){
                this.out.push(this.in.pop())
            }
        }
        return this.out[this.out.length-1]
    }

    empty(): boolean {
        return !this.out.length&&!this.in.length
   }
}

/**
 * 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()
 */

用队列实现栈​

题号225. 用队列实现栈

思考

  1. 用队列实现栈其实思路和用栈模拟队列不太一样
  2. 用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用思路是这个
方法一​
class MyStack {
    private queue
    private _queue
    constructor() {
        this.queue = []
        this._queue = []
    }

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

    pop(): number {
        while(this.queue.length > 1){
                this._queue.push(this.queue.shift());
            }
            let ans = this.queue.shift();
            while(this._queue.length){
                this.queue.push(this._queue.shift());
            }
            return ans;
    }

    top(): number {
        return this.queue.slice(-1)[0];
    }

    empty(): boolean {
        return !this.queue.length;
    }
}

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

有效的括号​

题号20. 有效的括号

思考

  1. 类似这种左右对应且要求顺序的题目都可以试试用栈来解决
  2. push到栈里面的可以是对应的，而不是原元素，这样比较更方便
方法一​
function isValid(s: string): boolean {
    let stack = []
    if(s.length%2!==0)return false //如果不是偶数的话肯定无法自洽
    for(let i of s){
    if(i==='('){stack.push(')')}
    else if(i==='['){stack.push(']')}
    else if(i==='{'){ stack.push('}')} // 前三个都是判断左括号
    else if(i===stack[stack.length-1]){stack.pop()} // 如果是右括号就比较
    else{return false}}
    return stack.length===0
};

删除字符串中的所有相邻重复项​

题号1047. 删除字符串中的所有相邻重复项

思考

  1. 第一反应是用双指针，没写出来（后面看了别人的思路，很有意思）
    1. 连连看一样，每次先把fast指针的值赋给slow指针，这个时候slow还没变更，如果slow的值和slow-1的值相等就删除这两个值，也就是slow回退，fast前进
  2. 栈
方法一 栈​
function removeDuplicates(s: string): string {
    let stack = []
    for(let i of s){
        if(stack.length===0||i!==stack[stack.length-1])stack.push(i)
        else stack.pop()
    }
    return stack.join('')
};
方法二 双指针​
function removeDuplicates(s: string): string {
   let arr = [...s],fast=0,slow=0
   while(fast<s.length){
       arr[slow] = arr[fast]  // 直接用fast指针覆盖slow指针的值
       if(slow>0&&arr[slow]===arr[slow-1])slow-- // 遇到前后相同值的就跳过，即slow指针后退一步，下次循环就直接被覆盖掉了
       else slow++
       fast++
   }
   arr.length = slow
   return arr.join('')
};

逆波兰表达式求值​

题号逆波兰表达式求值

思考

  1. 题目其实不是很难
  2. 重点在于能否理解要做什么
  3. 这道题目就是使用栈来保存
方法一​
function evalRPN(tokens: string[]): number {
    let helperStack: number[] = [];
    let temp: number;
    let i: number = 0;
    while (i < tokens.length) {
        let t: string = tokens[i];
        switch (t) {
            case '+':
                temp = helperStack.pop()! + helperStack.pop()!;
                helperStack.push(temp);
                break;
            case '-':
                temp = helperStack.pop()!;
                temp = helperStack.pop()! - temp;
                helperStack.push(temp);
                break;
            case '*':
                temp = helperStack.pop()! * helperStack.pop()!;
                helperStack.push(temp);
                break;
            case '/':
                temp = helperStack.pop()!;
                temp = Math.trunc(helperStack.pop()! / temp);
                helperStack.push(temp);
                break;
            default:
                helperStack.push(Number(t));
                break;
        }
        i++;
    }
    return helperStack.pop()!;
};

滑动窗口最大值​

题号239. 滑动窗口最大值

思考

  1. 这道题目使用单调队列来解决，自己写一个单调队列。核心在于永远保持队列头是最大的元素
function maxSlidingWindow(nums: number[], k: number): number[] {
    /** 单调递减队列 */
    class MonoQueue {
        private queue: number[];
        constructor() {
            this.queue = [];
        };
        /** 入队：value如果大于队尾元素，则将队尾元素删除，直至队尾元素大于value，或者队列为空 */
        public enqueue(value: number): void {
            let back: number | undefined = this.queue[this.queue.length - 1];
            while (back !== undefined && back < value) {
                this.queue.pop();
                back = this.queue[this.queue.length - 1];
            }
            this.queue.push(value);
        };
        /** 出队：只有当队头元素等于value，才出队 */
        public dequeue(value: number): void {
            let top: number | undefined = this.top();
            if (top !== undefined && top === value) {
                this.queue.shift();
            }
        }
        public top(): number | undefined {
            return this.queue[0];
        }
    }
    const helperQueue: MonoQueue = new MonoQueue();
    let i: number = 0,
        j: number = 0;
    let resArr: number[] = [];
    while (j < k) {
        helperQueue.enqueue(nums[j++]);
    }
    resArr.push(helperQueue.top()!);
    while (j < nums.length) {
        helperQueue.enqueue(nums[j]);
        helperQueue.dequeue(nums[i]);
        resArr.push(helperQueue.top()!);
        j++, i++;
    }
    return resArr;
};

前 K 个高频元素​

题号前 K 个高频元素

思考

  1. 使用Map然后最后排序
  2. 小顶堆
方法一 Map​
function topKFrequent(nums: number[], k: number): number[] {
    const countMap: Map<number, number> = new Map();
    for (let num of nums) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    // tS没有最小堆的数据结构，所以直接对整个数组进行排序，取前k个元素
    return [...countMap.entries()]
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(i => i[0]);
};