|
| 1 | +package_20160820_1st_contest; |
| 2 | + |
| 3 | +importjava.util.Comparator; |
| 4 | +importjava.util.HashMap; |
| 5 | +importjava.util.HashSet; |
| 6 | +importjava.util.Map; |
| 7 | +importjava.util.Map.Entry; |
| 8 | +importjava.util.PriorityQueue; |
| 9 | +importjava.util.Queue; |
| 10 | +importjava.util.Set; |
| 11 | + |
| 12 | +publicclassFirstUniqChar { |
| 13 | +publicstaticintfirstUniqChar(Strings) { |
| 14 | +Map<Character,Integer>countsMap =newHashMap(); |
| 15 | +Map<Character,Integer>indexMap =newHashMap(); |
| 16 | +Set<Character>uniqSet =newHashSet(); |
| 17 | +for(inti =0;i <s.length();i++){ |
| 18 | +if(!countsMap.containsKey(s.charAt(i))){ |
| 19 | +countsMap.put(s.charAt(i),1); |
| 20 | +indexMap.put(s.charAt(i),i); |
| 21 | +uniqSet.add(s.charAt(i)); |
| 22 | + }else { |
| 23 | +intcurrVal =countsMap.get(s.charAt(i)); |
| 24 | +countsMap.put(s.charAt(i),currVal+1); |
| 25 | +uniqSet.remove(s.charAt(i)); |
| 26 | + } |
| 27 | + } |
| 28 | +intindex =Integer.MAX_VALUE; |
| 29 | +for(charc :uniqSet){ |
| 30 | +if(indexMap.get(c) <index)index =indexMap.get(c); |
| 31 | + } |
| 32 | +return (index ==Integer.MAX_VALUE) ? -1 :index; |
| 33 | + } |
| 34 | + |
| 35 | +publicstaticintfirstUniqChar_dropped(Strings) { |
| 36 | +//TODO: deal with extreme test case |
| 37 | +Map<Character,Integer>map =newHashMap(); |
| 38 | +//use a priorityqueue to hold all candidates, remove it from the pq once it becomes invalid |
| 39 | +Queue<Map.Entry<Character,Integer>>heap =newPriorityQueue<Map.Entry<Character,Integer>>(newComparator<Map.Entry<Character,Integer>>(){ |
| 40 | +@Override |
| 41 | +publicintcompare(Entry<Character,Integer>o1,Entry<Character,Integer>o2) { |
| 42 | +if(o1.getValue() >o2.getValue())return1; |
| 43 | +elseif(o1.getValue() <o2.getValue())return -1; |
| 44 | +elsereturn0; |
| 45 | + } |
| 46 | + }); |
| 47 | + |
| 48 | +for(inti =0;i <s.length();i++){ |
| 49 | +if(!map.containsKey(s.charAt(i))){ |
| 50 | +map.put(s.charAt(i),1); |
| 51 | + }else { |
| 52 | +intcurrVal =map.get(s.charAt(i)); |
| 53 | +map.put(s.charAt(i),currVal+1); |
| 54 | + } |
| 55 | + } |
| 56 | + |
| 57 | +for(Map.Entry<Character,Integer>e :map.entrySet()){ |
| 58 | +heap.offer(e); |
| 59 | + } |
| 60 | + |
| 61 | +while(!heap.isEmpty()){ |
| 62 | +Map.Entry<Character,Integer>curr =heap.poll(); |
| 63 | +if(map.get(curr.getKey()) >1)continue; |
| 64 | +elsereturnmap.get(curr.getKey()); |
| 65 | + } |
| 66 | +return -1; |
| 67 | + } |
| 68 | + |
| 69 | +publicstaticvoidmain(String...strings){ |
| 70 | +// String s = "leetcode"; |
| 71 | +// String s = "loveleetcode"; |
| 72 | +// String s = ""; |
| 73 | +Strings ="fd.fsfew@#$%d"; |
| 74 | +System.out.println(firstUniqChar(s)); |
| 75 | + } |
| 76 | +} |