20. 有效的括号
扣除主题链接(opens new window)
给定一个只包括 字符串，判断字符串是否有效。
需要满足有效字符串：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序关闭。
- 注意空字符串可视为有效字符串。
示例 1:
- 输入: "()"
- 输出: true
示例2:
- 输入: ()[]{}”
- 输出: true
示例3:
- 输入: "(]"
- 输出: false
示例4:
- 输入: "([)"""
- 输出: false
示例5:
- 输入: "{[]"""""
- 输出: true
思路：
没有想法，直接看题解。首先要判断字符串是否有效，需要满足两点:
1、左括号必须与右括号闭合，反之亦然
2、左括号必须以正确的顺序闭合
无效字符串只有三种情况：
1、例如，右括号大于左括号， s = "([])"
2、左括号大于右括号， 比如 s = "([])"
3、顺序不对 ，比如 s = """""""""""""""
采用栈的理念，如果有右括号，则添加相应的左括号；此时，如果左括号遍历，则需要查看栈顶元素是否匹配或为空栈，以便判断情况3和情况2；如果栈顶元素匹配，栈不是空的，把同样的左括号从栈里拿出来。
全部遍历后，还栈还没有空，说明情况1发生了。
class Solution { public boolean isValid(String s) { Deque<Character> deq = new LinkedList<>(); char ch ; for(int i = 0; i < s.length(); i++){ ch = s.charAt(i); if(ch == '('){ deq.push(')'); }else if(ch == '{'){ deq.push('}'); }else if(ch == '['){ deq.push(']'); }else if(deq.isEmpty() || deq.peek() != ch){ 如果下一个不是ch，///deq是空的，说明右方向元素太多。说明顺序不对 return false; }else{ deq.pop(); } } return deq.isEmpty(); }}1047. 删除字符串中的所有相邻重复项
扣除主题链接(opens new window)
给出由小写字母组成的字符串S。重复项删除操作将选择两个相邻且相同的字母并删除它们。
在 S 在不能继续删除之前，反复执行重复项删除操作。
删除所有重复项后返回最终字符串。答案是唯一的。
示例：
- 输入："abbaca"
- 输出："ca"
- 解释：例如，在 "abbaca" 中间，我们可以删除它 "bb" 由于两个字母相邻且相同，这是此时唯一可以删除的重复项。然后我们得到字符串 "aaca"，其中只有 "aa" 重复项的删除操作可以执行，因此最终字符串是 "ca"。
提示：
- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
思路：
一开始，我想使用栈，遍历字符串。如果字符与栈中的字符相同，我会把栈中的字符从栈中走出来，最后留下我们想要的字符串。
后来写的时候发现有三个问题:
1、Deque的用法
Deque是一个双端队列，可以作为栈或队列使用。
一般来说，新的Deque方法是
Deque<Integer> deque = new LinkedList<>();Deque的许多方法都有重复语义，与Queue或Collection接口兼容
对于队列，入队时从尾部插入元素，出队时从头部插入元素
入队：offer()或者offerlast()
出队：poll() 或者 pollFirst()
查看队首： peek()
针对栈：
入栈：push()
出栈：poll()
栈顶：peek()
2、不能简单地考虑堆栈中的字符和字符串，最好是相邻的
3、最后，如何将栈中的字符输出到字符串中，必须保证顺序不变
class Solution { public String removeDuplicates(String s) { Deque<Character> deq = new LinkedList<>(); char ch; for(int i = 0; i < s.length(); i++){ ch = s.charAt(i); if(deq.isEmpty() == true || deq.peek() != ch){ deq.push(ch); }else{ deq.pop(); } } String str = ""; while(!deq.isEmpty()){ str = deq.pop()+str; } return str; }}150. 逆波兰表达式求值
扣除主题链接(opens new window)
根据 逆波兰表示法，要求表达值。
有效的操作符包括+ , - , * , /.每个计算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定的逆波兰表达式总是有效的。换句话说，表达式总是有效的值，没有除数 0 的情况。
示例1：
- 输入: ["2", "1", "+", "3", " * "]
- 输出: 9
- 解释: 该算法转化为常见的中缀算术表达式:(2) + 1) * 3) = 9
示例2：
- 输入: ["4", "13", "5", "/", "+"]
- 输出: 6
- 解释: 该算法转化为常见的中缀算术表达式:(4 + (13 / 5)) = 6
示例3：
- 输入: ["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逆波兰表达式：它是一种后缀表达式，所谓的后缀是指操作符写在后面。
常用的算法是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法是 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去除括号后，表达式没有歧义，即使上表达式写成 1 2 + 3 4 + * 正确的结果也可以按顺序计算。
- 适用于栈操作：遇到数字时进入栈；遇到运算符时，取出栈顶两个数字进行计算，并将结果压入栈中。
思想：
逆波兰表达式相当于后缀表达式，与之前删除的相邻重复项一致，只要有“+”、“-”、“*”、“/”四个字符需要拿出栈中最近两个项目进行操作，然后将操作结果压入栈中。剩下的就是我们想要的结果。
class Solution { public int evalRPN(String[] tokens) { Deque<Integer> deq = new LinkedList<>(); for(int i = 0; i < tokens.length; i++){ if("+".equals(tokens[i])){ deq.push(deq.pop()+deq.pop()); }else if("-".equals(tokens[i])){ deq.push(-deq.pop()+deq.pop()); }else if("*".equals(tokens[i])){ deq.push(deq.pop()*deq.pop()); }else if("/".equals(tokens[i])){ int tmp = deq.pop(); int tmp1 = deq.pop(); deq.push(tmp1 / tmp); }else{ deq.push(Integer.valueOf(tokens[i])); } } return deq.pop(); }}Integer valueOf(String s):返回指定的保存 String 的值的 Integer 对象。
湘公网安备43019002002060