【算法提升—力扣每日一刷】五日总结【12/18--12/22】

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 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 {// 如果没有对应的左括号，则返回falsereturn false;}}}// 如果栈为空，则返回truereturn stack.isEmpty();}

这是一个 Java 代码，定义了一个名为 isValid 的方法，该方法接受一个字符串 s 作为输入，并返回一个布尔值，表示该字符串是否是一个有效的括号序列。

该方法使用一个堆栈来跟踪在输入字符串中遇到的 opening parentheses（括号、大括号）。当它遇到一个 opening parenthesis 时，将与之对应的 closing parenthesis 压入堆栈。如果它遇到一个 closing parenthesis，它会检查它是否与堆栈的顶部元素匹配。如果它匹配，它会从堆栈中弹出顶部元素。如果不匹配，它会返回 false，表示输入字符串不是有效的括号序列。

在处理完输入字符串中的所有字符后，该方法检查堆栈是否为空。如果为空，这意味着所有括号都已匹配，输入字符串是一个有效的括号序列。如果堆栈不为空，则表示存在未匹配的括号，输入字符串不是一个有效的括号序列。

以下是代码的逐行解释：

1. 创建一个名为 stack 的空堆栈。
2. 遍历输入字符串 s 中的每个字符 c。
3. 如果 c 是 opening parenthesis（(、[ 或 {），将与之对应的 closing parenthesis 压入堆栈（) 或 ] 或 }， respectively）。
4. 如果 c 是 closing parenthesis，检查它是否与堆栈的顶部元素匹配。
   • 如果它匹配，从堆栈中弹出顶部元素。
   • 如果它不匹配，返回 false，表示输入字符串不是有效的括号序列。
5. 如果 c 既不是 opening parenthesis 也不是 closing parenthesis，检查它是否与堆栈的顶部元素匹配。
   • 如果它匹配，从堆栈中弹出顶部元素。
   • 如果它不匹配，返回 false，表示输入字符串不是有效的括号序列。
6. 在处理完输入字符串中的所有字符后，检查堆栈是否为空。
   • 如果为空，返回 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新语法，不需要写breakpublic 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();}

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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;}
}

参考解答，注意：题目已说明

• 调用 push、pop 等方法的次数最多 100

public class E04Leetcode232 {/*队列头      队列尾s1       s2顶   底   底   顶abcpush(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 -> 32if ((capacity & capacity - 1) != 0) {int n = (int) ((Math.log10(capacity) / Math.log10(2)) + 1);//计算大于参数的最小2的n次方的ncapacity = 1 << n;  //左移运算符，相当于乘2 ， 1 << n相当于 2^nSystem.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++;}}//将下一层节点数赋值给cc = 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>类型的列表中。

以下是代码的详细解释：

1. 定义一个存放结果集的链表result，以及一个存放节点的队列queue。
2. 如果根节点为空，则直接返回空结果集。
3. 定义一个变量c来记录每层节点的个数，以及一个布尔变量odd来记录当前是奇数层还是偶数层。
4. 定义一个双端队列lever来存放每一层的节点。
5. 遍历当前层的每一个节点，将节点从队列中弹出，并将其值添加到lever队列中。如果是奇数层，则从队列尾部添加，即正序；如果是偶数层，则从队列头部添加，即逆序。
6. 如果当前节点的左孩子不为空，则将其加入队列queue中。如果当前节点的右孩子不为空，则将其加入队列queue中。
7. 计算下一层节点的个数n，并将队列queue中的节点个数赋值给c。
8. 将lever队列中的节点值组成一个List<Integer>类型的列表，并将其添加到结果集result中。
9. 更新odd变量，使其在奇数层和偶数层之间切换。
10. 循环执行步骤5到步骤9，直到队列为空。
11. 返回结果集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即可！