最长快乐字符串Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
- s 是一个尽可能长的快乐字符串。
- s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
- s 中只含有 'a'、'b' 、'c' 三种字母。 如果不存在这样的字符串 s ，请返回一个空字符串 ""。
示例 1：
输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。
示例 2：
输入：a = 2, b = 2, c = 1
输出："aabbc"
示例 3：
输入：a = 7, b = 1, c = 0
输出："aabaa"
解释：这是该测试用例的唯一正确答案。
提示：
- 0 <= a, b, c <= 100
- a + b + c > 0
# 思路
优先队列
# 解法
class Solution {
public String longestDiverseString(int a, int b, int c) {
/*
1.每次都从最长的开始选取 如果选的会造成3个连续字母 则换下一个最长的 此时想到优先队列
2.一维数组 第一个和第二个值分别表示其 字母 和 所剩个数
*/
//优先队列
PriorityQueue<int[]> queue=new PriorityQueue(new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
return o2[1]-o1[1];
}
});
StringBuilder str=new StringBuilder();
//相当于0+'a'='a' 1+'a'='b'
if(a!=0)
queue.add(new int[]{0,a});//0 为'a' a为所剩个数
if(b!=0)
queue.add(new int[]{1,b});//0 为'b' b为所剩个数
if(c!=0)
queue.add(new int[]{2,c});//0 为'c' c为所剩个数
//开始遍历
while(!queue.isEmpty()){
//出队 此时出队的元素为所剩个数最多的 字母
int[] curr=queue.poll();
//首先判断str长度 和出队元素 是否和字符串末尾两个元素相等
int n=str.length();
//str.charAt(n-1)-'a' 转化为了数字比较
if(n>=2 && str.charAt(n-1)-'a'==curr[0] && str.charAt(n-2)-'a'==curr[0]){
if(queue.isEmpty()) break;
//如果相等 就重新出队一个 个数最多的
int[] next=queue.poll();
str.append((char)(next[0]+'a'));
next[1]--;
if(next[1]!=0)
queue.add(next);
//重新入队刚进入循环时 拿出来的元素
queue.add(curr);
}else{//不相等 就直接拼接 然后个数-1
if(curr[1]>0){
str.append((char)(curr[0]+'a'));
curr[1]--;
// 如果剩余个数不等于0 则重新入队
if(curr[1]!=0)
queue.add(curr);
}
}
}
return str.toString();
}
}
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
57
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
57
# 总结
- 分析出几种情况，然后分别对各个情况实现
