1、任务系统
算法分析
记录下来一个任务的编号，周期和下次提醒时间，放进按提醒时间从小往大排（提醒时间一样按编号从小往大排）的优先队列，循环k次，每次取队首输出，出队，并将其下次提醒时间加上一周期后重新入队。
时间复杂度 "第13章 二叉树和堆,第1张")
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main {
static int N = 50010;
static PriorityQueue<Pair> q = new PriorityQueue<Pair>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int k = Integer.parseInt(s1[1]);
for(int i = 0;i < n;i ++)
{
String[] s2 = br.readLine().split(" ");
int id = Integer.parseInt(s2[1]);
int time = Integer.parseInt(s2[2]);
q.add(new Pair(id,time,time));
}
while(k -- > 0)
{
Pair t = q.poll();
System.out.println(t.id);
q.add(new Pair(t.id,t.time + t.period,t.period));
}
}
}
class Pair implements Comparable<Pair>
{
int id ,time,period;
Pair(int id,int time,int period)
{
this.id = id;
this.time = time;
this.period = period;
}
@Override
public int compareTo(Pair o) {
// TODO 自动生成的方法存根
if(time == o.time) return Integer.compare(id, o.id);
return Integer.compare(time, o.time);
}
}
2、n个最小和
算法1
对两个数组分别排序，维护一个数量为n的大根堆，始终维护前n小
枚举a[]元素的过程中，依次从小到大枚举b[]
若大根堆的数量小于n，则加进大根堆中
若大根堆的数量大于等于n，
- 1、若a[i] + b[i] >= 堆顶元素，则直接
break - 2、若a[i] + b[i] < 堆顶元素，则大根堆
poll出堆顶元素，把a[i] + b[i]加入到大根堆中
时间复杂度 "第13章 二叉树和堆,第2张")
由于有剪枝的存在，所有会比时间复杂度小很多
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
static PriorityQueue<Long> q = new PriorityQueue<Long>((x,y) -> y.compareTo(x));
static int N = 50010;
static int[] a = new int[N];
static int[] b = new int[N];
static long[] ans = new long[N];
static int k = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s1 = br.readLine().split(" ");
for(int i = 0;i < n;i ++) a[i] = Integer.parseInt(s1[i]);
String[] s2 = br.readLine().split(" ");
for(int i = 0;i < n;i ++) b[i] = Integer.parseInt(s2[i]);
Arrays.sort(a,0,n);
Arrays.sort(b,0,n);
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < n;j ++)
{
int x = a[i] + b[j];
if(q.size() >= n)
{
if(x >= q.peek()) break;
q.poll();
q.add((long) x);
}
else q.add((long) x);
}
}
for(int i = 0;i < n;i ++)
{
ans[k ++] = q.poll();
}
for(int i = n - 1;i >= 0;i --)
{
if(i != 0) System.out.print(ans[i] + " ");
else System.out.println(ans[i]);
}
}
}
算法2
小根堆
先把A数组和B数组从小到大排序，取A数组中的每一个数与B[0]相加，记录取的A的数组下标和B的数组下标和数组中两数之和，放入按和从小到大排的优先队列，每一次取出队首，输出这个和，出队，如果它的B数组下标还没有到最后，就把B的数组下标后移一位，重新计算新的两数之和并入队。
小根堆中共有n个元素，其中每个元素都有a[0],a[1].....a[n - 1]，且唯一，故存储的是a[]数组固定每个元素，搭配b[]数组中的目前可以搭配的最小的元素
证明：由于两个数组从小到大排序，假设a[i]和b[j]是当前优先队列中最小的，由于队列中所有的和始终都有a[]数组的所有元素，则表示a[i]一定是固定的，不需要判断a[i + 1] + b[j]的情况，则把a[i]和b[j + 1]的和添加进去替代a[i]和b[j]即可。
时间复杂度
Java 代码
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static int N = 50010;
static int[] a = new int[N];
static int[] b = new int[N];
static long[] ans = new long[N];
static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
for(int i = 0;i < n;i ++) b[i] = scan.nextInt();
Arrays.sort(a,0,n);
Arrays.sort(b,0,n);
for(int i = 0;i < n;i ++)
{
q.add(new Edge(i,0,a[i] + b[0]));
}
int cnt = 0;
while(cnt < n)
{
Edge t = q.poll();
ans[cnt ++] = t.sum;
q.add(new Edge(t.l,t.r + 1,a[t.l] + b[t.r + 1]));
}
for(int i = 0;i < n;i ++)
{
if(i != n - 1) System.out.print(ans[i] + " ");
else System.out.print(ans[i]);
}
}
}
class Edge implements Comparable<Edge>
{
int l,r;
long sum;
Edge(int l,int r,int sum)
{
this.l = l;
this.r = r;
this.sum = sum;
}
@Override
public int compareTo(Edge o) {
// TODO 自动生成的方法存根
return Long.compare(sum, o.sum);
}
}
3、银行的客户队列
算法分析
这题主要考察的是以结构体为元素的优先队列的大小根堆的运用
小根堆
PriorityQueue<Pair> s = new PriorityQueue<Pair>();
大根堆
PriorityQueue<Pair> h = new PriorityQueue<Pair>((p1, p2) -> p2.compareTo(p1)) ;
Pair结构体有编号id 和 优先级p
- 1操作：将相应的结构体分别扔进大小根堆
- 2操作：将大根堆的队头取出并输出id，且把小根堆相应的结构体删除
- 3操作：将小根堆的队头取出并输出id，且把大根堆相应的结构体删除
时间复杂度
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main {
static PriorityQueue<Pair> s = new PriorityQueue<Pair>();
static PriorityQueue<Pair> h = new PriorityQueue<Pair>((p1, p2) -> p2.compareTo(p1)) ;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
String[] s1 = br.readLine().split(" ");
int op = Integer.parseInt(s1[0]);
if(op == 0) break;
if(op == 1)
{
int id = Integer.parseInt(s1[1]);
int p = Integer.parseInt(s1[2]);
Pair t = new Pair(id,p);
h.add(t);
s.add(t);
}
if(op == 2)
{
if(h.isEmpty())
{
System.out.println(0);
continue;
}
Pair t = h.poll();
System.out.println(t.id);
s.remove(t);
}
if(op == 3)
{
if(s.isEmpty())
{
System.out.println(0);
continue;
}
Pair t = s.poll();
System.out.println(t.id);
h.remove(t);
}
}
}
}
class Pair implements Comparable<Pair>
{
int id,p;
Pair(int id,int p)
{
this.id = id;
this.p = p;
}
@Override
public int compareTo(Pair o) {
// TODO 自动生成的方法存根
return Integer.compare(p, o.p);
}
}
4、二叉树
算法分析
先把二叉树通过前序和中序构建出来，再交换树中所有节点的左右子节点，就变成一棵镜像树，再用队列层次遍历
1、建二叉树
先通过哈希表记录中序遍历序列的元素在中序遍历中哪个位置
找到前序遍历序列的第一个元素在中序遍历序列的位置y，即绿色区域是y结点值的左子树，蓝色区域是y结点值的右子树
2、如何变成一棵镜像树
交换树中所有节点的左右子节点，即得到树的镜像。
求一棵树的镜像的过程：先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的左右两个子节点，当交换完所有非叶节点的左、右子节点之后，就得到了树的镜像。
时间复杂度 "第13章 二叉树和堆,第6张")
Java 代码
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 35;
static int[] a = new int[N];
static int[] b = new int[N];
static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
static int[] ans = new int[N];
static int k = 0;
//通过前序遍历序列和中序遍历序列建树
static Node build(int al,int ar,int bl,int br)
{
if(al > ar || bl > br) return null;
int x = a[al];
int y = map.get(x);
int len = y - bl;
Node root = new Node(x);
root.left = build(al + 1,al + len,bl,y - 1);
root.right = build(al + len + 1,ar,y + 1,br);
return root;
}
//将二叉树镜像翻转
static void dfs(Node root)
{
if(root == null) return;
if(root.left == null && root.right == null) return;
Node temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left != null) dfs(root.left);
if(root.right != null) dfs(root.right);
}
//层次遍历
static void bfs(Node root)
{
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while(!q.isEmpty())
{
Node t = q.poll();
ans[k ++] = t.val;
if(t.left != null) q.add(t.left);
if(t.right != null) q.add(t.right);
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 0;i < n;i ++)
{
b[i] = scan.nextInt();
map.put(b[i], i);
}
for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
Node root = build(0,n - 1,0,n - 1);
dfs(root);
bfs(root);
for(int i = 0;i < k;i ++)
{
if(i != k - 1) System.out.print(ans[i] + " ");
else System.out.println(ans[i]);
}
}
}
class Node
{
Node left;
Node right;
int val ;
Node(int val)
{
this.val = val;
}
}
5、n个最小和加强版
先把所有数组排成有序的，先按照第2题 n个最小和 的方式求出第一个数组和第二个数组的前n小，存到t[]数组中，再求出t[]数组和第三个数组的前n小，存到t[]数组中....
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static int N = 1010;
static long[][] A = new long[N][N];
static long[] ans = new long[N];
static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
int n = scan.nextInt();
for(int i = 0;i < m;i ++)
{
for(int j = 0;j < n;j ++)
{
A[i][j] = scan.nextInt();
}
Arrays.sort(A[i],0,n);
}
for(int i = 0;i < m - 1;i ++)
{
q.clear();
for(int j = 0;j < n;j ++)
{
q.add(new Edge(j,0,A[i][j] + A[i + 1][0]));
}
int cnt = 0;
while(cnt < n)
{
Edge t = q.poll();
ans[cnt ++] = t.sum;
q.add(new Edge(t.l,t.r + 1,A[i][t.l] + A[i + 1][t.r + 1]));
}
for(int j = 0;j < n;j ++) A[i + 1][j] = ans[j];
}
for(int i = 0;i < n;i ++)
{
if(i != n - 1) System.out.print(A[m - 1][i] + " ");
else System.out.print(A[m - 1][i]);
}
}
}
class Edge implements Comparable<Edge>
{
int l,r;
long sum;
Edge(int l,int r,long sum)
{
this.l = l;
this.r = r;
this.sum = sum;
}
@Override
public int compareTo(Edge o) {
// TODO 自动生成的方法存根
return Long.compare(sum, o.sum);
}
}