|
| 1 | +packageAlgorithms.facebook; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.Collections; |
| 5 | +importjava.util.HashMap; |
| 6 | +importjava.util.HashSet; |
| 7 | +importjava.util.Iterator; |
| 8 | +importjava.util.LinkedList; |
| 9 | + |
| 10 | +publicclassSortWeight { |
| 11 | +publicstaticvoidmain(String[]args) { |
| 12 | +Stringinput1 ="crab hotdog 9.0 chicken 9.2 pig 9.2"; |
| 13 | +Stringinput2 ="pizza 1 hotdog 2.0"; |
| 14 | +Stringinput3 ="pizza 500 hotdog 2.0"; |
| 15 | +Stringinput4 ="pizza 500 2.0"; |
| 16 | + |
| 17 | +LinkedList<String>list1 =sortWeight(input1); |
| 18 | +LinkedList<String>list2 =sortWeight(input2); |
| 19 | +LinkedList<String>list3 =sortWeight(input3); |
| 20 | +LinkedList<String>list4 =sortWeight(input4); |
| 21 | + |
| 22 | +System.out.println(list1.toString()); |
| 23 | +System.out.println(list2.toString()); |
| 24 | +System.out.println(list3.toString()); |
| 25 | +System.out.println(list4.toString()); |
| 26 | + } |
| 27 | + |
| 28 | +publicstaticLinkedList<String>sortWeight(Stringinput) { |
| 29 | +LinkedList<String>ret =newLinkedList<String>(); |
| 30 | +if (input ==null) { |
| 31 | +returnret; |
| 32 | + } |
| 33 | + |
| 34 | +String[]strs =input.split(" "); |
| 35 | + |
| 36 | +floatdefautWeight =5; |
| 37 | + |
| 38 | +// 当weight = -1，表示这一组食物-重量链还未完成 |
| 39 | +Stringfood =null; |
| 40 | +floatweight =0; |
| 41 | + |
| 42 | +// 记录某重量下所有的食物 |
| 43 | +HashMap<Float,ArrayList<String>>map =newHashMap<Float,ArrayList<String>>(); |
| 44 | + |
| 45 | +// Go through the string. |
| 46 | +for (Strings:strs) { |
| 47 | +// 上一次的food-weight对已经结束 |
| 48 | +if (weight != -1) { |
| 49 | +food =s; |
| 50 | +weight = -1; |
| 51 | + }else { |
| 52 | +floattmp =stringToNumber(s); |
| 53 | +// This is a float, so just add a food to the list. |
| 54 | +if (tmp != -1) { |
| 55 | +weight =tmp; |
| 56 | +addFoodToMap(map,food,weight); |
| 57 | + }else { |
| 58 | +// This is not a float, means that there should be |
| 59 | +// a new food. |
| 60 | +addFoodToMap(map,food,defautWeight); |
| 61 | + |
| 62 | +// 开始新一轮的食物-重量链 |
| 63 | +food =s; |
| 64 | +weight = -1; |
| 65 | + } |
| 66 | + } |
| 67 | + } |
| 68 | + |
| 69 | +//System.out.println(map.toString()); |
| 70 | + |
| 71 | +if (weight == -1) { |
| 72 | +addFoodToMap(map,food,defautWeight); |
| 73 | + } |
| 74 | + |
| 75 | +ArrayList<Float>array =newArrayList<Float>(map.keySet()); |
| 76 | +Collections.sort(array); |
| 77 | + |
| 78 | +for (Floatw:array) { |
| 79 | +ArrayList<String>foods =map.get(w); |
| 80 | +for (Stringelement:foods) { |
| 81 | +ret.addFirst(element); |
| 82 | + } |
| 83 | + } |
| 84 | + |
| 85 | +returnret; |
| 86 | + } |
| 87 | + |
| 88 | +publicstaticvoidaddFoodToMap(HashMap<Float,ArrayList<String>>map,Stringfood, |
| 89 | +floatweight) { |
| 90 | +// 把上一次的食物-重量终结 |
| 91 | +ArrayList<String>list =map.get(weight); |
| 92 | +if (list !=null) { |
| 93 | +// 在相应的重量下添加食物 |
| 94 | +list.add(food); |
| 95 | + }else { |
| 96 | +// 新建一个重量链 |
| 97 | +ArrayList<String>listNew =newArrayList<String>(); |
| 98 | +listNew.add(food); |
| 99 | +map.put(weight,listNew); |
| 100 | + } |
| 101 | + } |
| 102 | + |
| 103 | +// when it is not a float, return -1; |
| 104 | +publicstaticfloatstringToNumber(Stringcur) { |
| 105 | +floatresult = -1; |
| 106 | + |
| 107 | +try { |
| 108 | +result =Float.parseFloat(cur); |
| 109 | + }catch (NumberFormatExceptione) { |
| 110 | +result = -1; |
| 111 | + } |
| 112 | + |
| 113 | +returnresult; |
| 114 | + } |
| 115 | +} |