给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
提示:
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
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;
}
}
以上思路出自
作者:Krahets
链接:https://leetcode.cn/problems/valid-parentheses/
来源:LeetCode(LeetCode)
public boolean isValid(String s) {
// 创建一个栈
Stack<Character> stack = new Stack<>();
// 遍历字符串中的每一个字符
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 如果字符是左括号,则将右括号压入栈中
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
// 如果字符是右括号,则判断栈中是否有对应的左括号
if (!stack.isEmpty() && c == stack.peek()) {
stack.pop();
} else {
// 如果没有对应的左括号,则返回false
return false;
}
}
}
// 如果栈为空,则返回true
return stack.isEmpty();
}
这是一个 Java 代码,定义了一个名为
isValid
的方法,该方法接受一个字符串s
作为输入,并返回一个布尔值,表示该字符串是否是一个有效的括号序列。该方法使用一个堆栈来跟踪在输入字符串中遇到的 opening parentheses(括号、大括号)。当它遇到一个 opening parenthesis 时,将与之对应的 closing parenthesis 压入堆栈。如果它遇到一个 closing parenthesis,它会检查它是否与堆栈的顶部元素匹配。如果它匹配,它会从堆栈中弹出顶部元素。如果不匹配,它会返回
false
,表示输入字符串不是有效的括号序列。在处理完输入字符串中的所有字符后,该方法检查堆栈是否为空。如果为空,这意味着所有括号都已匹配,输入字符串是一个有效的括号序列。如果堆栈不为空,则表示存在未匹配的括号,输入字符串不是一个有效的括号序列。
以下是代码的逐行解释:
- 创建一个名为
stack
的空堆栈。- 遍历输入字符串
s
中的每个字符c
。- 如果
c
是 opening parenthesis((
、[
或{
),将与之对应的 closing parenthesis 压入堆栈()
或]
或}
, respectively)。- 如果
c
是 closing parenthesis,检查它是否与堆栈的顶部元素匹配。
- 如果它匹配,从堆栈中弹出顶部元素。
- 如果它不匹配,返回
false
,表示输入字符串不是有效的括号序列。- 如果
c
既不是 opening parenthesis 也不是 closing parenthesis,检查它是否与堆栈的顶部元素匹配。
- 如果它匹配,从堆栈中弹出顶部元素。
- 如果它不匹配,返回
false
,表示输入字符串不是有效的括号序列。- 在处理完输入字符串中的所有字符后,检查堆栈是否为空。
- 如果为空,返回
true
,表示输入字符串是一个有效的括号序列。- 如果不为空,返回
false
,表示输入字符串不是一个有效的括号序列。
给你一个字符串数组
tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意:
- 有效的算符为
'+'
、'-'
、'*'
和'/'
。- 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 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
提示:
1 <= tokens.length <= 104
tokens[i]
是一个算符("+"
、"-"
、"*"
或"/"
),或是在范围[-200, 200]
内的一个整数逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式,如
( 1 + 2 ) * ( 3 + 4 )
。- 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )
。逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成
1 2 + 3 4 + *
也可以依据次序计算出正确结果。- 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
//jdk新语法,不需要写break
public int evalRPN(String[] tokens) {
//定义一个栈数据结构
LinkedList<Integer> stack = new LinkedList<>();
//迭代字符串数组中的每一个元素
for (String s : tokens) {
switch (s) {
//如果当前字符为" + ",则将栈顶两个元素弹出,做和运算后再压入栈中
case "+" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a + b);
}
//如果当前字符串为" - ",则将栈顶两个元素弹出,做差运算后再压入栈中(注意弹栈顺序:先弹栈的做减数)
case "-" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
}
//如果当前字符串为" * ",则将栈顶两个元素弹出,做乘积运算后再压入栈中
case "*" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a * b);
}
//如果当前字符串为" / ",则将栈顶两个元素弹出,做除法运算后再压入栈中(注意弹栈顺序:先弹栈的做除数)
case "/" -> {
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
}
//如果当前字符串为非运算符,则转为int类型后,压入栈中
default -> {
stack.push(Integer.parseInt(s));
}
}
}
//最后将栈中最后一个也是唯一一个元素返回,即是后缀表达式运算结果
return stack.pop();
}
//jdk旧语法
LinkedList<Integer> stack = new LinkedList<>();
for (String s : tokens) {
switch (s) {
case "+": {
int b = stack.pop();
int a = stack.pop();
stack.push(a + b);
break;
}
case "-": {
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
break;
}
case "*": {
int b = stack.pop();
int a = stack.pop();
stack.push(a * b);
break;
}
case "/": {
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
break;
}
default: {
stack.push(Integer.parseInt(s));
}
}
}
return stack.pop();
}
思路: 1. 遇到非运算符 直接拼串 2. 遇到 + - * / - 它的优先级比栈顶运算符高, 入栈, 如: 栈中是 + 当前是 * - 否则把栈里优先级 >= 它 的都出栈, 它再入栈, 如: 栈中是 +*, 当前是 - 3. 遍历完成, 栈里剩余运算符依次出栈 4. 如果带() - 左括号直接入栈, 左括号优先设置为0 - 右括号就把栈里到左括号为止的所有运算符出栈 | | | | | | _____ a+b ab+ a+b-c ab+c- a*b+c ab*c+ a+b*c abc*+ a+b*c-d abc*+d- (a+b)*c ab+c* (a+b*c-d)*e abc*+d-e* a*(b+c) abc+*
//计算优先级
static int priority(char c) {
return switch (c) {
case '+', '-' -> 1; // + - 优先级为 1
case '*', '/' -> 2; // * / 优先级为 2
case '(' -> 0;
default -> throw new IllegalArgumentException("输入的参数不合法 " + c);
};
}
static String infixToSuffix(String exp) {
//定义一个StringBuilder字符串变量,用于拼接结果集字符串
StringBuilder result = new StringBuilder(exp.length());
//定义一个栈,用于存放按照规定的优先级规律存放 运算符
LinkedList<Character> stack = new LinkedList<>();
//遍历字符串参数(中缀表达式)
for (int i = 0; i < exp.length(); i++) {
//取到表达式中的每一个字符
char c = exp.charAt(i);
//如果取到的字符为运算符或者括号,则根据规则入栈或者出栈,如果取到的字符是非运算符和括号,则直接参与字符串拼接
switch (c) {
case '+', '-', '*', '/' -> {
//如果栈是空的,则直接将字符串压入栈中
if (stack.isEmpty()) {
stack.push(c);
} else {
//如果栈非空,则判断当前运算符的优先级及栈顶运算符优先级,如果当前运算符优先级高于栈顶运算符优先级,则将当前运算符压人栈
if (priority(c) > priority(stack.peek())) {
stack.push(c);
} else {//如果当前运算符优先级小于或等于栈顶运算符优先级,则将栈顶运算符弹栈后拼接到结果集字符串中,并循环比较,如果栈被弹空,停止循环
while (!stack.isEmpty() && priority(c) <= priority(stack.peek())) {
result.append(stack.pop());
}
//最后将当前运算符压入栈中
stack.push(c);
}
}
}//如果当前字符为左括号,则直接压入栈中
case '(' -> {
stack.push('(');
}//如果当前运算符是右括号,则将栈中左括号上面的所有运算符弹栈后拼接到结果集字符串中
case ')' -> {
while (!stack.isEmpty()&& stack.peek()!='('){
result.append(stack.pop());
}
//最后将左括号从栈中弹出
stack.pop();
}
//字符为非运算符,直接拼接到结果集字符串中
default -> result.append(c);
}
}
//当字符串中每个字符都被迭代后,将栈中还未弹栈的运算符弹出并拼接到结果集字符串中
while (!stack.isEmpty()){
result.append(stack.pop());
}
//返回StringBuilder的toString字符串类型
return result.toString();
}
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(
push
、pop
、peek
、empty
):实现
MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
说明:
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
示例 1:
输入: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 1, 1, false] 解释: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
提示:
1 <= x <= 9
- 最多调用
100
次push
、pop
、peek
和empty
- 假设所有操作都是有效的 (例如,一个空的队列不会调用
pop
或者peek
操作)进阶:
- 你能否实现每个操作均摊时间复杂度为
O(1)
的队列?换句话说,执行n
个操作的总时间复杂度为O(n)
,即使其中一个操作可能花费较长时间。
给LeetCode题目用的自实现栈,可以定义为静态内部类
class ArrayStack<E> {
private E[] array;
private int top; // 栈顶指针
@SuppressWarnings("all")
public ArrayStack(int capacity) {
this.array = (E[]) new Object[capacity];
}
public boolean push(E value) {
if (isFull()) {
return false;
}
array[top++] = value;
return true;
}
public E pop() {
if (isEmpty()) {
return null;
}
return array[--top];
}
public E peek() {
if (isEmpty()) {
return null;
}
return array[top - 1];
}
public boolean isEmpty() {
return top == 0;
}
public boolean isFull() {
return top == array.length;
}
}
参考解答,注意:题目已说明
public class E04Leetcode232 {
/*
队列头 队列尾
s1 s2
顶 底 底 顶
abc
push(a)
push(b)
push(c)
pop()
*/
ArrayStack<Integer> s1 = new ArrayStack<>(100);
ArrayStack<Integer> s2 = new ArrayStack<>(100);
public void push(int x) {
s2.push(x);
}
public int pop() {
if (s1.isEmpty()) {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.pop();
}
public int peek() {
if (s1.isEmpty()) {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
提交版代码:
class MyQueue
ArrayStack<Integer> s1 = new ArrayStack<>(100);
ArrayStack<Integer> s2 = new ArrayStack<>(100);
public void push(int x) {
s1.push(x);
}
public int pop() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
static class ArrayStack<E>{
private final E[] stack;
private int top;
@SuppressWarnings("ALL")
public ArrayStack(int capacity) {
stack = (E[]) new Object[capacity];
}
public boolean push(E value) {
if (isFull()) {
return false;
}
stack[top++] = value;
return true;
}
public E pop() {
if(isEmpty()){
return null;
}
return stack[--top];
}
public E peek() {
if(isEmpty()){
return null;
}
return stack[top-1];
}
public boolean isEmpty() {
return top == 0;
}
public boolean isFull() {
return top == stack.length;
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
LeetCode官方题解:
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new ArrayDeque<Integer>();
outStack = new ArrayDeque<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
//将输入栈中的元素弹栈并压入输出栈
private void in2out() {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
作者:LeetCode官方题解
链接:https://leetcode.cn/problems/implement-queue-using-stacks/
来源:LeetCode(LeetCode)
思路
将一个栈当作输入栈,用于压入 push 传入的数据;另一个栈当作输出栈,用于 pop 和 peek 操作。
每次 pop 或 peek 时,若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(
push
、top
、pop
和empty
)。实现
MyStack
类:
void push(int x)
将元素 x 压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回true
;否则,返回false
。注意:
- 你只能使用队列的基本操作 —— 也就是
push to back
、peek/pop from front
、size
和is empty
这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
输入: ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 2, 2, false] 解释: MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
提示:
1 <= x <= 9
- 最多调用
100
次push
、pop
、top
和empty
- 每次调用
pop
和top
都保证栈不为空**进阶:**你能否仅用一个队列来实现栈。
提交代码:
class MyStack {
ArrayQueue5<Integer> queue = new ArrayQueue5<>(100);
private int size = 0;
public void push(int x) {
queue.offer(x);
for(int i =0;i<size;i++){
queue.offer(queue.poll());
}
size++;
}
public int pop() {
size--;
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
static class ArrayQueue5<E>{
private final E[] array;
int head = 0;
int tail = 0;
@SuppressWarnings("all")
public ArrayQueue5(int capacity) {
/*//抛异常
if ((capacity & capacity - 1) != 0) {
throw new IllegalArgumentException("请传入容量为2的N次方的容量参数");
}*/
//增大容量为大于当前参数的最小2的n次方 13 -> 16 22 -> 32
if ((capacity & capacity - 1) != 0) {
int n = (int) ((Math.log10(capacity) / Math.log10(2)) + 1);//计算大于参数的最小2的n次方的n
capacity = 1 << n; //左移运算符,相当于乘2 , 1 << n相当于 2^n
System.out.println(capacity);
}
array = (E[]) new Object[capacity];
}
public boolean offer(E value) {
if (isFull()) {
return false;
}
//使用位运算,规律:当一个数对2的整数次的数取模时,余数=这个数 &(按位与) 2的整数次-1
// 666 % 8 = 666 & 7
/*
求模运算:
- 如果除数是 2 的 n 次方
- 那么被除数的后 n 位即为余数 (模)
- 求被除数的后 n 位方法: 与 2^n-1 按位 与
*/
array[tail & array.length - 1] = value;
tail++;
return true;
}
public E poll() {
if (isEmpty()) {
return null;
}
E value = array[head & array.length - 1];
head++;
return value;
}
public E peek() {
if (isEmpty()) {
return null;
}
E value = array[head & array.length - 1];
return value;
}
public boolean isEmpty() {
return tail == head;
}
public boolean isFull() {
return (tail - head) == array.length;
}
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
官方题解:
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
一个队列
方法一使用了两个队列实现栈的操作,也可以使用一个队列实现栈的操作。使用一个队列时,为了满足栈的特性,即最后入栈的元素最先出栈,同样需要满足队列前端的元素是最后入栈的元素。
入栈操作时,首先获得入栈前的元素个数 n,然后将元素入队到队列,再将队列中的前 n 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列,此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保队列的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可,获得栈顶元素操作只需要获得队列的前端元素并返回即可(不移除元素)。
由于队列用于存储栈内的元素,判断栈是否为空时,只需要判断队列是否为空即可。
给你二叉树的根节点
root
,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[20,9],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内-100 <= Node.val <= 100
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
//定义一个存放结果集的链表
List<List<Integer>> result = new ArrayList<>();
//如果根节点为空,则直接返回空结果集
if (root == null) {
return result;
}
//定义一个队列
Queue<TreeNode> queue = new LinkedList<>();
//将根节点放入队列
queue.offer(root);
//记录每层节点个数
int c = 1;
//记录层数,以便对不同层做不同操作
boolean odd = true;//默认为奇数层
//如果队列非空
while (!queue.isEmpty()) {
//定义一个变量记录下一层节点个数
int n = 0;
//定义一个双端队列,用来存放每一层的节点
Deque<Integer> lever = new LinkedList<>();
//遍历当前层的每一个节点
for (int i = 0; i < c; i++) {
//将节点从队列中弹出
TreeNode treeNode = queue.poll();
if(odd){//如果为奇数层,则从尾部添加,正序
lever.offerLast(treeNode.val);
}else {//如果是偶数层,则从头部添加,逆序
lever.offerFirst(treeNode.val);
}
//如果节点有左孩子,则加入队列
if (treeNode.left != null) {
queue.offer(treeNode.left);
n++;
}
//如果节点有右孩子,则加入队列
if (treeNode.right != null) {
queue.offer(treeNode.right);
n++;
}
}
//将下一层节点数赋值给c
c = n;
//将每一层的节点组成的双端队列转换为链表加入到结果集
result.add(new LinkedList<>(lever));
//层数取反,奇数层变偶数层 偶数层变奇数层
odd=!odd;
}
return result;
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
这段Java代码定义了一个名为
zigzagLevelOrder
的方法,该方法接受一个TreeNode
类型的参数root
,并返回一个List<List<Integer>>
类型的结果。该方法的作用是按照zigzag顺序(即先从左到右,再从右到左)遍历二叉树的每一层,并将每一层的节点值存储在一个List<Integer>
类型的列表中。以下是代码的详细解释:
- 定义一个存放结果集的链表
result
,以及一个存放节点的队列queue
。- 如果根节点为空,则直接返回空结果集。
- 定义一个变量
c
来记录每层节点的个数,以及一个布尔变量odd
来记录当前是奇数层还是偶数层。- 定义一个双端队列
lever
来存放每一层的节点。- 遍历当前层的每一个节点,将节点从队列中弹出,并将其值添加到
lever
队列中。如果是奇数层,则从队列尾部添加,即正序;如果是偶数层,则从队列头部添加,即逆序。- 如果当前节点的左孩子不为空,则将其加入队列
queue
中。如果当前节点的右孩子不为空,则将其加入队列queue
中。- 计算下一层节点的个数
n
,并将队列queue
中的节点个数赋值给c
。- 将
lever
队列中的节点值组成一个List<Integer>
类型的列表,并将其添加到结果集result
中。- 更新
odd
变量,使其在奇数层和偶数层之间切换。- 循环执行步骤5到步骤9,直到队列为空。
- 返回结果集
result
。此外,代码中还定义了一个名为
TreeNode
的类,用于表示二叉树的节点。该类包含一个整数值val
,以及两个指向子节点的引用left
和right
。
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2:
输入:lists = [] 输出:[]
示例 3:
输入:lists = [[]] 输出:[]
提示:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i]
按 升序 排列lists[i].length
的总和不超过10^4
/**
* 小顶堆
*/
public class MinHeap {
ListNode[] array;
int size;
public MinHeap(int capacity) {
array = new ListNode[capacity];
}
public boolean offer(ListNode value) {
if (isFull()) {
return false;
}
int child = size++;
int father = (child - 1) / 2;
while (child > 0 && value.val < array[father].val) {
array[child] = array[father];
child = father;
father = (child - 1) / 2;
}
array[child] = value;
return true;
}
public ListNode poll() {
if (isEmpty()) {
return null;
}
//1.交换堆顶元素与最后一个元素,删除最后一个元素
swap(0, size - 1);
size--;
ListNode e = array[size];
array[size] = null;// help GC
//2.将推顶元素与其孩子不断比较,到他合适位置
down(0);
return e;
}
private void down(int father) {
int left = father * 2 + 1;
int right = left + 1;
int min = father;// 假设父元素最小
if (left < size && array[left].val < array[min].val) {
min = left;
}
if (right < size && array[right].val < array[min].val) {
min = right;
}
if (min != father) {// 说明发生了交换,则有孩子比父亲大
swap(min, father);
down(min);
}
}
private void swap(int i, int j) {
ListNode t = array[j];
array[j] = array[i];
array[i] = t;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == array.length;
}
}
//使用小顶堆解决
public ListNode mergeKLists(ListNode[] lists) {
/* p1
* 1 5 9 7 null
* p2
* 5 6 8 9 null
* p3
* 3 5 7 8 null
*
小顶堆: 1 5 3
空链表 null->
*/
MinHeap minHeap = new MinHeap(lists.length);
for (ListNode h : lists) {
if (h != null) {
minHeap.offer(h);
}
}
//新链表的哨兵节点
ListNode s = new ListNode(-1, null);
ListNode p = s;
while (!minHeap.isEmpty()) {
ListNode min = minHeap.poll();
p.next = min;
p = min;
if(min.next!=null){
minHeap.offer(min.next);//将链表的下一个节点加入小顶堆
}
}
return s;
}
使用小顶堆数据结构,先将链表中的头节点都加入小顶堆中,实例化一个新的链表【直接实例化一个新链表的哨兵节点即可】,定义一个指针,用来操作新链表,如果小顶堆不为空,则将小顶堆中poll出来的元素加入到新链表中,指针指向新的节点且将poll出来的节点的下一个节点再次加入到小顶堆(前提:下一节点存在),循环操作,直到小顶堆为空,说明已将全部节点转移到新链表,返回哨兵节点的next即可!
2023/12/18
- 20.有效的括号
? 定义一个名为
isValid
的方法,该方法接受一个字符串s
作为输入,并返回一个布尔值,表示该字符串是否是一个有效的括号序列。? 该方法使用一个堆栈来跟踪在输入字符串中遇到的 opening parentheses(括号、大括号)。当它遇到一个 opening parenthesis 时,将与之对应的 closing parenthesis 压入堆栈。如果它遇到一个 closing parenthesis,它会检查它是否与堆栈的顶部元素匹配。如果它匹配,它会从堆栈中弹出顶部元素。如果不匹配,它会返回
false
,表示输入字符串不是有效的括号序列。? 在处理完输入字符串中的所有字符后,该方法检查堆栈是否为空。如果为空,这意味着所有括号都已匹配,输入字符串是一个有效的括号序列。如果堆栈不为空,则表示存在未匹配的括号,输入字符串不是一个有效的括号序列。
2023/12/19
- 150.逆波兰表达式求值(后缀表达式运算)
? 使用**栈**数据结构,遍历逆波兰表达式数组,将**非运算符字符**压入栈中,如果遍历到的元素为运算符,则将**栈中弹出两个元素进行运算操作**,最后**将运算结果再次压入栈中**,直到遍历完整个字符串,将栈中最后一个元素弹出并返回即可!
- 联想思考:如何将中缀表达式转换为后缀表达式?
思路:
1. 遇到非运算符 直接拼串 2. 遇到 + - * / - 它的优先级比栈顶运算符高, 入栈, 如: 栈中是 + 当前是 * - 否则把栈里优先级 >= 它 的都出栈, 它再入栈, 如: 栈中是 +*, 当前是 - 3. 遍历完成, 栈里剩余运算符依次出栈 4. 如果带() - 左括号直接入栈, 左括号优先设置为0 - 右括号就把栈里到左括号为止的所有运算符出栈 | | | | | | _____ a+b ab+ a+b-c ab+c- a*b+c ab*c+ a+b*c abc*+ a+b*c-d abc*+d- (a+b)*c ab+c* (a+b*c-d)*e abc*+d-e* a*(b+c) abc+*
- 232.双栈模拟队列
思路: 将一个栈当作输入栈,用于压入 push 传入的数据;另一个栈当作输出栈,用于 pop 和 peek 操作。 每次 pop 或 peek 时,若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
2023/12/20
- 225.用队列实现栈
思路:
使用一个队列
使用一个队列时,为了满足栈的特性,即最后入栈的元素最先出栈,同样需要满足队列前端的元素是最后入栈的元素。
入栈操作时,首先获得入栈前的元素个数 n,然后将元素入队到队列,再将队列中的前 n 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列,此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保队列的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可,获得栈顶元素操作只需要获得队列的前端元素并返回即可(不移除元素)。
由于队列用于存储栈内的元素,判断栈是否为空时,只需要判断队列是否为空即可。
2023/12/21
- 103.二叉树的锯齿形层序遍历
思路: 使用**队列**数据结构,先将二叉树的根节点入队,并定义一个变量记录二叉树每一层的节点个数,用于遍历每一层的节点,再定义一个双端队列,每次从队列出队的节点,根据层数的奇偶不同,选择从双端队列头部添加或者尾部添加,以此实现锯齿形层序遍历,判断如果从队列出队的节点存在左右孩子,则将其左右孩子入队列,循环此操作,直到队列为空。
2023/12/22
- 23.合并 K 个升序链表<小顶堆实现>
使用小顶堆数据结构,先将链表中的头节点全都加入小顶堆中,实例化一个新的链表【直接实例化一个新链表的哨兵节点即可】,定义一个指针,用来操作新链表,如果小顶堆不为空,则将小顶堆中poll出来的元素加入到新链表中,指针指向新的节点且将poll出来的节点的下一个节点再次加入到小顶堆(前提:下一节点存在),循环操作,直到小顶堆为空,说明已将全部节点转移到新链表,返回哨兵节点的next即可!