每日一题:LeetCode:1405.最长的快乐字符串

浏览次数 : 次 2022-02-07

博文字数统计 : 1.1k字 | 阅读所需时长 : 4分

× 文章目录

1. 2022-02-07：LeetCode：1405.最长的快乐字符串

每日一题：LeetCode：1405.最长的快乐字符串
- 时间：2022-02-07
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：数组、堆、优先队列
- 算法：贪心、排序

2022-02-07：LeetCode：1405.最长的快乐字符串

1. 题目描述

题目：原题链接
- 如果字符串中不含有任何 ‘aaa’，’bbb’ 或 ‘ccc’ 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
- 给你三个整数 a，b ，c，请你返回任意一个满足下列全部条件的字符串 s：
  - s 是一个尽可能长的快乐字符串。
  - s 中最多有a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
  - s 中只含有 ‘a’、’b’ 、’c’ 三种字母。
- 如果不存在这样的字符串 s ，请返回一个空字符串 “”。
输入输出规范
- 输入：abc三种字符的个数
- 输出：最长的快乐字符串
输入输出示例
- 输入：a = 1, b = 1, c = 7
- 输出：”ccaccbcc”

2. 方法一：贪心 & 排序 & 二维数组

思路
- 本题是要构造一个只有a、b、c三种字符的字符串，且相同字符不能超过连续两个，类似高中数学中的排列组合问题，如：多种小球间隔排列
- 根据贪心的思想，可以发现，为了构造出最长的合法字符串，每次可以使用当前数量最多的一种字符来填充字符串
- 而当字符串中的后两个字符是相同的种类时，此时根据题目的限制，切换成另一种字符填充(其他两种均可)
- 那么，只需要动态维护一个各个种类字符(本题是abc三种)的个数大小关系，然后每次根据字符串末尾两位是否相等，来决定填充数量最多的字符还是其他字符，并更新字符的个数
- 为了实现字符与其个数的关联，并进行动态排序，需要将字符和其个数保存在特定的结构中
- 方式一：可以直接使用二维数组int[n][2]来存放，int[n][0]表示字符，存为字符对应的char变量的值，注意char与int的转换，int[n][1]表示字符的个数，每次添加字符到字符串后，修改字符个数并重新排序，直到最大的字符个数为0，或者最大有剩余，但其他的字符已经用尽且字符串末尾两个字符为最大字符

题解

public String longestDiverseString(int a, int b, int c) {
       if(a + b + c == 0) return "";
       StringBuilder sb = new StringBuilder();
       int[][] pair = new int[][]{{'a', a}, {'b', b}, {'c', c}};
       while (true) {
           Arrays.sort(pair, (o1, o2) -> o2[1] - o1[1]);
           int[] max = pair[0];
           if(max[1] == 0) break;
           int n = sb.length();
           if(n >= 2 && sb.charAt(n - 1) == max[0] && sb.charAt(n - 2) == max[0]) {
               if(pair[1][1] == 0) break;
               sb.append((char) pair[1][0]);
               pair[1][1]--;
           }else {
               sb.append((char) max[0]);
               max[1]--;
           }
       }
       return sb.toString();
   }

复杂度分析：a、b、c 是三种字符的个数
- 时间复杂度：$O((a+b+c)*ClogC)$，C = 3，每次排序的复杂度为$O(ClogC)$
- 空间复杂度：$O(C)$

3. 方法二：贪心 & 排序 & 堆

思路
- 同样的，也可以使用其他的结构将字符和其个数关联、保存起来
- 方式二：利用堆、优先队列的结构来自动完成定制排序，也可以使用TreeMap的定制排序
- 方式三：使用自定义的类对象，将char类型的字符和int类型的个数以属性的形式关联保存，即官方题解的方式

题解

public String longestDiverseString(int a, int b, int c) {
    if(a + b + c == 0) return "";
    StringBuilder sb = new StringBuilder();
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((o1,o2) -> o2[1] - o1[1]);
    maxHeap.add(new int[]{'a', a});
    maxHeap.add(new int[]{'b', b});
    maxHeap.add(new int[]{'c', c});
    while (!maxHeap.isEmpty()) {
        int n = sb.length();
        int[] max = maxHeap.poll();
        if(max[1] == 0) break;
        if(n >= 2 && sb.charAt(n - 1) == max[0] && sb.charAt(n - 2) == max[0]) {
            int[] mid = maxHeap.poll();
            if(mid[1] == 0) break;
            sb.append((char) mid[0]);
            maxHeap.add(new int[]{mid[0], mid[1] - 1});
            maxHeap.add(max);
        }else {
            sb.append((char) max[0]);
            maxHeap.add(new int[]{max[0], max[1] - 1});
        }
    }
    return sb.toString();
}

复杂度分析：a、b、c 是三种字符的个数
- 时间复杂度：$O((a+b+c)*ClogC)$，C = 3，每次堆排序的复杂度为$O(ClogC)$
- 空间复杂度：$O(C)$

本文作者： Chthollists
发布时间： 2022-02-07 23:16:28
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1405.最长的快乐字符串
本文链接： https://chthollists.github.io/post/4d7c782a.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！