fork(2) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4.  
  5. /**
  6.  * Created by mac on 12.11.15.
  7.  */
  8. public class Main {
  9.     public static void main(String[] args) {
  10.         Scanner in = new Scanner(System.in);
  11.  
  12.         Map<String,Integer> map = new HashMap<>();
  13.         String string = in.nextLine();
  14.         int value;
  15.         String key;
  16.         for (int i = 0; i < string.length(); i++) {
  17.             key = "" + string.charAt(i);
  18.             if (map.containsKey(key)) {
  19.                 value = map.get(key) + 1; // получение значения по ключу те частоту
  20.                 map.put(key,value);
  21.             } else {
  22.                 map.put(key,1);
  23.             }
  24.         }
  25.         List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
  26.         List<Element> q = new ArrayList<>();
  27.  
  28.         for (int i = 0; i < list.size(); i ++) {
  29.             q.add(new Element(list.get(i).getValue(), list.get(i).getKey()));
  30.         }
  31.  
  32.         Comparator comparator = new Comparator() {
  33.             @Override
  34.             public int compare(Object o1, Object o2) {
  35.                 Element one = (Element) o1;
  36.                 Element two = (Element) o2;
  37.                 return one.p-two.p;
  38.             }
  39.         };
  40.  
  41.         Collections.sort(q,comparator);
  42.         int dl = list.size();
  43.         Element buffer1;
  44.         Element buffer2;
  45.  
  46.         if (list.size() == 1) {
  47.             System.out.println(1 + " " + string.length());
  48.             System.out.println(string.charAt(0) + ": " + "0");
  49.             String simplecode = "";
  50.             for (int i = 0; i < string.length(); i++) {
  51.                 simplecode += "0";
  52.             }
  53.             System.out.println(simplecode);
  54.         } else {
  55.  
  56.             do {
  57.                 buffer1 = extractMin(q);
  58.                 buffer2 = extractMin(q);
  59.                 // добавляем элемент с именем сум двух мин элементов и приоритетом сум двух мин элементов
  60.                 insertElement(q, new Element(buffer1.p + buffer2.p, buffer1.v + buffer2.v, buffer1, buffer2));
  61.             } while (q.size() > 1);
  62.  
  63.             // получаем код 'a'
  64.  
  65.  
  66.             Map<String, String> dictionary = new HashMap<>();
  67.  
  68.             String[] halfresult = new String[q.get(0).v.length()];
  69.  
  70.  
  71.             for (int i = 0; i < q.get(0).v.length(); i++) {
  72.                 String code = "";
  73.                 String symbol = "" + q.get(0).v.charAt(i);
  74.                 Element buffCoding = q.get(0);
  75.                 while ((buffCoding.leftchild != null) && (buffCoding.rightchild != null)) {
  76.                     if (buffCoding.leftchild.v.contains(symbol)) {
  77.                         code += "0";
  78.                         buffCoding = buffCoding.leftchild;
  79.                     } else if (buffCoding.rightchild.v.contains(symbol)) {
  80.                         code += "1";
  81.                         buffCoding = buffCoding.rightchild;
  82.                     }
  83.                 }
  84.                 dictionary.put(symbol, code);
  85.                 halfresult[i] = (symbol + ": " + code);
  86.             }
  87.  
  88.             String resultCode = "";
  89.             for (int i = 0; i < string.length(); i++) {
  90.                 key = "" + string.charAt(i);
  91.                 resultCode += dictionary.get(key);
  92.             }
  93.  
  94.             System.out.println(list.size() + " " + resultCode.length());
  95.  
  96.             for (int i = 0; i < halfresult.length; i ++) {
  97.                 System.out.println(halfresult[i]);
  98.             }
  99.             System.out.println(resultCode);
  100.         }
  101.     }
  102.  
  103.  
  104.     public static class Element{
  105.         int p;
  106.         String v;
  107.         Element leftchild = null;
  108.         Element rightchild = null;
  109.         public Element(int p, String v) {
  110.             this.p = p;
  111.             this.v = v;
  112.         }
  113.  
  114.         public Element(int p, String v, Element leftchild, Element rightchild) {
  115.             this.p = p;
  116.             this.v = v;
  117.             this.leftchild = leftchild;
  118.             this.rightchild = rightchild;
  119.         }
  120.  
  121.     }
  122.  
  123.     public static Element extractMin(List<Element> q) {
  124.         Element buffer = q.get(0);
  125.         for (int i = 1; i < q.size(); i++) {
  126.             q.set(i-1,q.get(i));
  127.         }
  128.         q.remove(q.size()-1);
  129.         return buffer;
  130.     }
  131.  
  132.     public static void insertElement(List<Element> q, Element el) {
  133.         if (q.size() == 0) {
  134.             q.add(el);
  135.             return;
  136.         }
  137.         for (int i = q.size()-1; i >= 0; i--) {
  138.             if (el.p >= q.get(i).p) {
  139.                 q.add(i+1,el);
  140.                 break;
  141.             }
  142.         }
  143.     }
  144.  
  145.  
  146. }
Success #stdin #stdout 0.14s 321280KB
comments (?)
stdin
copy 
cbaaa
stdout
copy 
3 8
a: 
nullnull
https://ideone.com/vXkdr7
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!