Reorganize String
给一个string, 问能不能重组它, 让每个相邻字符都不一样.
这个题用可以sort可以用pq, 我用的pq.
|
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 |
class Solution { class Pair { int count; char c; Pair(int count, char c) { this.count = count; this.c = c; } } Map<Character, Integer> map = new HashMap<>(); public String reorganizeString(String S) { for(char c : S.toCharArray()) { map.putIfAbsent(c, 0); map.put(c, map.get(c) + 1); } PriorityQueue<Pair> pairs = new PriorityQueue<>((a, b) -> (b.count - a.count)); for(Map.Entry<Character, Integer> e : map.entrySet()) { pairs.add(new Pair(e.getValue(), e.getKey())); } StringBuilder sb = new StringBuilder(); while(!pairs.isEmpty()) { Pair p = pairs.poll(); if(sb.length() >= 1 && sb.charAt(sb.length() - 1) == p.c) { Pair pp = pairs.poll(); if(pp == null) { return ""; } pp.count --; sb.append(pp.c); if(pp.count != 0) pairs.add(pp); } p.count--; sb.append(p.c); if(p.count != 0) pairs.add(p); } return sb.toString(); } } |