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

2023/12/18

LeetCode每日一刷：20. 有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1
• s 仅由括号 '()[]{}' 组成

class Solution {
    private static final MapCharacter,Character> map = new HashMapCharacter,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};
    public boolean isValid(String s) {
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        LinkedListCharacter> stack = new LinkedListCharacter>() {{ 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) {
        // 创建一个栈
        StackCharacter> 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，表示输入字符串不是有效的括号序列。

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

以下是代码的逐行解释：

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，表示输入字符串不是一个有效的括号序列。

2023/12/19

LeetCode每日一刷：150. 逆波兰表达式求值（后缀表达式运算）

给你一个字符串数组 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[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

	//jdk新语法，不需要写break
    public int evalRPN(String[] tokens) {
        //定义一个栈数据结构
        LinkedListInteger> 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旧语法
        LinkedListInteger> 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());
        //定义一个栈，用于存放按照规定的优先级规律存放 运算符
        LinkedListCharacter> 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();
    }

---

LeetCode今日两刷： 232.双栈模拟队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

给LeetCode题目用的自实现栈，可以定义为静态内部类

class ArrayStackE> {

    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
        顶   底   底   顶
                 abc

        push(a)
        push(b)
        push(c)
        pop()
     */
    ArrayStackInteger> s1 = new ArrayStack>(100);
    ArrayStackInteger> 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 
    ArrayStackInteger> s1 = new ArrayStack>(100);
    ArrayStackInteger> 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 ArrayStackE>{
        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 {
    DequeInteger> inStack;
    DequeInteger> outStack;

    public MyQueue() {
        inStack = new ArrayDequeInteger>();
        outStack = new ArrayDequeInteger>();
    }

    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 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

---

2023/12/20

LeetCode每日一刷：225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（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
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

**进阶：**你能否仅用一个队列来实现栈。

提交代码：

class MyStack {

    ArrayQueue5Integer> queue = new ArrayQueue5>(100);
    private int size = 0;
    
    public void push(int x) {
        queue.offer(x);
        for(int i =0;isize;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 ArrayQueue5E>{
        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 
                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 {
    QueueInteger> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedListInteger>();
    }
    
    /** 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 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。

由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

2023/12/21

LeetCode每日一刷：103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[2服务器托管网0,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -100

public ListListInteger>> zigzagLevelOrder(TreeNode root) {
        //定义一个存放结果集的链表
        ListListInteger>> result = new ArrayList>();
        //如果根节点为空，则直接返回空结果集
        if (root == null) {
            return result;
        }
        //定义一个队列
        QueueTreeNode> queue = new LinkedList>();
        //将根节点放入队列
        queue.offer(root);
        //记录每层节点个数
        int c = 1;
        //记录层数，以便对不同层做不同操作
        boolean odd = true;//默认为奇数层
        //如果队列非空
        while (!queue.isEmpty()) {
            //定义一个变量记录下一层节点个数
            int n = 0;
            //定义一个双端队列，用来存放每一层的节点
            DequeInteger> 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>类型的结果。该方法的作用是按照zigzag顺序（即先从左到右，再从右到左）遍历二叉树的每一层，并将每一层的节点值存储在一个List类型的列表中。

以下是代码的详细解释：

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

此外，代码中还定义了一个名为TreeNode的类，用于表示二叉树的节点。该类包含一个整数值val，以及两个指向子节点的引用left和right。

2023/12/22

LeetCode每日一刷：23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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
• 0
• -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即可！

LeetCode每五日一总结【12/18–12/22】

2023/12/18

20. 20.有效的括号

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

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

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

2023/12/19

150. 150.逆波兰表达式求值（后缀表达式运算）

​	使用**栈**数据结构，遍历逆波兰表达式数组，将**非运算符字符**压入栈中，如果遍历到的元素为运算符，则将**栈中弹出两个元素进行运算操作**，最后**将运算结果再次压入栈中**，直到遍历完整个字符串，将栈中最后一个元素弹出并返回即可！

151. 联想思考：如何将中缀表达式转换为后缀表达式？

思路:

      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+*

152. 232.双栈模拟队列

思路：

将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。

每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

2023/12/20

1. 225.用队列实现栈

思路：

使用一个队列

使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。

入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。

由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

2023/12/21

103. 103.二叉树的锯齿形层序遍历

思路：

使用**队列**数据结构，先将二叉树的根节点入队，并定义一个变量记录二叉树每一层的节点个数，用于遍历每一层的节点，再定义一个双端队列，每次从队列出队的节点，根据层数的奇偶不同，选择从双端队列头部添加或者尾部添加，以此实现锯齿形层序遍历，判断如果从队列出队的节点存在左右孩子，则将其左右孩子入队列，循环此操作，直到队列为空。

2023/12/22

1. 23.合并 K 个升序链表小顶堆实现>

使用小顶堆数据结构，先将链表中的头节点全都加入小顶堆中，实例化一个新的链表【直接实例化一个新链表的哨兵节点即可】，定义一个指针，用来操作新链表，如果小顶堆不为空，则将小顶堆中poll出来的元素加入到新链表中，指针指向新的节点且将poll出来的节点的下一个节点再次加入到小顶堆（前提：下一节点存在），循环操作，直到小顶堆为空，说明已将全部节点转移到新链表，返回哨兵节点的next即可！

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net