### 题目描述 如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。 给你三个整数 a，b ，c，请你返回** 任意一个 **满足下列全部条件的字符串 s： - s 是一个尽可能长的快乐字符串。 - s 中** 最多 **有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。 - s 中只含有 'a'、'b' 、'c' 三种字母。 ### 输入输出 #### 示例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" 解释：这是该测试用例的唯一正确答案。 ``` ### 题目解答 #### 思路 采用**贪心**的思路。 1. 先选择数量多的字母加入字符串 2. 如果连着2个相同的字母，那么第三个字母则只能选择次多的进行插空操作 3. 如果此时没有次多的字母进行插空，那么得到最长的字符串。 #### 复杂度分析 **时间复杂度**:字符串最长为a+b+c,同时，每次需要对3个字母数量进行排序，nlogn的复杂度，总时间复杂度如下 $$O((a+b+c) \times 3log3)$$ **空间复杂度**：空间上消耗a+b+c长度的字符串存储，3个字母数量，总空间复杂度 $$O(a+b+c)$$ #### 代码实现 **思路1：**采用二维数组存储字母数量，Array.sort(arr, (x, y) -> y[1]-x[1])排序 ```java public String longestDiverseString(int a, int b, int c) { int[][] arr = {{'a', a}, {'b', b}, {'c', c}}; String s = ""; while(true){ // 每次进行排序， 由大到小排序 Arrays.sort(arr, (x, y) -> y[1] - x[1]); if(arr[0][1] == 0) break; char max_c = (char)arr[0][0]; // 如果连续两个重复， if(s.length()>=2 && max_c == s.charAt(s.length()-1) && max_c == s.charAt(s.length()-2)){ if(arr[1][1] > 0){ s += (char)arr[1][0]; arr[1][1]--; }else{ return s; } }else{ s += (char)arr[0][0]; arr[0][1]--; } } return s; } ``` **思路2：**采用PriorityQueue进行排序，每次poll出来，修改后再offer进去 ```java public String longestDiverseString(int a, int b, int c) { PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> y[1]-x[1]); if(a > 0){ queue.add(new int[]{'a', a}); } if(b > 0){ queue.add(new int[]{'b', b}); } if(c > 0){ queue.add(new int[]{'c', c}); } StringBuilder sb = new StringBuilder(); while(!queue.isEmpty()){ int[] max = queue.poll(); if(max[1]==0) break; if(sb.length()>=2 && sb.charAt(sb.length()-1)==max[0] && sb.charAt(sb.length()-2)==max[0]){ if(queue.isEmpty()) return sb.toString(); int[] mid = queue.poll(); if(mid[1] > 0){ sb.append((char)mid[0]); mid[1]--; queue.offer(mid); }else{ return sb.toString(); } queue.offer(max); }else{ sb.append((char)max[0]); max[1]--; queue.offer(max); } } return sb.toString(); } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复