2018 阿里编程测验题目 求大神给思路！

哈弗曼树？？？对 就是这个思路。。。

如大神说的,哈夫曼树实现,有不对的地方请大家指正 public class Main { static class Node{ int v; Node lChild; Node rChild; public Node(){} public Node(int v){ this.v = v; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); List<Node> list = new ArrayList<Node>(); for(int i=0;i<n;i++){ list.add(new Node(scanner.nextInt())); } Node root = createHuff(list); System.out.println(getMin(root)); } private static int getMin(Node node) { if(node.lChild == null){ return 0; } if(node.lChild != null && node.rChild != null){ return node.v + getMin(node.lChild) + getMin(node.rChild); } return 0; } private static Node createHuff(List<Node> list) { while(list.size()>1){ sortList(list); Node parent = new Node(list.get(0).v + list.get(1).v); Node lChild = list.remove(0); Node rChild = list.remove(0); parent.lChild = lChild; parent.rChild = rChild; list.add(parent); } return list.get(0); } private static void sortList(List<Node> list){ for(int i=0;i<list.size();i++){ int index = i; int min = list.get(i).v; for(int j=i+1;j<list.size();j++){ if(min > list.get(j).v) { min = list.get(j).v; index = j; } } if(index != i){ Node tmp = list.get(i); list.set(i, list.get(index)); list.set(index, tmp); } } } }

一楼正解

每次找数组能组成的最接近的两个和，然后递归求两边，不知道这样能不能解