最长快乐字符串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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java