专栏首页Michael阿明学习之路LeetCode 984. 不含 AAA 或 BBB 的字符串(贪心)

LeetCode 984. 不含 AAA 或 BBB 的字符串(贪心)

1. 题目

给定两个整数 A 和 B,返回任意字符串 S,要求满足:

  • S 的长度为 A + B,且正好包含 A 个 ‘a’ 字母与 B 个 ‘b’ 字母;
  • 子串 ‘aaa’ 没有出现在 S 中;
  • 子串 ‘bbb’ 没有出现在 S 中。
示例 1:
输入:A = 1, B = 2
输出:"abb"
解释:"abb", "bab" 和 "bba" 都是正确答案。

示例 2:
输入:A = 4, B = 1
输出:"aabaa"
 
提示:
0 <= A <= 100
0 <= B <= 100
对于给定的 A 和 B,保证存在满足要求的 S。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/string-without-aaa-or-bbb 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 贪心

  • 先用A,B的较小的数
n=min(A,B)

生成 n 个 ab,或者 ba, 谁多,谁打头

  • 然后剩余的 a 或者 b 插空,即可
class Solution {
public:
    string strWithout3a3b(int A, int B) {
        int n = min(A,B), i = 0;
        A -= n;
        B -= n;
        string ans;
        while(n--)
        	if(A>=B)
        		ans += "ab";
        	else
        		ans += "ba";
        if(A)
        {
        	while(A--)
        	{
                if(i > ans.size())
                    ans.push_back('a');
                else
        		    ans.insert(i,1,'a');
        		i += 3;
        	}
        }
        if(B)
        {
        	while(B--)
        	{
                if(i > ans.size())
                    ans.push_back('b');
                else
        		    ans.insert(i,1,'b');
        		i += 3;
        	}
        }
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 67. 二进制求和

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-binary 著作权归领扣网络所有。商业转载...

    Michael阿明
  • 程序员面试金典 - 面试题 16.22. 兰顿蚂蚁(deque模拟)

    一只蚂蚁坐在由白色和黑色方格构成的无限网格上。 开始时,网格全白,蚂蚁面向右侧。 每行走一步,蚂蚁执行以下操作。

    Michael阿明
  • LeetCode 1363. 形成三的最大倍数(贪心,难)

    给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

    Michael阿明
  • 12:加密的病历单

    12:加密的病历单 总时间限制: 1000ms 内存限制: 65536kB描述 小英是药学专业大三的学生,暑假期间获得了去医院药房实习的机会。  在药房实习期...

    attack
  • 开始使用Octave

    mwangblog
  • Gym 100952H&&2015 HIAST Collegiate Programming Contest H. Special Palindrome【dp预处理+矩阵快速幂/打表解法】

    H. Special Palindrome time limit per test:1 second memory limit per test:64 mega...

    Angel_Kitty
  • LeetCode 67. 二进制求和

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-binary 著作权归领扣网络所有。商业转载...

    Michael阿明
  • 【Gym 100947C】Rotate It !!

    饶文津
  • 剑指offer——丑数

    题目描述 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑...

    AI那点小事
  • NYOJ----次方求模

    次方求模 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 求a的b次方对c取余的值 输入第一行输入一个整数n表示测试数据的组数...

    Gxjun

扫码关注云+社区

领取腾讯云代金券