输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。
输出权值。
5 1 2 2 5 9
37
import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; /* * 哈夫曼树 * 求哈夫曼带权路径长度(带权路径长度=非叶子结点权值之和) */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); List<Integer> myList = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { myList.add(scanner.nextInt()); } //List的排序需要使用Collections.sort()方法 Collections.sort(myList); int sum = 0; //记录非叶子结点之和 while (myList.size() > 1) { int temp1 = myList.remove(0); int temp2 = myList.remove(0); sum += temp1+temp2; myList.add(temp1+temp2); Collections.sort(myList); } System.out.println(sum); } } }
//写了这么多,看讨论才知道原来直接省去建立树的过程也能解决。还是大神们眼睛毒啊 //建立哈夫曼树的过程,复试考到过。 import java.util.*; * 哈夫曼树,第一行输入一个数n,表示叶结点的个数。 * 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 */ import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n=sc.nextInt(); PriorityQueue<TreeNode>pq=new PriorityQueue<>(n,new Comparator<TreeNode>() { @Override public int compare(TreeNode o1, TreeNode o2) { return o1.val-o2.val; } }); while(n-->0) { pq.add(new TreeNode(sc.nextInt())); } TreeNode root=buildTree(pq); //层次遍历哈夫曼树,并求和 int sum=bfs(root); System.out.println(sum); } } private static TreeNode buildTree(PriorityQueue<TreeNode> pq) { //使用优先队列建立哈夫曼树妙啊 while(pq.size()>1) { TreeNode left=pq.poll(); TreeNode right=pq.poll(); TreeNode parent=new TreeNode(left.val+right.val); parent.left=left; parent.right=right; pq.add(parent); } return pq.poll(); } private static int bfs(TreeNode root) { Queue<TreeNode>queue=new LinkedList<>(); queue.offer(root); int depth=-1;//不是从0开始。开始错了 int sum=0; while(!queue.isEmpty()) { int size=queue.size(); depth++; while(size-->0) { TreeNode node=queue.poll(); if(node.left==null&&node.right==null)//哈夫曼树叶子结点才算入 sum+=node.val*depth; if(node.left!=null)queue.offer(node.left); if(node.right!=null)queue.offer(node.right); } } return sum; } } class TreeNode { TreeNode left; TreeNode right; int val; public TreeNode(int val) { this.val=val; } }
import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); PriorityQueue<Integer> queue = new PriorityQueue<>(); for (int i = 0; i < n; i++) queue.add(scanner.nextInt()); int weight=0; while (queue.size()!=1){ Integer a = queue.poll(); Integer b = queue.poll(); weight+=a+b; queue.add(a+b); } System.out.println(weight); } }
import java.util.Arrays; import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()) { int n = scanner.nextInt(), sum = 0; int[] nums = new int[n]; for(int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } for(int i = 0; i < n - 1; i++) { Arrays.sort(nums, i, n); nums[i + 1] = nums[i] +nums[i + 1]; nums[i] = 0; sum += nums[i + 1]; } System.out.println(sum); } } }
//最关键因素是哈夫曼树最小路径长度的求法,一种简单的方法是所有非叶子节点之和 //明白这个道理之后就可以不用建堆、建树 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { int sum=0; Scanner in = new Scanner(System.in); int count = in.nextInt(); int[] num = new int[count]; for(int i=0;i<count;i++) { num[i] = in.nextInt(); } Arrays.sort(num); if(count==1) { System.out.println(num[0]); }else if(count==2) { System.out.println(num[0]+num[1]); }else { for(int i=0;i<count-1;i++) { num[i+1]=num[i]+num[i+1]; sum+=num[i+1]; Arrays.sort(num,i+1,count); } System.out.println(sum); } in.close(); } }
import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main{ static List ye =new ArrayList(); static int n; public static void main(String[] args){ Scanner in = new Scanner(System.in); int min1; int min2; while(in.hasNext()){ n =in.nextInt(); for(int i=0;in;i++){ ye.add(in.nextInt()); } int result =0; while(n>1){//执行n-1次即可 Collections.sort(ye); min1=ye.remove(0); min2=ye.remove(0); ye.add(min1+min2); result+=min1+min2; n--; } System.out.println(result); } } }
import java.util.PriorityQueue; import java.util.Scanner; /** * Created by fhqplzj on 17-2-19 at 下午8:03. */ public class Huff { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNextInt()) { int n = scanner.nextInt(); PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(n); for (int i = 0; i < n; i++) { priorityQueue.add(scanner.nextInt()); } int result = 0; while (priorityQueue.size() > 1) { int a = priorityQueue.poll(); int b = priorityQueue.poll(); result += a + b; priorityQueue.add(a + b); } System.out.println(result); } } }优先队列