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

发布时间:2023年12月24日


在这里插入图片描述

2023/12/18

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

给定一个只包括 '('')''{''}''['']' 的字符串 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 {
                    // 如果没有对应的左括号,则返回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.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();
    }

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

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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
  • 最多调用 100pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 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
        顶   底   底   顶
                 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/
来源:LeetCodeLeetCode

思路

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

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


2023/12/20

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

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

注意:

  • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis 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
  • 最多调用100pushpoptopempty
  • 每次调用 poptop 都保证栈不为空

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

提交代码

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 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列,此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。

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

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

2023/12/21

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

给你二叉树的根节点 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>类型的列表中。

以下是代码的详细解释:

  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,以及两个指向子节点的引用leftright

2023/12/22

LeetCode每日一刷:23. 合并 K 个升序链表<同12/09>

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

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

示例 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即可!

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

2023/12/18

  1. 20.有效的括号

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

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

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

2023/12/19

  1. 150.逆波兰表达式求值(后缀表达式运算)
?	使用**栈**数据结构,遍历逆波兰表达式数组,将**非运算符字符**压入栈中,如果遍历到的元素为运算符,则将**栈中弹出两个元素进行运算操作**,最后**将运算结果再次压入栈中**,直到遍历完整个字符串,将栈中最后一个元素弹出并返回即可!
  1. 联想思考:如何将中缀表达式转换为后缀表达式
思路:
      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+*

  1. 232.双栈模拟队列
思路:

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

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

2023/12/20

  1. 225.用队列实现栈

思路:

使用一个队列

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

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

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

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

2023/12/21

  1. 103.二叉树的锯齿形层序遍历
思路:

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

2023/12/22

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

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

文章来源:https://blog.csdn.net/guojiaqi_/article/details/135186384
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。