宁波网站制作流程,网站建设400电话,新闻内容摘抄,百度做网站多20. 有效的括号
● 力扣题目链接 ● 给定一个只包括 ‘(’#xff0c;‘)’#xff0c;‘{’#xff0c;‘}’#xff0c;‘[’#xff0c;‘]’ 的字符串#xff0c;判断字符串是否有效。 ● 有效字符串需满足#xff1a; ● 左括号必须用相同类型的右括号闭合。 ● 左…20. 有效的括号
● 力扣题目链接 ● 给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串判断字符串是否有效。 ● 有效字符串需满足 ● 左括号必须用相同类型的右括号闭合。 ● 左括号必须以正确的顺序闭合。 ● 注意空字符串可被认为是有效字符串。
思路
● 使用栈即可前括号就入栈对应的后括号 ● 如果不是前括号看栈是否空{}}“然后看栈顶元素能否匹配”{]“不能返回false能就弹出 ● 循环结束看栈是否为空”( ● 时间复杂度O(n) 空间复杂度O(n)
代码
class Solution {public boolean isValid(String s) {DequeCharacter stack new ArrayDeque();for (int i 0; i s.length(); i) {Character c s.charAt(i);if (c.equals(()) {stack.addFirst());} else if (c.equals([)) {stack.addFirst(]);} else if (c.equals({)) {stack.addFirst(});} else if (stack.isEmpty() || !stack.peekFirst().equals(c)) {return false;} else {stack.removeFirst();}}return stack.isEmpty();}
}1047. 删除字符串中的所有相邻重复项
● 力扣题目链接 ● 给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。 ● 在 S 上反复执行重复项删除操作直到无法继续删除。 ● 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路
● 使用栈遍历字符串如果栈空或元素不相等就入栈否则出栈 ● 最后遍历栈元素从尾部弹出返回字符串即可
代码
class Solution {public String removeDuplicates(String s) {DequeCharacter stack new ArrayDeque();for (int i 0; i s.length(); i) {if (stack.isEmpty() || stack.peek() ! s.charAt(i)) {stack.addFirst(s.charAt(i));} else {stack.removeFirst();}}StringBuilder builder new StringBuilder();while (!stack.isEmpty()) {builder.append(stack.removeLast());}return new String(builder);}
}150. 逆波兰表达式求值
● 力扣题目链接 ● 根据 逆波兰表示法求表达式的值。 ● 有效的运算符包括 , - , * , / 。每个运算对象可以是整数也可以是另一个逆波兰表达式。 ● 说明 ● 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数为 0 的情况。
思路
● 使用栈处理即可根据不同的情况入栈出栈
代码
class Solution {public int evalRPN(String[] tokens) {DequeInteger stack new ArrayDeque();for (String str : tokens) {if (str.equals()) {stack.addFirst(stack.removeFirst() stack.removeFirst());} else if (str.equals(-)) {int temp stack.removeFirst();stack.addFirst(stack.removeFirst() - temp);} else if (str.equals(*)) {stack.addFirst(stack.removeFirst() * stack.removeFirst());} else if (str.equals(/)) {int temp stack.removeFirst();stack.addFirst(stack.removeFirst() / temp);} else {stack.addFirst(Integer.parseInt(str));}}return stack.peekFirst();}
}
