原题链接:
https://leetcode.cn/problems/reorganize-string/

解法1: 贪心 + 堆

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
class Solution {
    public String reorganizeString(String s) {
        int [] count = new int[26];
        var ss = s.toCharArray();
        int n =  ss.length;
        
        if(n < 2){
            return s;
        }
        
        for(var c:ss){
            count[c - 'a']++;
            if(count[c - 'a'] > (n + 1) >> 1){
                return "";
            }
        }
        
        

        // 大根堆 根据字符的出现次数排序
        PriorityQueue<Character>pq = new PriorityQueue<>(((o1, o2) -> count[o2.charValue() - 'a'] - count[o1.charValue() - 'a']));

        for(var c = 'a' ; c <= 'z' ; c++){
            // 只将 出现次数大于0 入队 提高效率
            if(count[c - 'a'] > 0){
                pq.add(c);   
            }
        }
        
        StringBuffer sb = new StringBuffer();

        while(pq.size() > 1){
            var letter1 = pq.poll();
            var letter2 = pq.poll();
            sb.append(letter1);
            sb.append(letter2);
            count[letter1 - 'a']--;
            count[letter2 - 'a']--;
            if(count[letter1 - 'a'] > 0){
                pq.add(letter1);
            }

            if(count[letter2 - 'a'] > 0){
                pq.add(letter2);
            }
        }

        if(pq.size() > 0){
            sb.append(pq.poll());
        }

        return sb.toString();

    }
}

解法2: 贪心 + 计数