leetcode——栈、队列、优先队列

左手的ㄟ右手 2022-10-13 12:35 302阅读 0赞

题目

      1. 有效的括号
      1. 逆波兰表达式求值
      1. 简化路径
      1. 二叉树的前序遍历
      1. 二叉树的中序遍历
      1. 二叉树的后序遍历
      1. 扁平化嵌套列表迭代器
      1. 二叉树的层序遍历
      1. 二叉树的层序遍历 II
      1. 二叉树的锯齿形层序遍历
      1. 二叉树的右视图
      1. 前 K 个高频元素
      1. 合并K个升序链表

20. 有效的括号

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true

示例 2：

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

示例 3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([)]”
输出：false

示例 5：

输入：s = “{[]}”
输出：true

提示：

  1. 1 <= s.length <= 104
  2. s 仅由括号 '()[]{}' 组成

题解：经典的括号匹配问题，用栈处理。

那么这里为什么不用Stack，而使用ArrayDeque呢？因为Stack是Vector的子类，而Vector里面的方法基本都是用synchronized修饰的，虽然是线程安全的，但是效率会比较低，而对于ArrayList和ArrayDeque，本身是线程不安全的，若想要线程安全，只需使用Collections.synchronizedCollection()转化成线程安全的,基本可以绕过Vector。

  1. class Solution {
  3.     public boolean isValid(String s) {
  5.         char[] sc = s.toCharArray();
  6.         ArrayDeque<Character> deque = new ArrayDeque();
  7.         for(int i = 0; i < sc.length; i++){
  9.             if(sc[i] == '(' || sc[i] == '[' || sc[i] == '{'){
  11.                 deque.addLast(sc[i]);
  12.             }else{
  14.                 if(deque.isEmpty()){
  16.                     return false;
  17.                 }
  18.                 char c = deque.removeLast();
  19.                 if((sc[i] == ')' && c != '(' ) || (sc[i] == '}' && c != '{' ) || (sc[i] == ']' && c != '[' ))
  20.                 return false;
  21.             }
  22.         }
  23.         return deque.isEmpty();
  24.     }
  25. }

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

  1. 整数除法只保留整数部分。
  2. 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 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. 1 <= tokens.length <= 104
  2. tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

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

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

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

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

题解：上面介绍优点的第二个就是题解。

  1. class Solution {
  3.     public int evalRPN(String[] tokens) {
  5.         ArrayDeque<Integer> deque = new ArrayDeque();
  6.         for(int i = 0; i < tokens.length; i++){
  8.             if(isNumber(tokens[i])){
  10.                 deque.addLast(Integer.parseInt(tokens[i]));
  11.             }else{
  13.                 Integer a = deque.removeLast();
  14.                 Integer b = deque.removeLast();
  15.                 switch(tokens[i]){
  17.                     case "+" : deque.addLast(b + a); break;
  18.                     case "-" : deque.addLast(b - a); break;
  19.                     case "*" : deque.addLast(b * a); break;
  20.                     case "/" : deque.addLast(b / a); break;
  21.                 }
  22.             }
  23.         }
  24.         return deque.removeLast(); 
  25.     }
  27.     public boolean isNumber(String str){
  29.         return !(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"));
  30.     }
  31. }

71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

  1. 始终以斜杠 '/' 开头。
  2. 两个目录名之间必须只有一个斜杠 '/' 。
  3. 最后一个目录名（如果存在）不能 以 '/' 结尾。
  4. 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = “/home/”
输出：”/home”
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

输入：path = “/…/”
输出：”/“
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入：path = “/home//foo/”
输出：”/home/foo”
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入：path = “/a/./b/…/…/c/”
输出：”/c”

提示：

  1. 1 <= path.length <= 3000
  2. path 由英文字母，数字，'.'，'/' 或 '_' 组成。
  3. path 是一个有效的 Unix 风格绝对路径。

题解：将字符串按照 “/”分隔开，然后遍历，过滤掉空格和“.”,如果是“. .”，并且栈不为空，则出栈；否则入栈。

  1. class Solution {
  3.     public String simplifyPath(String path) {
  5.         String[] res = path.split("/");
  6.         ArrayDeque<String> deque = new ArrayDeque();
  7.         for(int i = 0; i < res.length; i++){
  9.             if(!res[i].equals("") && !res[i].equals(".")){
  11.                 if(res[i].equals("..")){
  13.                     if(!deque.isEmpty())
  14.                         deque.removeLast();
  15.                 }else{
  17.                     deque.addLast(res[i]);
  18.                 }
  19.             }
  20.         }
  21.         StringBuilder sb = new StringBuilder();
  22.         for(String s : deque){
  24.             sb.append("/" + s);
  25.         }
  26.         if(sb.toString().equals(""))
  27.             return "/";
  28.         return sb.toString();
  29.     }
  30. }

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：
在这里插入图片描述

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

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

示例 3：

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

示例 4：
在这里插入图片描述

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

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

  1. 树中节点数目在范围 [0, 100] 内
  2. -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

①递归实现：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  19.     List<Integer> res = new ArrayList<>();
  21.     public List<Integer> preorderTraversal(TreeNode root) {
  23.         if(root != null)
  24.             res.add(root.val);
  25.         if(root != null && root.left != null)
  26.             preorderTraversal(root.left);
  27.         if(root != null && root.right != null)
  28.             preorderTraversal(root.right);
  29.         return res;    
  30.     }   
  31. }

②迭代实现：对于二叉树的前序遍历，可以先推根节点入栈，进入循环，因为栈是后入先出，所以先推入右节点，后推入左节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<Integer> preorderTraversal(TreeNode root) {
  20.         ArrayDeque<TreeNode> deque = new ArrayDeque<>();
  21.         List<Integer> res = new ArrayList<>();
  22.         if(root == null)
  23.             return res;
  24.         deque.addLast(root);
  25.         while(!deque.isEmpty()){
  27.             TreeNode node = deque.removeLast();
  28.             res.add(node.val);
  29.             if(node.right != null){
  31.                 deque.addLast(node.right);
  32.             }
  33.             if(node.left != null){
  35.                 deque.addLast(node.left);
  36.             }
  37.         }
  38.         return res;
  39.     }   
  40. }

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

  1. 树中节点数目在范围 [0, 100] 内
  2. -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     List<Integer> res = new ArrayList<>();
  19.     public List<Integer> inorderTraversal(TreeNode root) {
  21.         if(root != null && root.left != null)
  22.             inorderTraversal(root.left);
  23.         if(root != null)
  24.             res.add(root.val);
  25.         if(root != null && root.right != null)
  26.             inorderTraversal(root.right);
  27.         return res;
  28.     }
  29. }

迭代实现思路：用栈，一路找到二叉树的最左孩子，弹出并存入结果；然后判断当前节点有无右节点，有的话需要继续找到其最左孩子。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<Integer> inorderTraversal(TreeNode root) {
  20.         ArrayDeque<TreeNode> deque = new ArrayDeque<>();
  21.         List<Integer> res = new ArrayList<>();
  22.         if(root == null)
  23.             return res;
  24.         TreeNode cur = root;
  25.         while(!deque.isEmpty() || cur != null){
  27.             while(cur != null){
  29.                 deque.addLast(cur);
  30.                 cur = cur.left;
  31.             }
  32.             TreeNode node = deque.removeLast();
  33.             res.add(node.val);
  34.             if(node.right != null){
  36.                 cur = node.right;
  37.             }
  38.         }
  39.         return res;
  40.     }
  41. }

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     List<Integer> res = new ArrayList<>();
  19.     public List<Integer> postorderTraversal(TreeNode root) {
  21.         if(root != null && root.left != null)
  22.             postorderTraversal(root.left);
  23.         if(root != null && root.right != null)
  24.             postorderTraversal(root.right);
  25.         if(root != null)
  26.             res.add(root.val);
  27.         return res;
  28.     }
  29. }

迭代：后序遍历打印的结果是左右中，所以我们入栈的顺序可以是中右左。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<Integer> postorderTraversal(TreeNode root) {
  20.         ArrayDeque<TreeNode> deque = new ArrayDeque<>();
  21.         ArrayDeque<Integer> resDeque = new ArrayDeque<>();
  22.         List<Integer> res = new ArrayList<>();
  23.         if(root == null)
  24.             return res;
  25.         deque.addLast(root);
  26.         while(!deque.isEmpty()){
  28.             TreeNode node = deque.removeLast();
  29.             resDeque.addLast(node.val);
  30.             if(node.left != null)
  31.                 deque.addLast(node.left);
  32.             if(node.right != null)
  33.                 deque.addLast(node.right);
  34.         }
  35.         while(!resDeque.isEmpty()){
  37.             res.add(resDeque.removeLast());
  38.         }
  39.         return res;
  40.     }
  41. }

341. 扁平化嵌套列表迭代器

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

思路：把一个嵌套的列表，存储到普通列表中，然后实现iterator()方法。

  1. /**
  2.  * // This is the interface that allows for creating nested lists.
  3.  * // You should not implement it, or speculate about its implementation
  4.  * public interface NestedInteger {
  5.  *
  6.  *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
  7.  *     public boolean isInteger();
  8.  *
  9.  *     // @return the single integer that this NestedInteger holds, if it holds a single integer
  10.  *     // Return null if this NestedInteger holds a nested list
  11.  *     public Integer getInteger();
  12.  *
  13.  *     // @return the nested list that this NestedInteger holds, if it holds a nested list
  14.  *     // Return empty list if this NestedInteger holds a single integer
  15.  *     public List<NestedInteger> getList();
  16.  * }
  17.  */
  18. public class NestedIterator implements Iterator<Integer> {
  20.     private List<Integer> list;
  21.     private Iterator<Integer> cur;
  23.     public NestedIterator(List<NestedInteger> nestedList) {
  25.         list = new ArrayList<>();
  26.         // 把值传入list
  27.         DFS(nestedList);
  28.         cur = list.iterator();    
  29.     }
  31.     @Override
  32.     public Integer next() {
  34.         return cur.next();
  35.     }
  37.     @Override
  38.     public boolean hasNext() {
  40.         return cur.hasNext();
  41.     }
  43.     public void DFS(List<NestedInteger> nestedList){
  45.         for(NestedInteger i : nestedList){
  47.             if(i.isInteger()){
  49.                 list.add(i.getInteger());
  50.             }else{
  52.                 DFS(i.getList());
  53.             }
  54.         }
  55.     }
  56. }
  58. /**
  59.  * Your NestedIterator object will be instantiated and called as such:
  60.  * NestedIterator i = new NestedIterator(nestedList);
  61.  * while (i.hasNext()) v[f()] = i.next();
  62.  */

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

在这里插入图片描述

返回其层序遍历结果：

[
[3],
[9,20],
[15,7]
]

题解：这里的ArrayDeque主要的作用是队列了。把每一层的元素入队，然后依次弹出记录。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<List<Integer>> levelOrder(TreeNode root) {
  20.         List<List<Integer>> res = new ArrayList<>();
  21.         Queue<TreeNode> queue = new ArrayDeque<>();
  22.         if(root != null){
  24.             queue.add(root);
  25.         }
  26.         while(!queue.isEmpty()){
  28.             List<Integer> list = new ArrayList<>();
  29.             int n = queue.size();
  30.             for(int i = 0; i < n; i++){
  32.                 TreeNode node = queue.poll();
  33.                 list.add(node.val);
  34.                 if(node.left != null)
  35.                     queue.add(node.left);
  36.                 if(node.right != null)
  37.                     queue.add(node.right);
  38.             }
  39.             res.add(list);
  40.         }
  41.         return res;
  42.     }
  43. }

107. 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

在这里插入图片描述

返回其自底向上的层序遍历为：

[
[15,7],
[9,20],
[3]
]

题解：把上一题的数据结构变成LinkedList<>()，用头插法实现倒序。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
  20.         LinkedList<List<Integer>> res = new LinkedList<>();
  21.         Queue<TreeNode> queue = new ArrayDeque<>();
  22.         if(root != null){
  24.             queue.add(root);
  25.         }
  26.         while(!queue.isEmpty()){
  28.             List<Integer> list = new ArrayList<>();
  29.             int n = queue.size();
  30.             for(int i = 0; i < n; i++){
  32.                 TreeNode node = queue.poll();
  33.                 list.add(node.val);
  34.                 if(node.left != null)
  35.                     queue.add(node.left);
  36.                 if(node.right != null)
  37.                     queue.add(node.right);
  38.             }
  39.             res.addFirst(list);
  40.         }
  41.         return res;
  42.     }
  43. }

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

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

例如：
给定二叉树 [3,9,20,null,null,15,7],
在这里插入图片描述

返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

题解：加一个flag判断，当其为偶数行的时候，利用Collections.reverse()，直接反转整一行即可。

  1. class Solution {
  3.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  5.         List<List<Integer>> res = new ArrayList<>();
  6.         Queue<TreeNode> queue = new ArrayDeque<>();
  7.         if(root != null){
  9.             queue.add(root);
  10.         }
  11.         Boolean flag = false;
  12.         while(!queue.isEmpty()){
  14.             int n = queue.size();
  15.             List<Integer> list = new ArrayList<>();
  16.             for(int i = 0; i < n; i++){
  18.                 TreeNode node = queue.poll();
  19.                 list.add(node.val);
  20.                 if(node.left != null)
  21.                     queue.add(node.left);
  22.                 if(node.right != null)
  23.                     queue.add(node.right);
  24.             }
  25.             if(flag){
  27.                 Collections.reverse(list);
  28.             }
  29.             flag = !flag;
  30.             res.add(list);
  31.         }
  32.         return res;
  33.     }
  34. }

199. 二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
在这里插入图片描述

思路：想法很简单，就是层序遍历，然后保存最后一个节点。一开始的代码如下，

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<Integer> rightSideView(TreeNode root) {
  20.         List<Integer> res = new ArrayList<>();
  21.         Queue<TreeNode> queue = new ArrayDeque<>();
  22.         if(root != null){
  24.             queue.add(root);
  25.         }
  26.         while(!queue.isEmpty()){
  28.             int n = queue.size();
  29.             ArrayDeque<Integer> queueLast = new ArrayDeque<>();
  30.             for(int i = 0; i < n; i++){
  32.                 TreeNode node = queue.poll();
  33.                 queueLast.add(node.val);
  34.                 if(node.left != null)
  35.                     queue.add(node.left);
  36.                 if(node.right != null)
  37.                     queue.add(node.right);
  38.             }
  39.             res.add(queueLast.removeLast());
  40.         }
  41.         return res;
  42.     }
  43. }

结果发现效率很低，2ms，只打败20+%的人，参考了一下大佬的代码，发现我这里有一些地方是多余的。
在这里插入图片描述我只要最后一个元素，却把很多多余的元素给添加进队列了。优化的方法就是把它去掉，然后再for里加一个判断是否为最后一轮遍历，此时的node.val就是最后一个值。变为1 ms, 在所有 Java 提交中击败了99.59% 的用户。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<Integer> rightSideView(TreeNode root) {
  20.         List<Integer> res = new ArrayList<>();
  21.         Queue<TreeNode> queue = new ArrayDeque<>();
  22.         if(root != null){
  24.             queue.add(root);
  25.         }
  26.         while(!queue.isEmpty()){
  28.             int n = queue.size();
  29.             for(int i = 0; i < n; i++){
  31.                 TreeNode node = queue.poll();
  32.                 if(node.left != null)
  33.                     queue.add(node.left);
  34.                 if(node.right != null)
  35.                     queue.add(node.right);
  36.                    // 修改的代码
  37.                 if(i == n - 1){
  39.                     res.add(node.val);
  40.                 }
  41.             }
  42.         }
  43.         return res;
  44.     }
  45. }

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

  1. 1 <= nums.length <= 105
  2. k 的取值范围是 [1, 数组中不相同的元素的个数]
  3. 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

思路：用一个treeMap来存储数值和它的频数，建立一个优先队列，在维持里面数量为k的情况下，遍历map.keySet。最后输出结果。

  1. import java.util.LinkedList;
  2. import java.util.PriorityQueue;
  3. import java.util.TreeMap;
  5. public class Solution {
  7.     class Freq implements Comparable<Freq>{
  9.         int e, freq;
  11.         public Freq(int e,int freq){
  13.             this.e = e;
  14.             this.freq = freq;
  15.         }
  17.         @Override
  18.         public int compareTo(Freq another){
  20.             if(this.freq < another.freq)
  21.                 return -1;
  22.             else if(this.freq > another.freq)
  23.                 return 1;
  24.             else
  25.                 return 0;
  27.         }
  29.     }
  30.         public int[] topKFrequent(int[] nums, int k) {
  32.             TreeMap<Integer,Integer> map = new TreeMap<>();
  33.             for(int num : nums){
  35.                 if(map.containsKey(num)){
  37.                     map.put(num, map.get(num) + 1);
  38.                 }else
  39.                     map.put(num, 1);
  40.             }
  42.             PriorityQueue<Freq> pq = new PriorityQueue<>();
  43.             for(int key : map.keySet()){
  45.                 if(pq.size() < k){
  47.                     pq.add(new Freq(key, map.get(key)));
  48.                 }else if(map.get(key) > pq.peek().freq){
  50.                     pq.remove();
  51.                     pq.add(new Freq(key, map.get(key)));
  52.                 }
  53.             }
  56.             int[] res = new int[k];
  57.             int i = 0;
  58.             while(!pq.isEmpty())
  59.                 res[i++] = pq.remove().e;
  60.             return res;
  62.         }
  64. }

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 = [[]]
输出：[]

提示：

  1. k == lists.length
  2. 0 <= k <= 10^4
  3. 0 <= lists[i].length <= 500
  4. -10^4 <= lists[i][j] <= 10^4
  5. lists[i] 按 升序 排列
  6. lists[i].length 的总和不超过 10^4

思路：用容量为K的最小堆优先队列，把链表的头结点都放进去，然后出队当前优先队列中最小的，挂上链表，然后让出队的那个节点的下一个入队，再出队当前优先队列中最小的，直到优先队列为空。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  13.     public ListNode mergeKLists(ListNode[] lists) {
  15.         if(lists.length==0)
  16.             return null;
  17.         // 定义一个存结果的链表
  18.         ListNode dummy = new ListNode(0);
  19.         ListNode cur = dummy;
  20.         PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
  22.             @Override
  23.             public int compare(ListNode o1,ListNode o2){
  25.                 return o1.val - o2.val;
  26.             }
  27.         });
  29.         for(ListNode list : lists){
  31.             if(list == null)
  32.                 continue;
  33.             pq.add(list);
  34.         }
  36.         while(!pq.isEmpty()){
  38.             ListNode node = pq.poll();
  39.             cur.next = node;
  40.             cur = cur.next;
  41.             if(node.next != null){
  43.                 pq.add(node.next);
  44.             }
  46.         }
  47.         return dummy.next;
  48.     }
  49. }

发表评论

表情：
评论列表 （有 0 条评论，302人围观）

还没有评论，来说两句吧...

相关阅读