【每日一题】【栈和队列、双端队列】20. 有效的括号/NC52 有效括号序列-211127/220126
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
//stack不是抽象类
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(Character c : s.toCharArray()) {
if(c == '{') {
stack.push('}');
} else if(c == '(') {
stack.push(')');
} else if(c == '[') {
stack.push(']');
} else if(stack.isEmpty() || c != stack.pop()) {
return false;
}
}
return stack.isEmpty(); //不是直接return true,而是看栈是否为空
}
}
同上解法
import java.util.*;
public class Solution {
public boolean isValid (String s) {
char[] arr = s.toCharArray();
//栈的初始化,后进先出
Stack<Character> stack = new Stack<>();
char str = ' ';
for(char c : arr) {
if (!stack.isEmpty()) {
str = stack.peek();
}
if(c == '[') {
stack.add(']');
} else if(c == '{') {
stack.add('}');
} else if(c == '(') {
stack.add(')');
} else if(!stack.isEmpty() && c == stack.peek()) {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
}
注意:
1、栈
初始化:Stack<E> stack = new Stack<>();
出栈:stack.pop() 或 stack.remove(stack.size() - 1)
入栈:stack.push(2) 或 stack.add(1)
栈顶:stack.peek()
2、队列
初始化:Queue<E> queue = new LinkedList<>();
入队:queue.offer(2) 或 queue.add(3)
出队:queue.poll() 或 queue.remove()
查看队头元素:queue.peek()
3、双端队列
初始化:
Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> deque1 = new LinkedList<>();
入队:
deque1.addFirst(1);
deque1.addLast(2);
deque1.offerFirst(3);
deque1.offerLast(4);
出队:
deque1.removeFirst()
deque1.removeLast()
deque1.pollFirst()
deque1.pollLast()
查看队头元素:
deque1.peekFirst()
deque1.peekLast()
4、测试
public static void main(String[] args) {
//System.out.println(isValid("([])"));
//testQueue();
testStack();
} public static void testDeque() {
//双端队列
Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> deque1 = new LinkedList<>();
//入队
deque1.addFirst(1);
deque1.addLast(2);
deque1.offerFirst(3);
deque1.offerLast(4);
System.out.println(deque1.peekFirst());
System.out.println(deque1.peekLast());
//出队
System.out.println(deque1.removeFirst());
System.out.println(deque1.removeLast());
System.out.println(deque1.pollFirst());
System.out.println(deque1.pollLast()); }
public static void testQueue() {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.add(3);
System.out.println(queue.peek());
System.out.println(queue.poll());
System.out.println(queue.peek());
System.out.println(queue.remove());
System.out.println(queue.peek());
} public static void testStack() {
Stack<Integer> stack = new Stack<>();
stack.add(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.peek());
System.out.println(stack.remove(stack.size() - 1));
System.out.println(stack.peek());
}
public static void testDeque() {
//双端队列
Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> deque1 = new LinkedList<>();
//入队
deque1.addFirst(1);
deque1.addLast(2);
deque1.offerFirst(3);
deque1.offerLast(4);
System.out.println(deque1.peekFirst());
System.out.println(deque1.peekLast());
//出队
System.out.println(deque1.removeFirst());
System.out.println(deque1.removeLast());
System.out.println(deque1.pollFirst());
System.out.println(deque1.pollLast());
}
最新文章
- 邮件开发——base64账号密码转换
- suse linux 命令
- 安卓模拟器研究-root
- 如何禁止DELETE、PUT、OPTIONS、TRACE、HEAD等协议访问应用程序 .
- Java 多线程Thread和Runnable
- 【转】BUG敏感度的培养
- Android Camera 流程梳理
- jQuery delegate方法实现Ajax请求绑定事件不丢失
- Prototypes analyze(二叉排序树,不同树形个数)
- vue实例讲解之vuex的使用
- vue-resource传参数到后端,后端取不到数据的问题
- python爬虫之获取验证码登陆
- oracle实用基础
- npm安装删除模块以及cnpm淘宝镜像
- buffer格式的转换
- 如何推进企业流程体系建设?_K2 BPM
- sql server 报错处理
- PHP7 网络编程(五)进程间通信【待】
- nativefier(一行代码将任意网页转化为桌面应用)
- Python-str-操作-6