Ryanjxy's Blog

题目一：优先队列（最小堆）操作模拟

【题目描述】
请使用最小堆（Min-Heap）实现一个优先队列。给定若干操作，按要求执行并输出结果。
支持如下三种操作：

1. insert x：向优先队列中插入一个整数 x
2. getmin：输出当前堆中的最小元素
3. delmin：删除当前堆中的最小元素（若堆为空则忽略）
   【输入格式】
   第一行：操作数 n (1 ≤ n ≤ 2×10^5)
   接下来 n 行：每行一个操作（insert x、getmin 或 delmin）
   【输出格式】
   对于每个 getmin 操作，输出当前最小值，占一行。

【输入样例】  
7
insert 3
insert 1
insert 5
getmin
delmin
getmin
delmin
【输出样例】
1
3

代码：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        PriorityQueue<Integer> q=new PriorityQueue<>();
        while(n-->0){
            String op=s.next();
            if(op.equals("insert")) q.add(s.nextInt());
            else if(op.equals("getmin")) System.out.println(q.peek());
            else if(op.equals("delmin") && !q.isEmpty()) q.poll();
        }
    }
}

题目二：根据中序遍历与后序遍历恢复二叉树，并输出先序遍历

【题目描述】
给定一棵二叉树的中序遍历序列与后序遍历序列，请恢复该二叉树，并输出其先序遍历序列。
保证树中节点值互不重复。
【输入格式】
第一行：一个整数 n（1 ≤ n ≤ 10^5）
第二行：中序遍历序列（n 个整数）
第三行：后序遍历序列（n 个整数）
【输出格式】
输出该树的先序遍历序列，用空格分隔。

【输入样例】
7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
【输出样例】
1 2 4 5 3 6 7

代码：

import java.util.*;
public class Main2 {
    static int[] in,post;
    static Map<Integer,Integer> pos=new HashMap<>();
    static StringBuilder sb=new StringBuilder();
    static void build(int il,int ir,int pl,int pr){
        if(il>ir) return;
        int root=post[pr];
        sb.append(root).append(" ");
        int k=pos.get(root);
        int left=k-il;
        build(il,k-1,pl,pl+left-1);
        build(k+1,ir,pl+left,pr-1);
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        in=new int[n];
        post=new int[n];
        for(int i=0;i<n;i++){ in[i]=sc.nextInt(); pos.put(in[i],i); }
        for(int i=0;i<n;i++) post[i]=sc.nextInt();
        build(0,n-1,0,n-1);
        System.out.println(sb.toString());
    }
}