AcWing 1649. Java 堆路径
原题链接
中等
作者:
ACSaber
,
2020-12-01 18:29:23
,
所有人可见
,
阅读 507
import java.util.*;
import java.io.*;
class Main {
static int N = 1010;
static int[] heap = new int[N];
static int size = 1;
public static void main (String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine());
String[] s = reader.readLine().split(" ");
for (int j = 1; j <= n; j++) heap[j] = Integer.parseInt(s[j - 1]);
size = n;
getLog(writer);
// 判断是否为大根堆
boolean isMax = true;
for (int k = 1; k <= n; k++) {
int root = heap[k];
int left = k * 2 <= size ? heap[k * 2] : Integer.MIN_VALUE;
int right = k * 2 + 1 <= size ? heap[k * 2 + 1] : Integer.MIN_VALUE;
if (root < left || root < right) {
isMax = false;
break;
}
}
if (isMax) {
writer.write("Max Heap");
}
// 判断是否为小根堆
boolean isMin = true;
for (int k = 1; k <= n; k++) {
int root = heap[k];
int left = k * 2 <= size ? heap[k * 2] : Integer.MAX_VALUE;
int right = k * 2 + 1 <= size ? heap[k * 2 + 1] : Integer.MAX_VALUE;
if (root > left || root > right) {
isMin = false;
break;
}
}
if (isMin) {
writer.write("Min Heap");
}
// 都不是
if (!isMax && !isMin) {
writer.write("Not Heap");
}
reader.close();
writer.flush();
writer.close();
}
private static void getLog(BufferedWriter writer) throws IOException {
ArrayList<Integer> list = new ArrayList<>();
dfs(1, size, list, writer);
}
private static void dfs(int i, int n, ArrayList<Integer> list, BufferedWriter writer) throws IOException {
if (i * 2 > n) {
if (i <= n) list.add(heap[i]);
for (int item : list) {
writer.write(item + " ");
}
writer.write("\n");
return;
}
list.add(heap[i]);
if (i * 2 + 1 <= n) {
ArrayList<Integer> copy2 = new ArrayList<>(list);
dfs(i * 2 + 1, n, copy2, writer);
}
if (i * 2 <= n) {
ArrayList<Integer> copy1 = new ArrayList<>(list);
dfs(i * 2, n, copy1, writer);
}
}
}
用java可就真的是太秀了
我一看 “嗬,是啥语言来挑事了”
哦… 原来是 cpp,没事了。