代码随想录 ﹏ヽ暗。殇╰゛Y 2024-02-22 09:15 61阅读 0赞 ## 一、Leetcode 20. 有效的括号 ## ### 1.题目 ### 给定一个只包括 '(',')','\{','\}','\[','\]' 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 复制代码 `左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。` 示例 1: 输入:s = "()" 输出:true 示例 2: 输入:s = "()\[\]\{\}" 输出:true 示例 3: 输入:s = "(\]" 输出:false 提示: scss 复制代码 `1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/va…][leetcode.cn_problems_va] ### 2.解题思路 ### 方法一:栈 判断括号的有效性可以使用「栈」这一数据结构来解决。 我们遍历给定的字符串 ss。当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。 当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 ss 无效,返回 FalseFalse。为了快速判断括号的类型,我们可以使用哈希表存储每一种括号。哈希表的键为右括号,值为相同类型的左括号。 在遍历结束后,如果栈中没有左括号,说明我们将字符串 ss 中的所有左括号闭合,返回 TrueTrue,否则返回 FalseFalse。 注意到有效字符串的长度一定为偶数,因此如果字符串的长度为奇数,我们可以直接返回 FalseFalse,省去后续的遍历判断过程。 ### 3.代码实现 ### java 复制代码 `class Solution { private static final Map<Character,Character> map = new HashMap<Character,Character>(){ { put('{','}'); put('[',']'); put('(',')'); put('?','?'); }}; public boolean isValid(String s) { if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false; LinkedList<Character> stack = new LinkedList<Character>() { { add('?'); }}; for(Character c : s.toCharArray()){ if(map.containsKey(c)) stack.addLast(c); else if(map.get(stack.removeLast()) != c) return false; } return stack.size() == 1; } }` ## 二、Leetcode 1047. 删除字符串中的所有相邻重复项 ## ### 1.题目 ### 给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。 在 S 上反复执行重复项删除操作,直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例: 输入:"abbaca" 输出:"ca" 解释: 例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。 提示: matlab 复制代码 `1 <= S.length <= 20000 S 仅由小写英文字母组成。` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/re…][leetcode.cn_problems_re] ### 2.解题思路 ### 方法一:栈 充分理解题意后,我们可以发现,当字符串中同时有多组相邻重复项时,我们无论是先删除哪一个,都不会影响最终的结果。因此我们可以从左向右顺次处理该字符串。 而消除一对相邻重复项可能会导致新的相邻重复项出现,如从字符串 abbaabba 中删除 bbbb 会导致出现新的相邻重复项 aaaa 出现。因此我们需要保存当前还未被删除的字符。一种显而易见的数据结构呼之欲出:栈。我们只需要遍历该字符串,如果当前字符和栈顶字符相同,我们就贪心地将其消去,否则就将其入栈即可。 ### 3.代码实现 ### java 复制代码 `class Solution { public: string removeDuplicates(string s) { string stk; for (char ch : s) { if (!stk.empty() && stk.back() == ch) { stk.pop_back(); } else { stk.push_back(ch); } } return stk; } };` ## 三、Leetcode 150. 逆波兰表达式求值 ## ### 1.题目 ### 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意: arduino 复制代码 `有效的算符为 '+'、'-'、'*' 和 '/' 。 每个操作数(运算对象)都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。` 示例 1: 输入:tokens = \["2","1","+","3","\*"\] 输出:9 解释:该算式转化为常见的中缀算术表达式为:((2 + 1) \* 3) = 9 示例 2: 输入:tokens = \["4","13","5","/","+"\] 输出:6 解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6 示例 3: 输入:tokens = \["10","6","9","3","+","-11","*","/","*","17","+","5","+"\] 输出:22 解释:该算式转化为常见的中缀算术表达式为: ((10 \* (6 / ((9 + 3) \* -11))) + 17) + 5 = ((10 \* (6 / (12 \* -11))) + 17) + 5 = ((10 \* (6 / -132)) + 17) + 5 = ((10 \* 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 提示: matlab 复制代码 `1 <= tokens.length <= 104 tokens[i] 是一个算符("+"、"-"、"*" 或 "/"),或是在范围 [-200, 200] 内的一个整数` 逆波兰表达式: 逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。 scss 复制代码 `平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。` 逆波兰表达式主要有以下两个优点: 复制代码 `去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/ev…][leetcode.cn_problems_ev] ### 2.解题思路 ### 方法一:栈 逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作: 复制代码 `如果遇到操作数,则将操作数入栈; 如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数,后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。` 整个逆波兰表达式遍历完毕之后,栈内只有一个元素,该元素即为逆波兰表达式的值。 ### 3.代码实现 ### java 复制代码 `class Solution { public int evalRPN(String[] tokens) { Deque<Integer> stack = new LinkedList<Integer>(); int n = tokens.length; for (int i = 0; i < n; i++) { String token = tokens[i]; if (isNumber(token)) { stack.push(Integer.parseInt(token)); } else { int num2 = stack.pop(); int num1 = stack.pop(); switch (token) { case "+": stack.push(num1 + num2); break; case "-": stack.push(num1 - num2); break; case "*": stack.push(num1 * num2); break; case "/": stack.push(num1 / num2); break; default: } } } return stack.pop(); } public boolean isNumber(String token) { return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)); } }` [leetcode.cn_problems_va]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fvalid-parentheses [leetcode.cn_problems_re]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fremove-all-adjacent-duplicates-in-string [leetcode.cn_problems_ev]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fevaluate-reverse-polish-notation
相关 代码随想录 前言 代码随想录算法训练营day44 -------------------- 一、Leetcode 518. 零钱兑换 II 1.题目 给你一个整数数组 布满荆棘的人生/ 2024年02月22日 09:45/ 0 赞/ 54 阅读
相关 代码随想录 前言 代码随想录算法训练营day14 -------------------- 一、Leetcode \\\\ 144. 二叉树的前序遍历 1.题目 给你 待我称王封你为后i/ 2024年02月22日 09:16/ 0 赞/ 44 阅读
相关 代码随想录 一、Leetcode 20. 有效的括号 1.题目 给定一个只包括 '(',')','\{','\}','\[','\]' 的字符串 s ,判断字符串是否有效。 ﹏ヽ暗。殇╰゛Y/ 2024年02月22日 09:15/ 0 赞/ 62 阅读
相关 代码随想录 前言 代码随想录算法训练营day06 -------------------- 一、哈希表基础知识 【 [代码随想录][Link 1]】 【[菜鸟教 桃扇骨/ 2024年02月22日 09:14/ 0 赞/ 48 阅读
相关 代码随想录 前言 代码随想录算法训练营day39 -------------------- 一、Leetcode 62.不同路径 1.题目 一个机器人位于一个 m x 女爷i/ 2024年02月22日 04:39/ 0 赞/ 82 阅读
相关 代码随想录 前言 代码随想录算法训练营day37 -------------------- 一、Leetcode 968.监控二叉树 v 1.题目 给定一个二叉树,我 朱雀/ 2024年02月22日 04:38/ 0 赞/ 109 阅读
相关 代码随想录 前言 代码随想录算法训练营day37 -------------------- 一、Leetcode 968.监控二叉树 v 1.题目 给定一个二叉树,我 叁歲伎倆/ 2024年02月22日 04:37/ 0 赞/ 63 阅读
相关 代码随想录 前言 代码随想录算法训练营day39 -------------------- 一、Leetcode 62.不同路径 1.题目 一个机器人位于一个 m x 左手的ㄟ右手/ 2024年02月22日 02:29/ 0 赞/ 52 阅读
相关 代码随想录 前言 代码随想录算法训练营day35 -------------------- 一、Leetcode 860.柠檬水找零 1.题目 在柠檬水摊上,每一杯柠 朱雀/ 2024年02月22日 02:26/ 0 赞/ 116 阅读
相关 代码随想录 前言 代码随想录算法训练营day34 -------------------- 一、Leetcode 1005.K次取反后最大化的数组和 1.题目 给你一 ゞ 浴缸里的玫瑰/ 2024年02月22日 02:25/ 0 赞/ 40 阅读
还没有评论,来说两句吧...