做一个网站,注册新公司名称查询,wordpress备案号代码,购物网站宣传方案随想录日记part10 t i m e #xff1a; time#xff1a; time#xff1a; 2024.03.03 主要内容#xff1a;今天的主要内容是深入了解数据结构中栈和队列#xff0c;并通过三个 l e e t c o d e leetcode leetcode 题目深化认识。
20. 有效的括号1047. 删除字符串中的所有…随想录日记part10 t i m e time time 2024.03.03 主要内容今天的主要内容是深入了解数据结构中栈和队列并通过三个 l e e t c o d e leetcode leetcode 题目深化认识。
20. 有效的括号1047. 删除字符串中的所有相邻重复项150. 逆波兰表达式求值 Topic1有效的括号
题目 给定一个只包括 ′ ( ′ ′ ) ′ ′ ′ ′ ′ ′ [ ′ ′ ] ′ (){}[] ′(′′)′′′′′′[′′]′ 的字符串 s s s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例 输入: s ( ) [ ] s ()[]{} s()[] 输出: t r u e true true
思路 括号匹配是使用栈解决的经典问题 先来分析一下 这里有三种不匹配的情况: 1.字符串里左方向的括号多余 2.括号没有多余但是括号的类型没有匹配上 3.字符串里右方向的括号多余 其 java代码的实现与解释如下 class Solution {public boolean isValid(String s) {//建立堆栈StackCharacter stack new Stack();char ch;//如果s的长度不是偶数则无法匹配if(s.length()%2!0)return false;for(int i0;is.length();i){chs.charAt(i);if(ch(){stack.push());}else if(ch{){stack.push(});}else if(ch[){stack.push(]);}else if(stack.isEmpty() || stack.peek()!ch){return false;}else{stack.pop();}}return stack.isEmpty();}
}时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) Topic2删除字符串中的所有相邻重复项
题目 给出由小写字母组成的字符串 S S S重复项删除操作会选择两个相邻且相同的字母并删除它们。在 S S S 上反复执行重复项删除操作直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例 输入: a b b a c a abbaca abbaca 输出: c a ca ca 解释: 例如在 a b b a c a abbaca abbaca 中我们可以删除 b b bb bb 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 a a c a aaca aaca其中又只有 a a aa aa 可以执行重复项删除操作所以最后的字符串为 c a ca ca。
思路 本题也是用栈来解决的经典题目如下图 其 java代码的实现与解释如下 class Solution {public String removeDuplicates(String s) {//建立堆栈StackCharacter stack new Stack();char ch;for(int i0;is.length();i){chs.charAt(i);if(stack.isEmpty()true){stack.push(ch);}else{if(chstack.peek())stack.pop();else{stack.push(ch);}}}String te;while(stack.isEmpty()!true){testack.pop()te;}return te;}
}时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1)返回值不计空间复杂度 Topic3逆波兰表达式求值
题目 给你一个字符串数组 t o k e n s tokens tokens 表示一个根据逆波兰表示法表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。
示例 输入: t o k e n s [ 2 , 1 , , 3 , ∗ ] tokens [2,1,,3,*] tokens[2,1,,3,∗] 输出: 该算式转化为常见的中缀算术表达式为 ( ( 2 1 ) ∗ 3 ) 9 ((2 1) * 3) 9 ((21)∗3)9
思路 用栈操作运算遇到数字则入栈遇到运算符则取出栈顶两个数字进行计算并将结果压入栈中 ) java实现的代码如下 cclass Solution {public int evalRPN(String[] tokens) {//建立堆栈StackInteger stack new Stack();for(String s:tokens){if(.equals(s))stack.push(stack.pop()stack.pop());else if(-.equals(s))stack.push(-stack.pop()stack.pop());else if(*.equals(s))stack.push(stack.pop()*stack.pop());else if(/.equals(s)){int temp1 stack.pop();int temp2 stack.pop();stack.push(temp2 / temp1);}else stack.push(Integer.valueOf(s));} return stack.pop();}
}时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n)
