leetcode刷题(javaScript)——栈相关场景题总结

 在LeetCode刷题中,栈是一个非常有用的数据结构,可以解决许多问题,包括但不限于以下几类问题:

  1. 括号匹配问题:例如检查括号序列是否有效、计算表达式的值等。
  2. 逆波兰表达式求值:使用栈来实现逆波兰表达式的计算。
  3. 柱状图中最大矩形:通过维护一个递增栈来解决柱状图中最大矩形的问题。
  4. 简化路径:使用栈来简化给定的文件路径。
  5. 二叉树的遍历:使用栈来实现二叉树的前序、中序、后序遍历等。

栈的主要思想是“后进先出”(Last In First Out,LIFO),即最后进入栈的元素最先出栈。栈通常用于解决需要“回溯”或“撤销”操作的问题,以及需要维护“最近相关性”的问题。

对于新手刷题,以下是一些建议:

  1. 掌握基本操作:首先要熟练掌握栈的基本操作,包括入栈、出栈、获取栈顶元素等。
  2. 理解栈的应用场景:了解栈在解决问题中的常见应用场景,例如上面提到的几类问题。
  3. 练习经典问题:尝试解决一些经典的栈相关问题,例如括号匹配、逆波兰表达式求值等。
  4. 多思考、多实践:在解决问题时,多思考不同的解题思路,多实践不同类型的题目,逐渐提升对栈的理解和应用能力。

20. 有效的括号

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

主要思路是遇到左括号推入栈

遇到右括号,将栈顶左括号移除,并和它进行对比。

不相等return false

否则继续比较,直到最后,判断是否还有没匹配上的左括号

 刚开始刷题,先看第一个版本 ,有两个地方可以优化,一个是很明显的stask.length的判断可以改写为三元表达式。另外可以用对象key:value的特性进行括号对比。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const stask = [];
    for (let item of s) {
        if (['(', '[', '{'].includes(item)) {
            stask.push(item);
        } else {
            const pre = stask.pop();
            if ((pre === '(' && item === ')') || (pre === '[' && item === ']') || (pre === '{' && item === '}')) {
                continue;
            } else {
                return false;
            }
        }
    }
    if (stask.length > 0) {
        return false;
    } else {
        return true;
    }
};

优化后的代码

使用了一个映射表 map 来存储左右括号的对应关系,这样可以使代码更加清晰易懂。同时,在判断右括号是否匹配时,直接与栈顶元素进行比较,避免了多次判断的情况,提高了效率。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const stask = [];
    const map = {
        '(': ')',
        '[': ']',
        '{': '}',
    };
    for (let char of s) {
        if (char in map) {
            stask.push(char);
        } else if (char != map[stask.pop()]) {
            return false;
        }
    }
    return stask.length === 0;
};

这里有个巧妙之处,可以用in判断一个属性是不是对象的属性!!

此外一些小点,如可用用for of进行字符串的遍历

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

给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

 思路是使用栈来消除相邻重复的字符。当前遍历的元素和前一个栈顶元素比较,如果不等,将已经pop出的元素和当前元素入栈,继续。否则,相等,当重复的元素已经pop了,无需处理。

比较后留在栈的元素就是没有相邻重复的数组,再将数组转成字符串。使用数组的join方法。

这里相同的是对字符串操作时,使用for of进行遍历即可

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
    let stack = [];
    for (let char of s) {
        const pre = stack.pop();
        if ( char != pre) {
            stack.push(pre);
            stack.push(char);
        }
    }
    return stack.join('');
};

 1614. 括号的最大嵌套深度

 这道题原文很长,其实主要就是求括号最大嵌套层数,可以不考虑中间出现的数字和运算符。

 思想是用栈存储左括号,当遇到右括号的时候先看栈内左括号的个数,即当前的嵌套层数,将其保存下来。然后将栈顶左括号出栈;只要统计栈的最大长度即可得到最大嵌套深度

/**
 * @param {string} s
 * @return {number}
 */
var maxDepth = function (s) {
    let stack = [];
    let tempDep = 0;
    let dep = 0;
    for (let char of s) {
        //char是左括号
        if (char === '(') {
            stack.push(char);
        } else if (char === ')') {
            //char是右括号
            tempDep = stack.length;
            dep = tempDep > dep ? tempDep : dep;
            stack.pop();
        }
    }
    return dep;
};

 这样只用考虑左括号和右括号就好啦

 1544. 整理字符串

给你一个由大小写英文字母组成的字符串 s 。一个整理好的字符串中,两个相邻字符 s[i]s[i+1],其中 0<= i <= s.length-2 ,要满足如下条件:

  • s[i] 是小写字符,则 s[i+1] 不可以是相同的大写字符。
  • s[i] 是大写字符,则 s[i+1] 不可以是相同的小写字符。

请你将字符串整理好,每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除,直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下,测试样例对应的答案是唯一的。

注意:空字符串也属于整理好的字符串,尽管其中没有任何字符。

 思路:用栈保留不相邻大小写字符,每次用栈顶元素与当前元素比较,如果两个是相邻的大小写字符,则弹出栈顶元素。否则,当前元素入栈。

使用字符串的charCodeAt方法获取字符串的ASCII码;使用Math.abs返回相差的绝对值,大小写相差32

返回字符串,需要将stack数组转字符串,同样也用数组的join方法

/**
 * @param {string} s
 * @return {string}
 */

var makeGood = function (s) {
    let stack = [];
    for (let char of s) {
        let stackTop = stack[stack.length - 1];
        if (stackTop && Math.abs(char.charCodeAt(0) - stackTop.charCodeAt(0)) == 32) {
            stack.pop();
        } else {
            stack.push(char);
        }
    }
    return stack.join("");
};

682. 棒球比赛 ——逆波兰表达式求值

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

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

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

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

 这是一道用栈来进行求值的,当前项与前一项或前两项有关系,且已经存在的元素可以被删除。就可以考虑栈对栈顶元素的操作

/**
 * @param {string[]} operations
 * @return {number}
 */
const calPoints = function (operations) {
  const stack = [];
  for (let item of operations) {
    if (item === "C") {
      stack.pop();
    } else if (item === "D") {
      stack.push(stack[stack.length - 1] * 2);
    } else if (item === "+") {
      stack.push(stack[stack.length - 1] + stack[stack.length - 2]);
    } else {
      stack.push(Number(item));
    }
  }

  return stack.reduce((total, num) => total + num, 0);
};

 思想是用栈存储确定后的没项元素,根据当前匹配的是数字还是符号进行响应规则增加或删除项。最后用数组的reduce方法对数字求和。比较简单

 150. 逆波兰表达式求值

逆波兰表达式是一种不需要括号来标识优先级的数学表达式表示方法,它通过将操作符放在操作数的后面来表示运算顺序。

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

  • 有效的算符为 '+''-''*''/'
  • 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

 

 思路:用栈存储操作数,遇到操作符号+-*/时从栈顶依次弹出两个数,分别作为右操作数和左操作数。需要手动处理+-*/匹配时的运算。并且考虑除法向0靠拢。js的Math函数,trunc提供了这个方法。这个平时真用的挺少的。先给个初版的,后面有个进阶优化的代码

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
    let stack = [];
    const symbol = ['+', '-', '*', '/'];
    for (let item of tokens) {
        if (symbol.includes(item)) {
            let right = stack.pop();
            let left = stack.pop();
            stack.push(getData(left, right, item));
        } else {
            stack.push(Number(item));
        }
    }
    return stack[0];
};
function getData(left, right, operate) {
    switch (operate) {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return Math.trunc(left / right);
    }

}

 这里比较操作符用数组includes方法减少了比较,那如何更加匹配时的简化运算逻辑呢

考虑使用ES6提供的Map对象,key值存放符合,value值存放一个函数,接收两个操作数。

通过Map对象的has方法判断key值是否存在,通过get方法获取函数。parseInt和Number都可以转换数字,这里只是提供了一种方法

var evalRPN = function (tokens) {
    const stack = [];
    const operators = new Map([
        ['+', (a, b) => a + b],
        ['-', (a, b) => a - b],
        ['*', (a, b) => a * b],
        ['/', (a, b) => Math.trunc(a / b)]
    ]);

    for (let token of tokens) {
        if (operators.has(token)) {
            let right = stack.pop();
            let left = stack.pop();
            let result = operators.get(token)(left, right);
            stack.push(result);
        } else {
            stack.push(parseInt(token));
        }
    }

    return stack[0];
};

 

844. 比较含退格的字符串

给定 st 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true# 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function (s, t) {
    return getStr(s) === getStr(t);
};

function getStr(str) {
    let stack = [];
    for (let char of str) {
        if (char != '#') {
            stack.push(char);
        } else {
            stack.pop();
        }
    }
    return stack.join('');
}

 思路:用栈保存s或t最终的结果,在比较两者是否相等。

不等于#时push进,为#时将栈顶元素弹出。

比较简单

 2696. 删除子串后的字符串最小长度

给你一个仅由 大写 英文字符组成的字符串 s 。你可以对此字符串执行一些操作,在每一步操作中,你可以从 s 中删除 任一个 "AB""CD" 子字符串。通过执行操作,删除所有 "AB""CD" 子串,返回可获得的最终字符串的 最小 可能长度。注意,删除子串后,重新连接出的字符串可能会产生新的 "AB""CD" 子串。

/**
 * @param {string} s
 * @return {number}
 */
var minLength = function (s) {
    const map = {
        'A': 'B',
        'C': 'D'
    }
    let stack = [];
    for (let char of s) {
        if (stack.length > 0 && char === map[stack[stack.length - 1]]) {
            stack.pop();
        } else {
            stack.push(char);
        }
    }
    return stack.length;
};

也是一道典型的字符匹配题目,用栈加map存储键值对比较真的无敌了。

不啰嗦了,这里返回的是数组长度注意一下就行

 71. 简化路径

给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' 。 对于此问题,任何其他格式的点(例如,'...')均被视为文件/目录名称。

请注意,返回的 规范路径 必须遵循下述格式:

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/'
  • 最后一个目录名(如果存在)不能 '/' 结尾。
  • 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '.''..')。

返回简化后得到的 规范路径

 

 终结题目的要求:/不能重复;..表示回退一步;.表示在当前;这道题的难点是对/的处理。要是按/进行分隔呢,只保留文件名和操作运算符。看下代码怎么实现吧

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function (path) {
    let stack = [];
    const pathArr = path.split('/');
    pathArr.forEach(item => {
        if (item === '..') {
            stack.pop();
        } else if (item && item != '.') {
            stack.push(item);
        }
    })
    return stack.length ? '/' + stack.join('/') : '/';
};

 思路:按照/将字符分开为数组。然后用栈存储当前经过的路径上的文件夹名称。

遇到..栈顶弹出,遇到.不处理。遇到文件名,push进栈

最后将文件名按/拼接,注意以/开头

144. 二叉树的前序遍历

(1)先(根)序遍历(根左右)

不管是前、中、后序遍历,总的来说都要从根元素开始,把左子树遍历一遍在把右子树遍历一遍,只不过过程中打印节点顺序不同而有所差异。栈的思想是当前元素遍历到了,但是它的左子树或右子树没遍历完,需要入栈,当左子树或右子数遍历了即可出栈

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
    let arr = [];
    let stack = [];
    let current = root;
    while (current != null || stack.length > 0) {
        while (current!= null) {
            arr.push(current.val);
            stack.push(current);
            current = current.left;

        }
        current = stack.pop();
        current = current.right;
    }
    return arr;
};

 arr存放遍历后的数据,优先入栈跟节点,其次左节点,最后右节点。每次循环仅得到一个节点,切记不多写,容易混乱

94. 二叉树的中序遍历

中(根)序遍历(左根右)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    const arr = [];
    const stack = [];
    let current = root;
    while (current != null || stack.length > 0) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        arr.push(current.val);
        current = current.right;

    }
    return arr;
};

 入栈的顺序是一样的,只不过arr添加的顺序不同,这里先push的一定是左子树

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/420075.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python实现链表:从基础到应用

一、引言 链表是一种常见的数据结构&#xff0c;它由一系列节点组成&#xff0c;每个节点包含数据和指向下一个节点的指针。链表在内存中的存储不是连续的&#xff0c;这使得它在插入和删除操作上具有较高的效率。本文将使用Python语言来实现一个简单的链表&#xff0c;并展示其…

零基础学编程,中文编程工具之进度标尺构件的编程用法

零基础学编程&#xff0c;中文编程工具之进度标尺构件的编程用法 一、前言 今天给大家分享的中文编程开发语言工具 进度条构件的用法。 编程入门视频教程链接 https://edu.csdn.net/course/detail/39036 编程工具及实例源码文件下载可以点击最下方官网卡片——软件下载——…

力扣:35. 搜索插入位置

力扣&#xff1a;35. 搜索插入位置 描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,…

windows系统玩《模拟人生 4》 免安装版本

本文介绍如何在windows系统上玩《模拟人生 4》这个游戏&#xff0c;无需安装&#xff0c;直接玩&#xff01; 首先下载百度网盘分享的文件&#xff0c;这里下载文章末尾。 下载完成后先点击 language-change.exe 将游戏语言更改为英文&#xff0c;默认是俄语&#xff0c;根本…

sqllabs的order by注入

当我们在打开sqli-labs的46关发现其实是个表格&#xff0c;当测试sort等于123时&#xff0c;会根据列数的不同来进行排序 我们需要利用这个点来判断是否存在注入漏洞&#xff0c;通过加入asc 和desc判断页面有注入点 1、基于使用if语句盲注 如果我们配合if函数&#xff0c;表达…

B端系统:导航机制设计,用户体验提升的法宝

Hi&#xff0c;大家好&#xff0c;我是贝格前端工场&#xff0c;从事8年前端开发的老司机。很多B端系统体验不好很大一部分原因在于导航设计的不合理&#xff0c;让用户无所适从&#xff0c;大大降低了操作体验&#xff0c;本文着重分析B端系统的导航体系改如何设计&#xff0c…

[CISCN2019 华北赛区 Day2 Web1]Hack World 1 题目分析与详解

一、分析判断 进入靶机&#xff0c;主页面如图&#xff1a; 主页面提供给我们一条关键信息&#xff1a; flag值在 表flag 中的 flag列 中。 接着我们尝试输入不同的id&#xff0c;情况分别如图&#xff1a; 当id1时&#xff1a; 当id2时&#xff1a; 当id3时&#xff1a; 我…

【IO流系列】ConvertStream 转换流

转换流 1. 概述2. 作用3. 字符编码和字符集3.1 字符编码3.2 字符集 4. InputStreamReader字符转换输入流4.1 构造方法4.2 代码示例 5. OutputStreamWriter字符转换输出流5.1 构造方法5.2 代码示例 6. 练习6.1 练习1&#xff1a;转换文件编码6.2 练习2&#xff1a;读取文件数据 …

Spring 源码解析

文章目录 前言相关Spring的定义接口整体代码StartupStep contextRefresh this.applicationStartup.start("spring.context.refresh")prepareRefresh()obtainFreshBeanFactory()registerBeanPostProcessors(beanFactory)SpringAOP原码流程EnableAspectJAutoProxyAnno…

基于java+springboot女士电商平台系统源码+文档设计

基于javaspringboot女士电商平台系统源码文档设计 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获取源…

GaussDB跨云容灾:实现跨地域的数据库高可用能力

背景 金融、银行业等对数据的安全有着较高的要求&#xff0c;同城容灾建设方案&#xff0c;在绝大多数场景下可以保证业务数据的安全性&#xff0c;但是在极端情况下&#xff0c;如遇不可抗力因素等&#xff0c;要保证数据的安全性&#xff0c;就需要采取跨地域的容灾方案。 …

【大咖分享】:千帆AppBuilder:我的AI大模型科研搭子

同济子豪兄介绍 不知不觉&#xff0c;我做人工智能科技区博主已经七年了。从斯坦福公开课系列&#xff0c;到精读AI经典论文系列&#xff0c;从编程奇妙夜&#xff0c;到两天搞定AI毕业设计系列。我们为十几万学员&#xff0c;提供人工智能各方向的论文课程、生涯规划、课题辅…

ROS2体系框架

文章目录 1.ROS2的系统架构2.ROS2的编码风格3.细谈初始化和资源释放4.细谈配置文件5.ROS2的一些命令6.ROS2的核心模块6.1 通信模块6.2 功能包6.3 分布式6.4 终端命令和rqt6.5 launch6.6 TF坐标变换6.7 可视化RVIZ 1.ROS2的系统架构 开发者的工作内容一般都在应用层&#xff0c;…

【计算机网络】五种IO模型与IO多路转接之select

文章目录 一、五种IO模型二、非阻塞IO1.fcntl2.实现函数SetNoBlock3.轮询方式读取标准输入 三、I/O多路转接之select1.初识select2.select函数原型3.socket就绪条件4.select的特点5.select缺点6.select使用案例--只读取数据的server服务器1.err.hpp2.log.hpp3.sock.hpp4.select…

游泳耳机哪种款式好?简单6招教你选到高品质机型!

游泳是一项全身性的运动&#xff0c;不仅能帮助我们保持身体健康&#xff0c;还能让我们在水中放松心情&#xff0c;享受水中的乐趣。而音乐则是人们生活中不可或缺的一部分&#xff0c;它能带给我们快乐和力量。当游泳与音乐相结合&#xff0c;游泳耳机应运而生&#xff0c;为…

MySQL-MHA搭建、故障测试

一、架构说明 MHA&#xff08;Master High Availability&#xff09;是一个用于 MySQL 主从复制管理和自动故障转移的开源工具集。MHA 的主要目的是提供 MySQL 环境的高可用性和自动故障转移功能&#xff0c;确保在主库发生故障时能够快速切换到备库&#xff0c;降低业务中断时…

机器人组装、充电桩组装行业生产管理MES系统免费用

​随着工业4.0和智能制造的兴起&#xff0c;企业对于生产过程的数字化、智能化需求日益迫切。传统的MES系统实施周期长、成本高&#xff0c;成为许多企业数字化转型的瓶颈。而低代码开发平台的出现为这一问题提供了新的解决思路。 ​一、万界星空科技低代码平台的优势&#xff…

【市工信】2024年青岛市绿色工厂、绿色工业园区等绿色制造示范申报

科大睿智小编从青岛市工信局了解到&#xff0c;为深入贯彻绿色发展理念&#xff0c;牢固树立绿色低碳发展导向&#xff0c;进一步完善绿色制造体系&#xff0c;培育绿色制造先进典型&#xff0c;根据《工业和信息化部关于印发<绿色工厂梯度培育及管理暂行办法>的通知》&a…

nginx出现 “414 request-uri too large”

nginx出现 “414 request-uri too large” 1.修改传参方式 POST 2.字段能变成后端获取就自己获取&#xff0c;不用前端传 3.修改nginx配置&#xff0c;添加client_header_buffer_size 512k;large_client_header_buffers 4 512k;配置

zephyr学习

zephyr内核对象学习 定时器 类似linux的定时器&#xff0c; 可以分别设置第一次到期时间和后续的周期触发时间&#xff0c; 可以注册到期回调和停止回调 还有一个计数状态&#xff0c;用于标记timer到期了多少次 duration&#xff1a;设定timer第一次到期的时间。 period: …