美团实习生试题１

请设计一个算法，给一个字符串进行二进制编码，使得编码后字符串的长度最短。

import java.util.*;
import java.util.Map.Entry;


public class lessStep {


    public static class Words implements Comparable{
        public Words(Integer count){
            this.count=count;
        }
        Words left,right;
        Integer count;
       public  int weight;


        public Words getLeft() {
        return left;
    }


    public void setLeft(Words left) {
        this.left = left;
    }


    public Words getRight() {
        return right;
    }


    public void setRight(Words right) {
        this.right = right;
    }


    public int getWeight() {
        return weight;
    }


    public void setWeight(int weight) {
        this.weight = weight;
    }


        @Override
        public int compareTo(Object o) {
            // TODO Auto-generated method stub
            Words word=(Words) o;
            if(word.count>count) return 1;
            else return -1;
        }

    }


    int lessSteps(Words word,int height){
        if(word.left==null&&word.right==null) return word.count*height;
        else return lessSteps(word.left,height+1)+lessSteps(word.right,height+1);
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
          Scanner scan=new Scanner(System.in);
          while(scan.hasNext()){
            String str=scan.next();
            Map<Integer,Integer> map=new HashMap<Integer,Integer>();
            char[] alpha=str.toCharArray();

            for(int i=0;i<alpha.length;i++)
              if(map.get(alpha[i]-0)==null) map.put((int)alpha[i],1);
              else map.put((int)alpha[i],map.get(alpha[i]-0)+1);

            System.out.println(map.size()+"----");

            Iterator<Entry<Integer, Integer>> iter=map.entrySet().iterator();
            List<Words> list=new ArrayList<Words>();
            while(iter.hasNext()){
                Words word=new Words(iter.next().getValue());
                list.add(word);
             }
            while(list.size()>1){
                Collections.sort(list);
                Words left=list.get(0),right=list.get(1);
                Words word=new Words(left.count+right.count);
                System.out.println(left.count+","+right.count);
                word.left=left;
                word.right=right;
                list.remove(1);
                list.remove(0);
                list.add(word);
            }

            System.out.println(new lessStep().lessSteps(list.get(0),0));
          }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99