• 【JavaScript数据结构与算法】一、栈及leetcode实战


    栈是一种遵从后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

    栈数据结构

    我们需要一种数据结构来保存栈里的元素。可以选择数组。数组允许我们在任何位置添加或删除元素。由于栈遵循 LIFO 原则,需要对元素的插入和删除功能进行限制。下面基本使用js实现一些栈的方法:

    • push(element(s)):添加一个(或几个)新元素到栈顶。
    • pop():移除栈顶的元素,同时返回被移除的元素。
    • peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)。
    • isEmpty():如果栈里没有任何元素就返回true,否则返回false。
    • clear():移除栈里的所有元素。
    • size():返回栈里的元素个数。该方法和数组的length属性很类似
    class Stack{
        constructor(){
            this.items = []
        }
        push(ele){
            this.items.push(ele)
        }
        pop(){
            return this.items.pop()
        }
        peek(){
            return this.items[this.items.length-1]
        }
        isEmpty(){
            return this.items.length===0
        }
        size(){
            return this.items.length
        }
        clear(){
            this.items=[]
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    到这,我们基本对栈的数据结构及其方法都有了比较清晰的认识,下面直接进行实现联系吧。

    leetcode应用

    1、 20. 有效的括号 (easy)

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

    有效字符串需满足:

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

    提示:

    1 <= s.length <= 104
    s 仅由括号 ‘()[]{}’ 组成

    • 思路:首先如果字符串能组成有效的括号,则长度一定是偶数,我们可以遍历字符串,遇到左括号则暂存,期待后面有右括号可以和它匹配,如果遇到右括号则检查是否能和最晚暂存的做括号匹配。这就和栈这种数据结构先进后出的特性相吻合了。所以我们可以准备一个栈存放括号对,遍历字符串的时候,如果遇到左括号入栈,遇到右括号则判断右括号是否能和栈顶元素匹配,在循环结束的时候还要判断栈是否为空,如果不为空,则不是有效括号匹配的字符串
    • 复杂度分析:
      • 时间复杂度:O(n),其中 nn是字符串 s 的长度。
      • 空间复杂度:O(n + ∣Σ∣),其中 Σ 表示字符集,本题中字符串只包含 6 种括号,∣Σ∣=6。栈中的字符数量为 O(n),而哈希表使用的空间为 O(∣Σ∣),相加即可得到总空间复杂度
    var isValid = function(s) {
        const n = s.length;
        if (n % 2 === 1) {//如果字符串能组成有效的括号,则长度一定是偶数
            return false;
        }
        const pairs = new Map([//用栈存储括号对
            [')', '('],
            [']', '['],
            ['}', '{']
        ]);
        const stk = [];
        for (let ch of s){//循环字符串
            if (pairs.has(ch)) {
              	//遇到右括号则判断右括号是否能和栈顶元素匹配
                if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
                    return false;
                }
                stk.pop();
            } else {
                stk.push(ch);//如果遇到左括号入栈
            }
        };
        return !stk.length;//循环结束的时候还要判断栈是否为空
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    2、 232. 用栈实现队列 (easy)

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

    实现 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(双端队列)来模拟一个栈,只要是标准的栈操作即可。
    • 思路:用栈模拟队列,不涉及到具体算法,主要考察栈和队列的掌握程度。使用先进后出的栈来模拟先进先出的队列的,一个栈来模拟肯定不能满足需要,所以这里使用两个栈:一个输入栈,一个输出栈

      • 在push数据时,数据仅存入输入栈;
      • pop时候,若输出栈为空,则就把进栈数据全部导入进来(注意是全部导入),再从出栈弹出数据,如果输出栈不为空,则直接从出栈弹出数据就可以了。最后如果进栈和出栈都为空的话,说明模拟的队列为空了。
    • 复杂度分析:

      • 时间复杂度:push 和 empty 为 O(1),pop 和peek 为均摊 O(1)。对于每个元素,至多入栈和出栈各两次,故均摊复杂度为O(1)。
      • 空间复杂度:O(n)。其中 n 是操作总数。对于有 n 次push 操作的情况,队列中会有 n 个元素,故空间复杂度为 O(n)。
    var MyQueue = function () {
        //准备两个栈
        this.stackIn = [];
        this.stackOut = [];
    };
    
    /** 
     * @param {number} x
     * @return {void}
     */
    MyQueue.prototype.push = function (x) {
        this.stackIn.push(x);
    };
    
    /**
     * @return {number}
     */
    MyQueue.prototype.pop = function () {
        // pop的时候判断输出栈是否为空
        const size = this.stackOut.length;
        if (size) return this.stackOut.pop(); //不为空则输出栈出栈
        
        while (this.stackIn.length) { //输出栈为空,则把输入栈所有的元素加入输出栈
            this.stackOut.push(this.stackIn.pop());
        }
        return this.stackOut.pop();
    };
    
    /**
     * @return {number}
     */
    MyQueue.prototype.peek = function () {
        //查看队头的元素 复用pop方法,由于元素已经从输出栈pop,需要再次push到输出栈
        const x = this.pop(); 
        this.stackOut.push(x);
        return x;
    };
    
    /**
     * @return {boolean}
     */
    MyQueue.prototype.empty = function () {
        return !this.stackIn.length && !this.stackOut.length
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    3、155. 最小栈 (easy)

    设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

    实现 MinStack 类:

    • MinStack() 初始化堆栈对象。
    • void push(int val) 将元素val推入堆栈。
    • void pop() 删除堆栈顶部的元素。
    • int top() 获取堆栈顶部的元素。
    • int getMin() 获取堆栈中的最小元素。
    • 思路:定义两个栈stack和min_stack,stack正常push,min_stack只会push需要入栈和min_stack栈顶中较小的元素,这样每次删除min_stack均可以保证其栈顶元素为最小值。getMin返回min_stack栈顶元素,top返回stack栈顶元素。
    • 复杂度分析
      • 时间复杂度:对于题目中的所有操作,时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1),我们定义的每个操作最多调用栈操作两次。
      • 空间复杂度:O(n),其中 n 为总操作数。最坏情况下,我们会连续插入 n 个元素,此时两个栈占用的空间为 O(n)。
    var MinStack = function() {
        this.stack = [];
        this.min_stack = [Infinity];
    };
    
    /** 
     * @param {number} val
     * @return {void}
     */
    MinStack.prototype.push = function(val) {
        this.stack.push(val);
        // min_stack只会push需要入栈和栈顶中较小的元素
        this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], val));
    };
    
    /**
     * @return {void}
     */
    MinStack.prototype.pop = function() {
        this.stack.pop();
        this.min_stack.pop();
    };
    
    /**
     * @return {number}
     */
    MinStack.prototype.top = function() {
        // 返回stack栈顶元素
        return this.stack[this.stack.length - 1];
    };
    
    /**
     * @return {number}
     */
    MinStack.prototype.getMin = function() {
        // 返回min_stack栈顶元素
        return this.min_stack[this.min_stack.length - 1];
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    4、946. 验证栈序列 (medium)

    给定 pushedpopped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false

    提示:

    • 1 <= pushed.length <= 1000
    • 0 <= pushed[i] <= 1000
    • pushed 的所有元素 互不相同
    • popped.length == pushed.length
    • poppedpushed 的一个排列
    • 思路:用栈模拟出栈入栈的过程,当poppedindex指向的位置的元素和stack栈顶的元素一致时,出栈且 index++,最后判断stack是否完全遍历popped。
    • 复杂度分析:
      • 时间复杂度O(n),pushed中的元素入栈出栈一次;
      • 空间复杂度O(n)
    /**
     * @param {number[]} pushed
     * @param {number[]} popped
     * @return {boolean}
     */
    var validateStackSequences = function(pushed, popped) {
        const stack = [];//用栈模拟出栈入栈的过程
        let index = 0;
        const len = pushed.length;
        for (let i = 0; i < len; i++) {
            stack.push(pushed[i]);
          	//当popped中index指向的位置的元素和stack栈顶的元素一致时,出栈 并且 index++
            while (stack.length && index<len && popped[index] === stack[stack.length - 1]) {
                stack.pop();
                index++;
            }
     
        }
        return index === len; // 最后判断 index是否完全遍历popped
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    5、445. 两数相加 II (medium)

    给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

    你可以假设除了数字 0 之外,这两个数字都不会以零开头。

    提示:

    • 链表的长度范围为 [1, 100]
    • 0 <= node.val <= 9
    • 输入数据保证链表代表的数字无前导 0
    • 思路:将两个链表的节点都推入栈中,然后不断出栈,计算每个位置的值和进位,串连成一个新的链表

    • 复杂度分析

      • 时间复杂度:O(max(m,n)),其中 m 和 n 分别为两个链表的长度。我们需要遍历两个链表的全部位置,而处理每个位置只需要 O(1) 的时间。

      • 空间复杂度:O(m + n),其中 m和 n 分别为两个链表的长度。空间复杂度主要取决于我们把链表内容放入栈中所用的空间

    var addTwoNumbers = function(l1, l2) {
        const stack1 = [];
        const stack2 = [];
        while (l1 || l2) {//两链表入栈
            if (l1) {
                stack1.push(l1.val);
                l1 = l1.next;
            }
            if (l2) {
                stack2.push(l2.val);
                l2 = l2.next;
            }
        }
        let carry = 0;
        let ansList = null;
        while (stack1.length || stack2.length || carry !== 0) {//不断出栈
            const s1 = stack1.length ? stack1.pop() : 0;
            const s2 = stack2.length ? stack2.pop() : 0;
            let val = s1 + s2 + carry;
            carry = parseInt(val / 10);//计算进位
            val = val % 10;//计算当前节点的值
            const curNode = new ListNode(val);
            curNode.next = ansList;//向链表前插入新节点
            ansList = curNode;//重新赋值ansList
        }
        return ansList;
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    6、682. 棒球比赛 (easy)

    你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成,过去几回合的得分可能会影响以后几回合的得分。

    比赛开始时,记录是空白的。你会得到一个记录操作的字符串列表 ops,其中 ops[i] 是你需要记录的第 i 项操作,ops 遵循下述规则:

    1. 整数 x - 表示本回合新获得分数 x
    2. "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
    3. "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
    4. "C" - 表示前一次得分无效,将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

    请你返回记录中所有得分的总和。

    • 复杂度:时间复杂度O(n),空间复杂度O(n)
    /**
     * @param {string[]} ops
     * @return {number}
     */
    var calPoints = function (ops) {
        let ans = []
        for (let i = 0; i < ops.length; i++) {
            switch(ops[i]) {
                case 'C':
                    ans.pop();
                    break;
                case 'D':
                    ans.push(+ans[ans.length - 1] * 2);
                    break;
                case '+':
                    ans.push(+ans[ans.length - 1] + +ans[ans.length - 2]);
                    break;
                default:
                    ans.push(+ops[i])
            }
        }
        return ans.reduce((a, b) => a + b, 0);
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
  • 相关阅读:
    Redis单线程和多线程
    openharmony容器组件之SideBarContainer
    android button 按钮,设置左/右小图标,与文字居中距离
    PaddleX场景实战:PP-TS在电压预测场景上的应用
    基于情感分析+聚类分析+LDA主题分析对服装产品类的消费者评论分析(文末送书)
    Redis 五大类型源码及底层实现
    回顾 Spring
    C#创建并启动新的进程
    网络协议常见问题
    Linux命令教程:使用cat命令查看和处理文件
  • 原文地址:https://blog.csdn.net/qq_38987146/article/details/126506758