Hedon

# 栈丨队列

# 总结

  • 栈：深度优先 DFS
  • 队列：广度优先遍历 BFS
    • 树：层次遍历
    • 图：无权图的最短路径

# Java 中的栈和队列

Java 有专门的 Stack 类可以做栈。

Java 还有 Queue 可以做队列，其中 PriorityQueue 可以做优先级队列。

Java 中的 LinkedList 即可当链表，也可以当栈和队列。

栈

  • E peek(): 查看栈顶的值，但是不弹出
  • E pop(): 弹出栈顶的值
  • void push(E e): 将 e 压入栈

队列

  • void offer(E e): 将 e 入队
  • E peek(): 查看队头的值，但是不出队
  • E poll(): 出队

优先队列

  • 默认是小顶堆，也就是最小的出队

# 栈的使用

# Leetcode 20 Valid Parentheses

https://leetcode-cn.com/problems/valid-parentheses/

对于一一匹配的问题，而且是就近匹配，就可以考虑到使用栈了。具体思路如下：

  1. 遍历 s 的每一个字符，如果遇到右括号，就检查栈顶是否是其对应的左括号，如果不是，就不对称；
  2. 遍历完 s 后看看栈是否为空，如果还不为空，就说明不对称。
class Solution {
    public boolean isValid(String s) {

        // 栈
        LinkedList<Character> stack = new LinkedList<>();

        for(int i=0; i<s.length(); i++){
            char c  = s.charAt(i);
            switch (c) {
                case ')':
                    if(stack.size() <= 0) {
                        return false;
                    }
                    Character v1 = stack.pop();
                    if(!v1.equals('(')) {
                        return false;
                    }
                    break;
                case ']':
                    if(stack.size() <= 0) {
                        return false;
                    }
                    Character v2 = stack.pop();
                    if(!v2.equals('[')) {
                        return false;
                    }
                    break;
                case '}':
                    if(stack.size() <= 0) {
                        return false;
                    }
                    Character v3 = stack.pop();
                    if(!v3.equals('{')) {
                        return false;
                    }
                    break;
                default:
                    stack.push(c);
            }
        }

        return stack.size() == 0;
    }
}

# Leetcode 150 Evaluate Reverse Polish Notation

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

本题又称后缀表达式，是栈的一种典型应用。具体思路：

  1. 遇到数字直接入栈；
  2. 遇到运算符，就弹出两个值进行相应的运算，再将运算结果入栈；
  3. 最终结果就是栈顶的值。
class Solution {
    public int evalRPN(String[] tokens) {

        // 栈
        LinkedList<Integer> stack = new LinkedList<>();

        Integer num1 = null;
        Integer num2 = null;

        for(int i=0; i<tokens.length; i++){
            String token = tokens[i];

            switch(token){
                // 遇到运算符就出栈两个元素计算然后再入栈
                // 因为题目保证合法了，所以就不需要考虑异常情况
                case "+":
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num1 + num2);
                    break;
                case "-":
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num2 - num1);
                    break;
                case "*":
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num1 * num2);
                    break;
                case "/":
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num2 / num1);
                    break;
                default:
                    // 数字直接入栈
                    stack.push(Integer.valueOf(token));
            }
        }

				// 题目保证合法
      	// 所以最后栈顶就是运算结果
        return stack.pop();
    }
}

# 栈与递归

递归的本质就是栈。

# Leetcode 144 Binary Tree Preorder Traversal

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

思路：

  • 节点
  • 遍历左子树
  • 遍历右子树
  • （栈的话，因为是先进后出，所以需要让右子树先入栈，然后再入栈左子树）

递归：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        help(root, result);
        return result;
    }

    public void help(TreeNode node, List<Integer> result){
        if(node == null){
            return;
        }
      	// 节点
        result.add(node.val);
      	// 左子树
        help(node.left, result);
      	// 右子树
        help(node.right, result);
    }
}

非递归：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new LinkedList<>();

        if(root == null){
            return result;
        }

        // 根节点入栈
        stack.push(root);

        // 栈不空就一直循环下去
        while(stack.size() != 0){
            // 弹出栈顶
            TreeNode node = stack.pop();
            // 节点
            result.add(node.val);
          	// 栈先进后出，所以要颠倒顺序，先右后左
            // 右子树
            if(node.right != null){
                stack.push(node.right);
            }
            // 左子树
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

栈模拟递归：

定义一个 StackInfo 来模拟程序底层的栈帧，保存当前栈帧的操作信息：

  • op：操作指令，print 表示输出，go 表示进行遍历；
  • node：当前结点
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res ;
        }

        LinkedList<StackInfo> stack = new LinkedList<>();
        stack.push(new StackInfo("go", root));

        while (stack.size()!=0) {

            StackInfo info = stack.pop();

            switch (info.op) {
                case "print":
                    // 访问
                    res.add(info.node.val);
                    break;
                case "go":
                    // 前序遍历
                    // 栈是后进先出，所以记得倒一下顺序 右 - 左 - 中
                    // 右
                    if (info.node.right != null) {
                        stack.push(new StackInfo("go", info.node.right));
                    }
                    // 左
                    if (info.node.left != null) {
                        stack.push(new StackInfo("go", info.node.left));
                    }
                    // 中
                    stack.push(new StackInfo("print", info.node));
            }

        }

        return res;

    }
}

// op:
//  - print 表示访问
//  - go 表示操作，即对该 node 进行遍历
class StackInfo {
    String op;
    TreeNode node;
    public StackInfo(String op, TreeNode node) {
        this.op = op;
        this.node = node;
    }
}

# Leetcode 94 Binary Tree Inorder Traversal

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

思路：

  • 左子树
  • 根节点
  • 右子树

递归：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        help(root, result);
        return result;
    }

    public void help(TreeNode node, List<Integer> result){
        if(node == null){
            return;
        }
      	// 左子树
        help(node.left, result);
      	// 节点
        result.add(node.val);
      	// 右子树
        help(node.right, result);
    }
}

使用栈模拟递归：

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res ;
        }

        LinkedList<StackInfo> stack = new LinkedList<>();
        stack.push(new StackInfo("go", root));

        while (stack.size()!=0) {

            StackInfo info = stack.pop();

            switch (info.op) {
                case "print":
                    // 访问
                    res.add(info.node.val);
                    break;
                case "go":
                    // 中序遍历
                    // 栈是后进先出，所以记得倒一下顺序 右 - 中 - 左
                    // 右
                    if (info.node.right != null) {
                        stack.push(new StackInfo("go", info.node.right));
                    }
                		// 中
                    stack.push(new StackInfo("print", info.node));
                    // 左
                    if (info.node.left != null) {
                        stack.push(new StackInfo("go", info.node.left));
                    }
            }

        }

        return res;

    }
}

// op:
//  - print 表示访问
//  - go 表示操作，即对该 node 进行遍历
class StackInfo {
    String op;
    TreeNode node;
    public StackInfo(String op, TreeNode node) {
        this.op = op;
        this.node = node;
    }
}

常规非递归：

  1. 一直找到最左边，期间的节点全部入栈；
  2. 弹出栈顶，这个时候就最左边那棵没有左右子树的子树的中间点了，直接进 result；
  3. 然后转向右子树，再一直找最左边；
  4. 循环，直到栈不为空即可。
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {

        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new LinkedList<>();

        TreeNode temp = root;

        // 一直找到左下角
        // 期间全部入栈
        while(temp != null){
            stack.push(temp);
            temp = temp.left;
        }

        // 栈不为空就一直循环
        while(stack.size() != 0){
            // 已经是最左边了
            TreeNode node = stack.pop();
            // 中间
            result.add(node.val);
            // 转向右边，继续寻找最左边
            TreeNode right = node.right;
            while(right != null){
                stack.push(right);
                right = right.left;
            }
        }

        return result;
    }
}

# Leetcode 145 Binary Tree Postorder Traversal

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

思路：

  • 左子树
  • 右子树
  • 根节点

递归：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        help(root, result);
        return result;
    }

    public void help(TreeNode node, List<Integer> result){
        if(node == null){
            return;
        }
        // 左子树
        help(node.left, result);
        // 右子树
        help(node.right, result);
        // 节点
        result.add(node.val);
    }
}

常规非递归：

因为后序遍历会对根节点进行多次访问，所以我们需要避免对根节点的重复输出，所以需要引入一个变量 pre，来记录上一次输出的节点，只有两种情况才可以输出当前节点：

  1. 没有右子树，也就是当前节点是叶子节点，直接输出；
  2. 上一个输出的节点 pre 是该节点的右子树，也就是该节点的右边已经输出过了，所以就可以输出当前节点
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new LinkedList<>();

        // 一直走到最左边
        // 途中所有节点入栈
        while(root != null){
            stack.push(root);
            root = root.left;
        }

        // 用来避免重复输出节点
        TreeNode pre = null;

        // 栈不为空则循环
        while(stack.size() != 0){

            // 弹出栈顶
            TreeNode node = stack.pop();

          	// 可以直接输出的两种情况
          	// ① 没有右子树，也就是当前节点是叶子节点，直接输出
          	// ② 上一个输出的节点是该节点的右子树，也就是该节点的右边已经输出过了
            if(node.right == null || node.right == pre){
                result.add(node.val);
                pre = node;
                continue;
            }
						
          	// 不输出的话，需要重复入栈
            stack.push(node);
          
          	// 转到右子树，继续往左走
            node = node.right;
            while(node != null){
                stack.push(node);
                node = node.left;
            }
        }
        return result;
    }

}

用栈模拟递归：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res ;
        }

        LinkedList<StackInfo> stack = new LinkedList<>();
        stack.push(new StackInfo("go", root));

        while (stack.size()!=0) {

            StackInfo info = stack.pop();

            switch (info.op) {
                case "print":
                    // 访问
                    res.add(info.node.val);
                    break;
                case "go":
                    // 后续遍历
                    // 栈是后进先出，所以记得倒一下顺序 中 -  右 - 左
                		// 中
                    stack.push(new StackInfo("print", info.node));
                    // 右
                    if (info.node.right != null) {
                        stack.push(new StackInfo("go", info.node.right));
                    }
                    // 左
                    if (info.node.left != null) {
                        stack.push(new StackInfo("go", info.node.left));
                    }
            }

        }

        return res;

    }
}

// op:
//  - print 表示访问
//  - go 表示操作，即对该 node 进行遍历
class StackInfo {
    String op;
    TreeNode node;
    public StackInfo(String op, TreeNode node) {
        this.op = op;
        this.node = node;
    }
}

# Leetcode 341 Platten Nested List Iterator

https://leetcode.cn/problems/flatten-nested-list-iterator/

读懂题目后发现就是一个递归问题：

  1. Integer：直接入队；
  2. nestednterger：递归该 NestedInteger；

递归：

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    // 队列，先进先出
    // 也可以是栈，然后反向入栈
    LinkedList<Integer> queue = new LinkedList<>();


    // 辅助函数，用来递归
    public void add(List<NestedInteger> nestedList) {
        for(NestedInteger ni: nestedList) {
            if(ni.isInteger()){
                queue.add(ni.getInteger());	// 递归出口
            }else {
                add(ni.getList()); // 递归
            }
        }
    }

    public NestedIterator(List<NestedInteger> nestedList) {
        add(nestedList);
    }

    @Override
    public Integer next() {
        return queue.poll();
    }

    @Override
    public boolean hasNext() {
        return queue.size() > 0;
    }
}

非递归：

  • 那就得用栈来实现递归思路了。
  • 栈的话，因为是先进后出，所以需要反向操作。
  • 整体思路就是，我们用一个栈来存储 NestedInteger，当调用要访问 next 的时候，我们需要让栈顶的元素是整数：
    • 如果本来就是，那就直接让用户访问；
    • 如果不是，那就是 List<NestedInteger> 那就要需要对该链表再次按照之前的方式，方向入栈，然后再看看栈顶是不是整数；
    • 依此循环，直到栈顶是整数的时候，就可以返回给用户了。
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    // 栈：后进先出
    // 需要反向入队
    LinkedList<NestedInteger> stack = new LinkedList<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for(int i=nestedList.size()-1; i>=0;i--){
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        // 取出栈顶
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        if (stack.size() == 0) {
            return false;
        }

        // 取出栈顶，如果是整数，那就直接返回 true 给调用方去访问 next 即可
        NestedInteger data = stack.pop();
        if(data.isInteger()){
            stack.push(data);   // 放回去
            return true;
        }

        // 如果不是整数，那就得进去找到整数了，思路跟初始化的时候一样，反向入栈
        while(!data.isInteger()){
            List<NestedInteger> l = data.getList();
            // 反向入栈
            for(int i=l.size()-1; i>=0; i--) {
                stack.push(l.get(i));
            }
            // 注意，NestedInteger 可能啥也没有 -> []
            if(stack.size() == 0){
                return false;
            }
            // 再取出栈顶元素，再次尝试是否是整数，是否能给调用方调用
            data = stack.pop();
        }

        stack.push(data);   // 放回去
        return true;
    }
}

# 队列的使用

# Leetcode 102

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

层次遍历的问题，一般我们都用队列解决，因为题目要求按层级组成数组来访问，所以我们可以考虑多加一个辅助类 Help，来记录当前节点所在的层级，以此辅助解决问题。具体思路：

  1. 创建一个新的辅助类 Help，记录 node 及其所在的 level；
  2. root 先入队；
  3. 队列不为空就循环，队头出队，依据 level 是否等于 result.size() 来判断是否遍历到新的一层，如果是，就需要创建新的一层的数组来记录数据；
  4. 再依次放入左右子树的根节点，这个时候对应的左右子树根节点所在的层级就是 level + 1了。
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Help> queue = new LinkedList<>();

        if(root == null){
            return result;
        }

        Help help = new Help(root, 0);
        queue.offer(help);

        while(queue.size() != 0){
						
          	// 出队
            help = queue.poll();
            int level = help.level;

            // 因为 level 从 0 开始
            // 所以如果 level == result.size()
            // 就说明遍历到了新的一层了
            if(level == result.size()){
                result.add(new LinkedList<Integer>());
            }   
            // 输出
            result.get(level).add(help.node.val);

            // 左右子树入队
            if(help.node.left != null){
                queue.offer(new Help(help.node.left, level + 1));
            }
            if(help.node.right != null){
                queue.offer(new Help(help.node.right, level + 1));
            }
        }
        return result;
    }
}

// 辅助类
// 加一个 level 记录当前节点所在的层，从 0 开始
class Help{
    TreeNode node;
    int level;
    public Help(TreeNode node, int level){
        this.node = node;
        this.level = level;
    }
}

# Leetcode 107 Binary Tree Level Order Traversal II

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

与一般的层次遍历不同，本题要求我们从底向上输出。核心思路与上题相似，有两点不同：

  1. 添加新的一层在 res 的时候，要添加在 res 前面；
  2. 在根据 level 定位 res 中的列表的时候，要根据当前 res.size 和 level 来定：res.size - level - 1
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        LinkedList<Help> queue = new LinkedList<>();
        queue.offer(new Help(root, 0));

        while(queue.size() != 0) {
            Help help = queue.poll();

            // 需要加层
            if(help.level == res.size()){
                // 添加前面
                res.addFirst(new LinkedList<Integer>());
            }

            res.get(res.size() - help.level -1).add(help.node.val);

            // 左
            if(help.node.left != null){
                queue.offer(new Help(help.node.left, help.level + 1));
            }
            // 右
            if(help.node.right != null){
                queue.offer(new Help(help.node.right, help.level + 1));
            }

        }

        return res;
    }
}

class Help{
    TreeNode node;
    int level; // 记录层
    public Help(TreeNode node, int level) {
        this.node = node;
        this.level = level;
    }
}

# Leetcode 103 Binary Tree ZigZag Level Order Traversal

https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

层次遍历的变通，如果 level 从 0 开始的话，那就是偶数层是从左到右，奇数层从右到左。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        LinkedList<Help> queue =  new LinkedList<>();
        queue.offer(new Help(root, 0)); // level 从 0 开始

        while(queue.size() != 0) {
            Help help = queue.poll();
            
            // 判断是否需要加层
            if(help.level == res.size()) {
                res.add(new LinkedList<Integer>());
            }

            // 偶数层，从左到右
            if(help.level % 2 == 0) {
                res.get(help.level).add(help.node.val);
            }
            // 奇数层，从右到左
            if(help.level % 2 == 1) {
                LinkedList<Integer> list = (LinkedList<Integer>)res.get(help.level);
                list.addFirst(help.node.val);
            }

            if(help.node.left != null) {
                queue.offer(new Help(help.node.left, help.level + 1));
            }
            if(help.node.right != null) {
                queue.offer(new Help(help.node.right, help.level + 1));
            }
        }

        return res;
    }
}

class Help{
    TreeNode node;
    int level; // 记录层
    public Help(TreeNode node, int level) {
        this.node = node;
        this.level = level;
    }
}

# Leetcode 199 Binary Tree Right Size View

https://leetcode.cn/problems/binary-tree-right-side-view/

本题只要层次遍历中，每一层的最后一个，所以我们就按层次遍历的方法来，如果该层右边还有节点，那就一直覆盖就可以了。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }

        LinkedList<Help> queue = new LinkedList<>();
        queue.offer(new Help(root, 0));
        while(queue.size() != 0) {
            Help help = queue.poll();
            
            if(help.level == res.size()) {
                // 新加一层，就先存当前节点的值
                res.add(help.node.val);
            } else {
                // 之前就有该层，那就直接覆盖
                res.set(help.level, help.node.val);
            }

            if(help.node.left != null){
                queue.offer(new Help(help.node.left, help.level + 1));
            }
            if(help.node.right != null){
                queue.offer(new Help(help.node.right, help.level + 1));
            }
        }
        return res;
    }
}

class Help{
    TreeNode node;
    int level;
    public Help(TreeNode node, int level) {
        this.node = node;
        this.level = level;
    }
}

# 最短路径

# Leetcode 279 Perfect Squares

https://leetcode.cn/problems/perfect-squares/

我们可以将本题转化为一个图论问题：

  1. 从 n 到 0，每个数字表示一个节点；
  2. 如果两个数字 x 和 y 相差一个完全平方数，则连接一条边；
  3. 这样我们就得到了一个无权图。

原问题转为：求这个无权图中从 n 到 0 的最短路径。

image-20220905211143504

class Solution {

    class Help{
        int num;			// 第 n 个数
        int step;			// n 走到 0 需要的步数
        public Help(int num, int step){
            this.num = num;
            this.step = step;
        }
    }


    public int numSquares(int n) {
      
        // BFS 用队列
        LinkedList<Help> queue = new LinkedList<>();
        queue.offer(new Help(n,0));
      
        // 去重，避免相同元素重复入队
        boolean[] visited = new boolean[n+1];
        visited[n] = true;
				
      	// BFS
        while(queue.size() != 0){
            Help help = queue.poll();
            int num = help.num;
            int step = help.step;
          	
           	// 到 0 了就可以退出了
            if(num == 0)
                return step;
          
            // 尝试继续走到 n
            // 最短路径的那个会最先走到 num == 0
            for(int i=0; ;i++){
                int newNum = num - i*i;
                if(newNum < 0){
                    break;
                }
                if(!visited[newNum]){
                    queue.offer(new Help(newNum,step+1));
                    visited[newNum] = true;
                }
            }
        }
        return 0;

    }
}

# Leetcode 127 Word Ladder

https://leetcode.cn/problems/word-ladder/

image-20220905214809043

画完示意图后，我们会发现，这也是个图论的最短路径问题。

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        // BFS 用队列
        LinkedList<Help>  queue = new LinkedList<>();

        // 初始化，beginWord 到 beginWord 的 length 为 1， index 默认为 -1
        queue.offer(new Help(beginWord, 1, -1));
        boolean[] visited = new boolean[wordList.size()];

        while(queue.size() != 0) {

            Help help = queue.poll();

            // 走到了 endWord， 就
            if(help.cur.equals(endWord)) {
                return help.length;
            }

            for(int i=0; i<wordList.size(); i++) {
                // 不跟自己绕
                if (i == help.index) {
                    continue;
                }
                // 去重
                if (!visited[i]) {
                    if(canLink(help.cur, wordList.get(i))) {
                        queue.offer(new Help(wordList.get(i), help.length+1, i));
                        visited[i] = true;
                    }
                }
                
            }
        }
        // 没找到
        return 0;
    }

		
  	// 判断两个单词是否一个一个字符不同
    public boolean canLink(String word1, String word2) {
        char[] c1 = word1.toCharArray();
        char[] c2 = word2.toCharArray();

        int differ = 0;

        for(int i=0;i < c1.length; i++) {
            if(c1[i] != c2[i]) {
                differ++;
            }
        }

        return differ <= 1;
    }
}

class Help{
    String cur;     // 当前节点
    int length;       // cur 到 beginWord 的长度
    int index;      // 当前节点在 wordList 中的索引，避免走回头路
    public Help(String cur, int length, int index) {
        this.cur = cur;
        this.length = length;
        this.index = index;
    }
}

# Leetcode 126 Word Ladder II

https://leetcode.cn/problems/word-ladder-ii/

与上一题不同的是，本题需要记录所有最短序列。

不会，超时了。

# 优先队列

# Leetcode 347 Top K Frequent Elements

https://leetcode.cn/problems/top-k-frequent-elements/

本题可以用 优先队列 + 并查集 来解决，具体思路如下：

  1. 定义一个 HashMap，key 存数字，value 存对应数字在数组中的出现次数；
  2. 遍历 nums，将数字及其对应的出现次数存储到 HashMap 中；
  3. 定义一个辅助类 Element 来存储数字及其出现次数；
  4. 以小顶堆的模式定义一个 PriorityQueue（默认就是小顶堆）；
  5. 不断将 Element 存入优先队列，如果优先队列满了，就比较当前 Element 的出现次数和堆顶的出现次数大小，如果大，堆顶就出队，新的 Element 就入队；
  6. 以此下去，最后剩下在 PriorityQueue 的就是前 k 个元素了。
class Element implements Comparable{
    int value;
    int freq;
    Element(int value,int freq){
        this.value = value;
        this.freq = freq;
    }

    @Override
    public int compareTo(Object o){
        if(o instanceof Element){
            Element e = (Element)o;
            if(this.freq>e.freq){
                return 1;
            }else if(this.freq < e.freq){
                return -1;
            }else{
                return 0;
            }
        }

        throw new RuntimeException();
    }
}


class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        int[] result = new int[k];

        //统计频率
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            Integer j = map.get(nums[i]);
            if(j==null){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],j+1);
            }
        }

        //扫描map，维护当前出现频率最高的k个元素，需要小顶堆
        Queue<Element> queue = new PriorityQueue<>();

        Set<Integer> keys = map.keySet();
        for(Integer key : keys){
            Integer freq = map.get(key);

            //满了，可能就需要替换了
            if( queue.size() == k){
                Element e = queue.peek();
                if( freq > e.freq){
                    queue.poll();
                    queue.offer(new Element(key,freq));
                }
            }else{
                queue.offer(new Element(key,freq));
            }
        }

        int i=0;
        while(!queue.isEmpty()){
            Element e = queue.poll();
            result[i] = e.value;
            i++;
        }
        
        return result;
    }
}

# Leetcode 23 Merge K Sorted Lists

https://leetcode.cn/problems/merge-k-sorted-lists/

本题最基本的思路就是循环，一个个两两合并。

不过本题我们还可以巧用优先队列来解决，具体思路如下：

  1. 建立一个长度为 len(lists) 的优先级队列（小顶堆），这里假定有 k 个链表；
  2. 先直接将 k 个链表中的最小值放到优先级队列中；
  3. 然后取出队头的元素 node，那么它就是当前未确定的最小的值，放到 res 的后面就可以了；
  4. 然后再将 node.next 放进队列中即可；
  5. 以此遍历完所有链表，即可合并 k 个链表。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists.length == 0) {
            return null;
        }

        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;

        // 优先级队列，就存 lists.length 个
        Queue<Element> queue = new PriorityQueue<>(lists.length);

        for(ListNode list : lists) {
            if(list != null) {
                queue.offer(new Element(list.val, list));
            }
        }
        while(!queue.isEmpty()){
            // 每次取出来都是待确定的最小的那个
            Element e = queue.poll();
            // 直接加在尾部
            cur.next = e.ptr;
            cur = cur.next;
            // 如果还有，那继续往里面放
            if(e.ptr.next != null) {
                queue.offer(new Element(e.ptr.next.val, e.ptr.next));
            }
        }
        return dummyHead.next;
    }
}

class Element implements Comparable<Element> {
    int val;            // 节点值
    ListNode ptr;       // 节点
    public Element(int val, ListNode ptr) {
        this.val = val;
        this.ptr = ptr;
    }

    // 小顶堆
    public int compareTo(Element e) {
        return this.val - e.val;
    }
}
上次更新: 9/6/2022, 11:46:05 PM

← 二叉树 →