LEETCODE 1405. Longest Happy String 解题思路分析

题目大意:

最长快乐字符串

如果字符串中不含有任何 ‘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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1405

解题思路分析:

本题的最优方案是采用贪心算法,算法核心如下:

  1. 找出a,b,c中个数最多的那个字母,选择2个加入到返回结果(如果不足2个时,将剩余的个数全部加入)。
  2. 重复第一步,如果当前个数最多的字母与上一次相同,那么选择一个个数次多的字母加入返回结果。反之选择2个个数最多的字母加入返回结果(如果不足2个时,将剩余的个数全部加入)。
  3. 直到三中字母的个数都为0时,结束循环。

实现代码:

public String longestDiverseString(int a, int b, int c) {
    StringBuilder sb = new StringBuilder();
    char lastMax='-';
    while(a>0||b>0||c>0){
        if(a>=b&&a>=c){ // 当字母a的个数最多时
            if(lastMax != 'a'){ // 上一次个数最多的字母不是a
                sb.append("a"); // 添加一个a至返回结果
                if(a>1) sb.append("a"); // 如果a还有剩余,再添加一个
                a-=2; // a的个数减去2
                lastMax='a'; // 更新上一个个数最多的字母是a
            }else{ // 如果上一次个数最多的字母也是a
                if(b>c){ // 次多的字母是b
                    sb.append("b"); // 添加一个b
                    b--; // b的个数减一
                    lastMax='b'; // 更新上一个个数最多的字母是a
                }else if(c>0){ // 次多的字母是c
                    sb.append("c"); // 添加一个c
                    c--; // c的个数减一
                    lastMax='c'; // 更新上一个个数最多的字母是c
                }else break;
            }
        }else if(b>=a&&b>=c){
            if(lastMax != 'b'){
                sb.append("b");
                if(b>1) sb.append("b");
                b-=2;
                lastMax='b';
            }else{
                if(a>c){
                    sb.append("a");
                    a--;
                    lastMax='a';
                }else if(c>0){
                    sb.append("c");
                    c--;
                    lastMax='c';
                }else break;
            }
        }else if(c>=a&&c>=b){
            if(lastMax != 'c'){
                sb.append("c");
                if(c>1) sb.append("c");
                c-=2;
                lastMax='c';
            }else{
                if(a>b){
                    sb.append("a");
                    a--;
                    lastMax='a';
                }else if(b>0){
                    sb.append("b");
                    b--;
                    lastMax='b';
                }else break;
            }
        }
    }
    return sb.toString();
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Longest Happy String.

Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Longest Happy String.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1405-longest-happy-string-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。