栈和队列
先来几个经典题目练练手
栈
Leetcode 20 有效的括号
括号匹配问题是很经典的栈应用问题，虽然很简单，但是我们也需要从头开始梳理一遍思路
首先，对于两个匹配的括号而言，他们应该具有同样的 “深度”，即左括号如果在第三层，那么右括号也必须在第三层
对于最深层的括号而言，第一个与其相反的括号必须是其另一半，否则就返回 false；倒数第二层的同理，第二个相反的括号也必须是其另一半
因此如果熟悉栈的性质，那么也就知道，如果对括号进行入栈和出栈操作，那就天然的符合一种嵌套的层次结构
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if(c == '{' || c == '[' || c == '('){stack.push(c);}else{if(stack.size() == 0) {return false;}char left = stack.peek();if(c == '}' && left != '{'){return false;}else if(c == ']' && left != '['){return false;}else if(c == ')' && left != '('){return false;}else {stack.pop();}}}//最后还剩下左括号的话，说明没有匹配完成return stack.size() == 0;}}
Leetcode 150 逆波兰表达式
太简单了，没啥好说的
class Solution {public int evalRPN(String[] tokens) {//数字栈Stack<Integer> iStack = new Stack<>();int sum = 0;int after;int before;//遍历，操作数入栈，遍历到运算符时出栈两个操作数运算，并入栈for (String token : tokens) {switch (token) {case "*":after = iStack.pop();before = iStack.pop();iStack.push(before * after);break;case "-":after = iStack.pop();before = iStack.pop();iStack.push(before - after);break;case "/":after = iStack.pop();before = iStack.pop();iStack.push( before / after);break;case "+":after = iStack.pop();before = iStack.pop();iStack.push(before + after);break;default:iStack.push(Integer.parseInt(token));}}return iStack.pop();}}
牛客巅峰赛 S2 第五期 牛牛与后缀表达式
这道题和逆波兰差不多的嗷，区别在于参数给的是字符串，而是字符串数组，因此需要做一些处理
- 当遇到 # 时，将数字入栈
- 当遇到数字时，不能入栈，而是要加到之前的数字的个位上 (如果有的话)，因此需要先将之前的数字扩大 10 倍
class Solution {public long solve (String tokens) {// write code here//数字栈Stack<Long> iStack = new Stack<>();Long temp = 0L;Long after;Long before;//遍历，操作数入栈，遍历到运算符时出栈两个操作数运算，并入栈for (char token : tokens.toCharArray()) {switch (token) {case '*':after = iStack.pop();before = iStack.pop();iStack.push(before * after);break;case '-':after = iStack.pop();before = iStack.pop();iStack.push(before - after);break;case '+':after = iStack.pop();before = iStack.pop();iStack.push(before + after);break;case '#'://遇到 #，将之前的数字入栈iStack.push(temp);temp = 0L;break;default://遇到数字，则将其转为数字//连续的数字就将之前的数字乘 10，然后加上当前的数字到个位temp = temp * 10 + (token-'0');}}return iStack.pop();}}
使用栈完成二叉树遍历
Leetcode 144 前序遍历
啊这，这题的递归写法应该不用说了吧？
class Solution {public List<Integer> preorderTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();preorder(root, list);return list;}private void preorder(TreeNode root, List<Integer> list){if(root == null){return;}list.add(root.val);preorder(root.left, list);preorder(root.right, list);}}
( 一开始把列表作为了全局变量一个函数即可。。但是想了想这不讲码德，就算了 )
其实递归本身就是一种栈的实验，只不过这种栈是系统 / 高级语言虚拟机为我们提供的 ( JVM 栈帧 )
因此我们可以使用自定义的栈来模拟栈帧
对于先序遍历而言，遍历顺序是根->左->右，因此我们只需要按照相反的顺序向 Stack 中按照右->左->根的顺序推入结点，那么最后的出栈顺序也就和系统栈的顺序一致了
class Solution {public List<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> res = new ArrayList<>();if(root == null){return res;}Stack<TreeNode> nodeStack = new Stack<>();nodeStack.push(root);while (!nodeStack.isEmpty()){TreeNode ptr = nodeStack.peek();nodeStack.pop();if(ptr != null){//右if(ptr.right != null){nodeStack.push(ptr.right);}//左if(ptr.left != null){nodeStack.push(ptr.left);}//根，标记下面一个是父结点，表示"应该"遍历的子结点都遍历完了nodeStack.push(ptr);nodeStack.push(null);}else{res.add(nodeStack.peek().val);nodeStack.pop();}}return res;}}
对于这个过程，如果不理解可以画图理解，很 easy 的
Leetcode 94 中序遍历
中序遍历的顺序是左->根->右
因此我们需要先到最深处的左结点，并将途中的所有左子树上的结点加入栈，然后弹出栈顶元素加入到待返回列表中 ( 由于是在栈顶元素的左子树为空时停止的循环，因此相当于已经遍历了基于该结点的左子树，然后栈顶元素就相当于当前的根 )，最后转向右子树
class Solution {public List<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> res = new ArrayList<>();if(root == null){return res;}Stack<TreeNode> nodeStack = new Stack<>();TreeNode ptr = root;while (!nodeStack.isEmpty() || ptr != null){//左while (ptr != null){nodeStack.push(ptr);ptr = ptr.left;}//根ptr = nodeStack.pop();res.add(ptr.val);//右ptr = ptr.right;}return res;}}
或者有了第一道题的模板，只需要更改一下顺序即可，中序遍历的顺序是左根右，因此入栈顺序是右根左
class Solution {public List<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> res = new ArrayList<>();if(root == null){return res;}Stack<TreeNode> nodeStack = new Stack<>();nodeStack.push(root);while (!nodeStack.isEmpty()){TreeNode ptr = nodeStack.peek();nodeStack.pop();if(ptr != null){//右if(ptr.right != null){nodeStack.push(ptr.right);}//根，并在根之后压入一个 null，表示已经把下次需要放入 res 的结点都压栈了nodeStack.push(ptr);nodeStack.push(null);//左if(ptr.left != null){nodeStack.push(ptr.left);}}else{res.add(nodeStack.peek().val);nodeStack.pop();}}return res;}}
Leetcode 145 后序遍历
和前序、中序遍历有所差别的是，根结点需要最后访问，因此在左子树全部入栈后，需要判断栈顶结点有没有右子树，有的话则优先访问右子树，否则才加入到待返回列表中
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Stack<TreeNode> nodeStack = new Stack<>();
TreeNode ptr = root;
while (!nodeStack.isEmpty() || root!=null){
while (root != null){
nodeStack.push(root);
root = root.left;
}
root = nodeStack.pop();
//如果弹出的结点有右子树，则先去访问右孩子，否则作为根结点将结果放入列表
//ptr 指向上一次进入列表的元素的对应结点
//当上一次进入的结点是右孩子时，说明这次需要进入根结点
//但是很明显 root.right 是不为 null 的，因此需要添加一个
//root.right == ptr 的判断条件，来判断是不是根结点
if(root.right == null || root.right == ptr){
res.add(root.val);
ptr = root;
root = null;
}else {
//根结点重新入栈，然后访问右子树
nodeStack.push(root);
root = root.right;
}
}
return res;
}
}
同样，这题也可以用上面的通用方法来解决，后序遍历的顺序是左右根，因此按照根右左的顺序入栈即可
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Stack<TreeNode> nodeStack = new Stack<>();
nodeStack.push(root);
while (!nodeStack.isEmpty()){
TreeNode ptr = nodeStack.peek();
nodeStack.pop();
if(ptr != null){
//根，标记下面一个是父结点，表示应该遍历的子结点都遍历完了
nodeStack.push(ptr);
nodeStack.push(null);
//右
if(ptr.right != null){
nodeStack.push(ptr.right);
}
//左
if(ptr.left != null){
nodeStack.push(ptr.left);
}
}else{
res.add(nodeStack.peek().val);
nodeStack.pop();
}
}
return res;
}
}
Leetcode 341 扁平化迭代器
这道题的模板看似给的很迷，但是如果理解了意思也就不难了
首先这道题的模板中给了一个接口，该接口表示了示例中所输入的列表中的元素，可以是数字也可以是 list，并提供了三个方法
需要我们编写的代码长这样，我们的目的是将 nestedList 拆分为一个 Integer list，因此可以设立一个全局的 List，然后将拆分结果放入这个 List 中，对于拆分而言，递归即可
public void getAllInt(List<NestedInteger> nestedList){
//如果是数字则加入，否则递归列表
for (NestedInteger nestedInteger : nestedList) {
if(nestedInteger.isInteger()){
res.add(nestedInteger.getInteger());
}else{
getAllInt(nestedInteger.getList());
}
}
}
然后 next 方法需要迭代出当前的元素，然后下次调用 next 时也可以迭代出 list 中下一个元素，因此我们需要设立一个索引，用来取出 list 中的元素并返回
@Override
public Integer next() {
return res.get(cur++);
}
最后 hasNext，判断还有没有下一个元素，由于 list 是在初始化时就将 nestedList 拆分后得到的已知长度的 list，因此如果索引大于等于 list 的长度时，返回 false 即可
@Override
public boolean hasNext() {
return cur >= res.size();
}
完整代码如下
public class NestedIterator implements Iterator<Integer> {
List<Integer> res = new ArrayList<>();
int cur = 0;
public NestedIterator(List<NestedInteger> nestedList) {
getAllInt(nestedList);
}
/**
* 递归所有数字，加入到 res 中
* @param nestedList
*/
public void getAllInt(List<NestedInteger> nestedList){
//如果是数字则加入，否则递归列表
for (NestedInteger nestedInteger : nestedList) {
if(nestedInteger.isInteger()){
res.add(nestedInteger.getInteger());
}else{
getAllInt(nestedInteger.getList());
}
}
}
@Override
public Integer next() {
return res.get(cur++);
}
@Override
public boolean hasNext() {
return cur >= res.size();
}
}
单调栈
Leetcode 402 移除 k 位数字
这题的关键是数学知识，拿实例 1 来说，假设有以下两个字符串
- 1432
- 1322
很显然，这两个都是移除了 k=3 的字符串，但是后者显然比前者小，因为在相同位上，后者更小
那要怎么做到相同位上的能填充更小的值呢？
我们可以使用一个数组，在遍历字符串时，如果遇到了一个更小的数字，那么我们就将前面所有比它小的数字进行移除，然后将这个更小的数字加入到比他小的数字的后面，同时在移除过程中需要进行计数，即移除次数不能大于 k，否则就不能构成可行解了
这样的过程和栈的出栈入栈过程很类似，同时在遍历过程中会保持栈从小到大的单调性，因此又被称为单调栈
比如：当前字符串是 1432，k 为 3，当前元素为 0，那么就会一直出栈 k 次，即将 234 依次出栈后将 0 入栈，使得栈中当前为 10 (自底向上)，这样无论如何都是比原来的字符串更小的
因此，我们不难写出对字符串进行遍历入栈的代码
Stack<Character> stack = new Stack<>();
for (char ch : num.toCharArray()) {
//移除的个数小于 k
//当前数字小于栈顶的数字
//且栈不为空时
//弹出栈中的栈顶元素，将较小的数字入栈顶替
//这样在删除 k 个数字的所有情况下，就能得到最小的那个数字
while (!stack.isEmpty() && ch < stack.peek() && k > 0) {
stack.pop();
k--;
}
stack.push(ch);
}
在遍历完成后，我们需要思考，k 最后一定为 0 吗？
答案是不一定，假设我们有 1432259 这样一个字符串，且 k = 3，则其解应该为：1225 ( 注意不是 1223，因为我们得保持数字的相对次序 )。随后的 9 因为比之前的所有元素都大，所以就会直接入栈，而此时 k = 1，没有归 0 ，所以在遍历完成字符串后，我们需要判断 k 是否大于 0 来完成继续出栈的操作
//如果字符串都遍历完了 k 还是大于 0，说明栈顶的 k 个元素都是
//比前面大的值，直接弹出即可
while (k > 0 && !stack.isEmpty()) {
stack.pop();
k--;
}
然后，还有一个陷阱，对于 10200，k = 1，这个字符串，0 会 取代掉一开始的 1，最后栈中就成了 0200，对于这种情况，我们需要清除前导 0
StringBuilder ans = new StringBuilder();
boolean leadingZero = true;
for (char ch : stack) {
//去除前导 0，中间出现过不为 0 的数将其置为 false，后续的就不再是前导 0 了
if (leadingZero && ch == '0') {
continue;
}
leadingZero = false;
ans.append(ch);
}
最后，还™有个陷阱，对于 10，k=2 这种会被删完的字符串而言，不能返回空串，而是返回 “0”
return ans.length() == 0 ? "0" : ans.toString();
完整代码如下
class Solution {
public String removeKdigits(String num, int k) {
Stack<Character> stack = new Stack<>();
for (char ch : num.toCharArray()) {
//移除的个数小于 k
//当前数字小于栈顶的数字
//且栈不为空时
//弹出栈中的栈顶元素，将较小的数字入栈顶替
//这样在删除 k 个数字的所有情况下，就能得到最小的那个数字
while (!stack.isEmpty() && ch < stack.peek() && k > 0) {
stack.pop();
k--;
}
stack.push(ch);
}
//如果字符串都遍历完了 k 还是大于 0，说明栈顶的 k 个元素都是
//比前面大的值，直接弹出即可
while (k > 0 && !stack.isEmpty()) {
stack.pop();
k--;
}
StringBuilder ans = new StringBuilder();
boolean leadingZero = true;
for (char ch : stack) {
//去除前导 0，中间出现过不为 0 的数将其置为 false，后续的就不再是前导 0 了
if (leadingZero && ch == '0') {
continue;
}
leadingZero = false;
ans.append(ch);
}
return ans.length() == 0 ? "0" : ans.toString();
}
}
Leetcode 316 去除重复字母
首先我们需要了解下什么叫字典序最小：对于两个字符串，我们从头开始比较
- 如果第一位不相同，则较小的字符串的字典序更小，如果相同则比较第二位
- 第二位较小的字符串的字典序更小，否则比较第三位
- ……
因此，从示例 2 中，我们可以得出以下两种可能的组合
- cbad
- acdb
很显然，第二种的字典序是更小的，那么我们要怎么大奥第二种字典序呢？
和 402 相同的是，我们首先要保证的是从左至右的字符的 ASCII 是单调递增的，且是最小的，因此也不难想到使用单调栈
但是与 402 不同的是，这道题并没有一个除了”当前字符比栈顶字符小”这样一个具体的要求以外的条件，但是仔细思考一下，除了这个条件外，其实还有一个条件：要弹出的字符在后面还会出现，如果不保证这个条件的话，就可能导致最后有的字符全部被弹出，一个都没有留下来的情况
为了知道将要被弹出的字符在后面是否还会出现，我们可以使用 map 来记录字符与位置的关系，最后记录的就是字符与该字符出现的最后一个索引的关系，这样当我们出栈一个元素的时候，就可以知道栈顶元素是否在后面还有了，如果后面已经没有这个元素了，那就放弃出栈栈顶元素，保证完整性
class Solution {
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
//存储每个字符以及其出现的最后一个位置
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.toCharArray().length; i++) {
map.put(s.charAt(i), i);
}
for (int i = 0; i < s.toCharArray().length; i++) {
char c = s.charAt(i);
//只能在栈中出现一次
if(stack.contains(c)){
continue;
}
//当前元素字典序小于栈顶元素
//并且当前栈顶元素在后面还会出现，则弹出栈顶元素将较小的元素入栈
//这样入栈的就能够保证字典序从上至下递减了
while (!stack.isEmpty() && c < stack.peek()
&& map.get(stack.peek()) > i){
stack.pop();
}
stack.push(c);
}
StringBuilder builder = new StringBuilder();
//拼接单调栈中的元素
while (!stack.isEmpty()){
builder.append(stack.pop());
}
//翻转一下
return builder.reverse().toString();
}
}
Leetcode 1081 不同字符的最小子序列
和 316 一样的，现在做只是为了练 (a) 手 (题)
class Solution {
public String smallestSubsequence(String s) {
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0; i<s.length(); i++){
map.put(s.charAt(i), i);
}
Stack<Character> stack = new Stack<>();
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(stack.contains(c)){
continue;
}
//出栈，保持最小字典序
while(!stack.isEmpty() && c < stack.peek() && map.get(stack.peek()) > i){
stack.pop();
}
stack.push(c);
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
队列
队列的基本应用就是 BFS
Leetcode 102 层序遍历
这道题要求每一层的结点都从左至右组成一个列表，最后组成一个大列表返回
对于这道题，我们可以借助队列来实现，
- 首先我们将根结点入队，然后在队列不为 null 时循环
- 对根结点出队，然后将其值放入一个临时的列表中
- 对根结点的左右孩子进行入队
- 将最上层的结点的所有左右孩子入队后，循环结束，将临时列表放入到待返回的列表中
所以，在这道题目中，最重要的就是对每一层的结点进行遍历，将其值放入列表，然后将所有结点的左右孩子入队，这样就可以逐层的遍历所有结点
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int count = queue.size();
while (count > 0){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
count--;
}
res.add(list);
}
return res;
}
}
Leetcode 107 二叉树的层次遍历II
我还能说什么呢？
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> nodeQue = new LinkedList<>();
nodeQue.add(root);
while (!nodeQue.isEmpty()){
List<Integer> list = new ArrayList<>();
int size = nodeQue.size();
while(size > 0){
TreeNode node = nodeQue.poll();
list.add(node.val);
if(node.left != null){
nodeQue.add(node.left);
}
if(node.right != null){
nodeQue.add(node.right);
}
size--;
}
res.add(list);
}
Collections.reverse(res);
return res;
}
}
但是如果 api 用得熟的话，也可以改用 LinkedList，这样就有一个 addFirst 的方法，这样在添加一层时只需要不断地往头插入，就可以自然的逆序了
Leetcode 103 二叉树的锯齿形层次遍历
这个题。。也很简单，根据上面的模板每次循环后把奇数层的列表翻转一下再放入即可
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
LinkedList<List<Integer>> res = new LinkedList<>();
if(root == null){
return res;
}
Queue<TreeNode> nodeQue = new LinkedList<>();
nodeQue.add(root);
boolean isZ = true;
while (!nodeQue.isEmpty()){
ArrayList<Integer> list = new ArrayList<>();
int size = nodeQue.size();
while (size > 0){
TreeNode node = nodeQue.poll();
list.add(node.val);
if(node.right != null){
nodeQue.add(node.right);
}
if(node.left != null){
nodeQue.add(node.left);
}
size--;
}
//奇数层结果翻转一下再放入即可
if(!isZ){
isZ = true;
}else {
Collections.reverse(list);
isZ = false;
}
res.add(list);
}
return res;
}
}
Leetcode 199 二叉树的右视图
没啥意思。。模板题，一次入列一层，取出链表里的最后一个就是最右边的了
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new LinkedList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
LinkedList<Integer> list = new LinkedList<>();
int size = queue.size();
while (size > 0){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
size--;
}
res.add(list.get(list.size()-1));
}
return res;
}
}
优先队列
Leetcode 347 前 K 个高频元素
对于这道题的第一直觉，就是将数字的出现次数进行统计，然后将其放入到一个列表中并排序
排序完成后，循环 k 次，每次循环在时，从 map 中找出和当前次数相同的 value 对应的 key，然后将这个 key 从 map 中删除，避免重复
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if(nums.length == 0) return new int[0];
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0)+1);
}
List<Integer> list = new LinkedList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
list.add(entry.getValue());
}
//频率排序
list.sort((o1, o2) -> o2 - o1);
int[] res = new int[k];
for (int i = 0; i < res.length; i++) {
//获得 value 对应的 key
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(entry.getValue().equals(list.get(i))){
res[i] = entry.getKey();
//防止获得重复元素
map.remove(entry.getKey());
//防止动态 rud 报错
break;
}
}
}
return res;
}
}
虽然可以 ac，但是题目是有要求的
因此常规的暴力解法是不可取的
但是这种问题很类似于单调栈，但是思考一下，我们是否可以使用单调栈来解决这个问题？答案是 No，思考一下一个序列
[1,1,1,3,4,4,4,4,5,5,5,5,5]
3
如果使用单调栈，根据出现频率进行入栈的话，那么就会出现最后栈中只剩下 5 的情况
因此我们可以考虑维护一个优先队列，如果遍历到的元素的频率比队列中最小频率元素的频率高，则取出队列中频率最小的元素， 将新元素入队，这样我们就变相的维护了一个最小堆
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//统计频率
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num,0)+1);
}
//遍历 map，维护出现频率最高的k个元素
//pair 对象代表一对数字与频率的组合
//compartor 代表入队的次序是升序还是降序
//如果是升序，则在 1 之后入队 2 会变为 1->2
//如果是降序，则在 1 之后入队 2 会变为 2->1
PriorityQueue<Pair> queue = new PriorityQueue<>(
(o1, o2) -> o1.value - o2.value);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//优先队列满时，可能挤掉优先队列中的元素
//如果按照升序入队，则会挤掉当前最小的元素
//这种维护的是一个最小堆
if(queue.size() == k){
if(entry.getValue() > queue.peek().value){
queue.poll();
queue.add(new Pair(entry.getKey(),entry.getValue()));
}
}else{
queue.add(new Pair(entry.getKey(), entry.getValue()));
}
}
//最后是一个
int[] res = new int[k];
for (int i = res.length-1; i >= 0 ; i--) {
res[i] = queue.poll().key;
}
return res;
}
}
class Pair{
Integer key;
Integer value;
public Pair(Integer key, Integer value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "k:"+key+" v:"+value;
}
}
剑指 offer40 最小的 k 个数
没啥好说的，优先队列
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k == 0) return new int[0];
Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i < arr.length; i++) {
if(queue.size() == k){
if(queue.peek() > arr[i]){
queue.poll();
queue.add(arr[i]);
}
}else{
queue.add(arr[i]);
}
}
int[] res = new int[k];
for (int i = 0; i < res.length; i++) {
res[i] = queue.poll();
}
return res;
}
}
Leetcode 659 分割数组为连续子序列
眼望过去貌似和优先队列没什么关系，但是仔细思考下，这道题给的是升序排序的数组，如果我们想要得到一个连续整数序列的长度，那么我们只需要在前一个数字的序列长度的基础上进行累加就好了，但是注意，同一个数字是可能出现多个子序列中的，比如
[1,1,2,2,3]
这个序列中，1,2 这个序列就出现了两次，因此 2 的子序列有 2 个，其中一个子序列被消耗，作为了 3 的基石，而另一个子序列不变依然为 2
再来看下面这个序列
[1,2,2,3,3,4,5]
在这个序列中，3 的序列长度有 1,2,3 组成的 3，也有 2,3 组成的 2，那么当 4 和 5 想要融入的时候，应该选择哪个呢？其实从题意也不难理解，为了组成长度至少为 3 的子序列，应该选择较小的那个，为了方便进行选择，这时候就可以使用优先队列维护一个存储子序列长度的最小堆了
有了上述的几个例子之后，不难知道我们应该将数字与其可能的所有子序列长度对应起来，因此应该使用 map，我们大概可以整理出以下的思路
当我们想要对当前生成新的子序列时，我们需要先判断他前面有没有数字在 map 中
- 如果有的话，就将该数字对应的优先队列中的队首元素出队，即最短子序列长度，然后判断这个数字还有没有其它的子序列，如果已经没有了，将这个数字从 map 中移除；否则就将往当前数字对应的优先队列中塞入这个数字的最短子序列长度 +1 的值
- 如果没有，则往这个数字的优先队列中塞入 1，表示这个数字之前没有可使用的子序列，是一个起始
- 最后，我们遍历 map 中所有剩余的优先队列的队首元素，这些子序列长度是在不断消耗前面子序列的基础上累加来的，因此一旦有 < 3 的，说明最终组成的子序列长度有不满足条件的，返回 false
class Solution {
public boolean isPossible(int[] nums) {
//k:每个数字 v:能够组成的子序列的可能长度
HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
for (int num : nums) {
if(!map.containsKey(num)){
map.put(num, new PriorityQueue<>());
}
//如果num-1在map中存在，取出其最小长度
//然后将其长度+1的值存入num的优先队列中
//否则说明没有可以消耗的，此时num只能以自己为子序列
if(map.containsKey(num-1)){
int len = map.get(num-1).poll();
//如果num-1没有其它子序列长度，说明这个数字已经被消耗完了
//不能再使用num-1组成其它的子序列，将其从map中移除
if(map.get(num-1).isEmpty()){
map.remove(num-1);
}
map.get(num).offer(len+1);
}else{
map.get(num).offer(1);
}
}
//在遍历完成后，map中就只剩下依然有子序列的num，这些num的子序列
//就是不断消耗前面的数字[nums[0],nums[num-1]]得出来的连续子序列
//只要这些连续子序列的值有小于3的，返回 false 即可
for (Map.Entry<Integer, PriorityQueue<Integer>> entry : map.entrySet()) {
if(entry.getValue().peek() < 3){
return false;
}
}
return true;
}
}
Leetcode 1046 最后一块石头的重量
这题也很简单啊，首先把元素放进顺序为高->低的优先队列中，然后每次出队两个元素，如果两个元素不相同，则将它们相减的结果放入队列中，直到队列中只剩下一个元素
最后需要注意的是，队列最后是可能为空的 ( 刚好最后两个石头抵消了 )，因此返回的时候需要判断一下
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->{return o2-o1;});
for (int stone : stones) {
queue.add(stone);
}
System.out.println(queue);
while (queue.size() > 1) {
int x = queue.poll();
int y = queue.poll();
if(x != y){
queue.add(Math.abs(x-y));
}
}
return queue.size() == 0 ? 0:queue.peek();
}
}
Leetcode 973 最接近原点的 K 个点
对于这道题，我们可以维护一个与距离相关的小顶堆，因此问题就在于如何将距离与点对应起来，我采用的是面向对象的方式
当然如果面向对象，那么直接使用 sort 也是很简单的，这里就不再赘述了
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<Point> queue = new PriorityQueue<>(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o1.des() - o2.des();
}
});
int[][] res = new int[k][2];
for (int i = 0; i < points.length; i++) {
int x = points[i][0];
int y = points[i][1];
queue.add(new Point(x, y));
}
for (int i = k-1; i >= 0; i--) {
Point p = queue.poll();
res[i][0] = p.x;
res[i][1] = p.y;
}
return res;
}
}
class Point{
int x;
int y;
//与原点的距离
public Point(int x, int y){
this.x = x;
this.y = y;
}
public int des(){
return x*x + y*y;
}
}
Leetcode 295 数据流的中位数
一开始尝试每次 findMedian 之前排序后再找中位数。。结果超时了，lc nb
思考一下， 我们想要找到的中位数无非就是
- 偶数长度情况下：取两个数的平均值，而且如果将一个有序列表从中间拆分，前一个数就是前半部分的最大值，后一个数就是后半部分的最小值
- 奇数长度情况下：取中间的一个数，那么如果我们能够将维护将有序列表拆分为两个部分，并保持二者的长度之差 <= 1，那么较长的那一部分的第一个数 / 最后一个数就是中位数 ( 取决于让后半部分长还是前半部分长 )
由于排序是不可行的，而且我们最多只需要从两个容器中取出最小值 / 最大值，因此可以使用两个优先队列，一个维护小根堆，一个维护大根堆，在 findMedian 时判断两个堆的长度是否相等，如果相等则结果就是两个堆的队首元素相加 / 2；否则就是小根堆的队首元素 ( 以小根堆长度大于大根堆构造 )
但是，难点就在于如何让 addNum 时的数字移动到其应该在的堆中
- 我们在 addNum 时，判断一下两个堆的大小是否相同，如果相同则往代表前半部分的堆中插入，保持差 1 的大小
- 如果不相同，则往后半部分插入，维持平衡
- 在往前半部分插入时，先在代表后半部分的堆中”流淌”一下，然后取出后半部分堆中的队首元素；反之则在前半部分的堆中”流淌”
class MedianFinder {
Queue<Integer> smallNum;
Queue<Integer> bigNum;
/** initialize your data structure here. */
public MedianFinder() {
smallNum = new PriorityQueue<>();
bigNum = new PriorityQueue<>((x, y)->{return y - x;});
}
public void addNum(int num) {
//如果两个堆的大小相等，就往小的那一堆插。先将要插入的元素在小根堆bigNum里面过一遍，再给smallNum
//保证smallNum 中的元素都小于bigNum
if(smallNum.size() == bigNum.size()){
bigNum.add(num);
smallNum.add(bigNum.poll());
}else{
smallNum.add(num);
bigNum.add(smallNum.poll());
}
}
public double findMedian() {
return bigNum.size() == smallNum.size() ?
((bigNum.peek()+smallNum.peek())*0.5)
:
smallNum.peek() ;
}
}
Leetcode 23 合并K个升序列表
我们将每个链表的首结点添加到一个优先队列中，然后每次出队一个最小的结点连接到待返回的链表中
在拼接完成后，为了遍历完所有的结点，如果被拼接的结点的 next 不为空，则将其加入队列
这样每次都会将最小的一个结点出队拼接，就完成了合并
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//合并 k 个链表，在优先队列中过滤一遍
ListNode dummyNode = new ListNode(0);
PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
//加入所有链表的首结点
for (ListNode list : lists) {
if(list != null){
queue.add(list);
}
System.out.println(list.val);
}
ListNode cur = dummyNode;
//在优先队列中过一遍，每次取出最小的结点链接
while (!queue.isEmpty()){
ListNode node = queue.poll();
cur.next = node;
cur = node;
//依次加入首结点后的所有结点
if(node.next != null){
queue.add(node.next);
}
}
return dummyNode.next;
}
}
Leetcode 692 前K个高频单词
我们可以先统计单词和词频的对应关系 map
然后建立优先队列，因为我们的排序有两种情况，因此我们可以选择建立一个类来表示对应关系，根据词频字段和单词字段来建立优先队列的比较器
然后循环 map，创建对象塞入优先队列
最后建立待返回 list，poll 出优先队列中的前 k 个塞入即可
class Solution {
public List<String> topKFrequent(String[] words, int k) {
HashMap<String, Integer> map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0)+1);
}
PriorityQueue<StringNums> queue = new PriorityQueue<>(new Comparator<StringNums>() {
@Override
public int compare(StringNums o1, StringNums o2) {
if(o1.nums == o2.nums){
return o1.word.compareTo(o2.word);
}
return o2.nums - o1.nums;
}
});
for (Map.Entry<String, Integer> entry : map.entrySet()) {
queue.add(new StringNums(entry.getKey(), entry.getValue()));
}
LinkedList<String> res = new LinkedList<>();
for (int i = 0; i < k; i++) {
res.add(queue.poll().word);
}
return res;
}
}
class StringNums{
String word;
int nums;
public StringNums(String word, int nums) {
this.word = word;
this.nums = nums;
}
}
若有收获，就点个赞吧
0 人点赞
