赞
踩
第九届 蓝桥杯 javaB组 堆的计数 全排列 我们知道包含 N 个元素的堆可以看成是一棵包含 N 个节点的完全二叉树。 每个节点有一个权值。对于小根堆来说,父节点的权值一定小于其子节点的权值。 假设 N 个节点的权值分别是 1~N,你能求出一共有多少种不同的小根堆吗? 例如对于 N=4 有如下 3 种: 1 / 2 3 / 4 1 / 3 2 / 4 1 / 2 4 / 3 由于数量可能超过整型范围,你只需要输出结果除以 1000000009 的余数。 【输入格式】 一个整数 N。 对于 40% 的数据,1 <= N <= 1000 对于 70% 的数据,1 <= N <= 10000 对于 100% 的数据,1 <= N <= 100000 【输出格式】 一个整数表示答案。 【输入样例】 4 【输出样例】 3 资源约定: 峰值内存消耗(含虚拟机) < 256M CPU 消耗 < 1000ms 请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。 所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。 不要使用 package 语句。不要使用 jdk1.7 及以上版本的特性。 主类的名字必须是:Main,否则按无效代码处理。
思路:
将数转换为数组,从arr[0]开始,一个结点的子结点可以表示为arr[i * 2 + 1]与arr[i * 2 + 2]。
转为数组表示后,我们就可以开始全排列,之后对每一个全排列的结果进行检查,如果符合要求,ans++。
import java.util.Scanner; public class Main{ static int ans = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = i + 1; } fullSort(arr, 0, arr.length - 1); System.out.println(ans); } private static void fullSort(int[] arr, int start, int end) { if (start == end) { if (check(arr)) { // for (int i : arr) { // System.out.print(i + " "); // } // System.out.println(); ans++; } return; } for (int i = start; i <= end; i++) { swap(arr, i, start); fullSort(arr, start + 1, end); swap(arr, i, start); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static boolean check(int[] arr) { boolean flag = false; for (int i = 0; i < arr.length; i++) { if ((i * 2 + 1) < arr.length && (i * 2 + 2) < arr.length && arr[i] < arr[i * 2 + 1] && arr[i] < arr[i * 2 + 2]) { flag = true; } else if ((i * 2 + 1) < arr.length && (i * 2 + 2) >= arr.length && arr[i] < arr[i * 2 + 1]) { flag = true; } else if ((i * 2 + 1) >= arr.length) { flag = true; } else { flag = false; return false; } } return flag; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。