【LeetCode】984. String Without AAA or BBB 解题报告(Python)
2024-10-18 00:55:44
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/string-without-aaa-or-bbb/
题目描述
Given two integers A and B, return any string S such that:
- S has length A + B and contains exactly A ‘a’ letters, and exactly B ‘b’ letters;
- The substring ‘aaa’ does not occur in S;
- The substring ‘bbb’ does not occur in S.
Example 1:
Input: A = 1, B = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.
Example 2:
Input: A = 4, B = 1
Output: "aabaa"
Note:
- 0 <= A <= 100
- 0 <= B <= 100
- It is guaranteed such an S exists for the given A and B.
题目大意
构造出来一个字符串,要求出现A个a和B个b,同时要求不能出现连续三个的a或者b.
解题方法
字符串构造
有不少人第一题就扑街了……我虽然一遍过了,但是也花了不少时间。
首先为了简化判断我做了一个设定就是A>B,如果不满足这个条件,就把A和B进行翻转,这里需要注意的是如果翻转A和B,那么需要把A和B对应的’a’和’b’也翻转。这步之后就能保证了A代表的字符是出现多的字符,B代表的是出现次数少的字符。
那么如何构造呢?我想了一个比较巧妙的方法:先构造出成对出现的’a’,‘b’,然后把剩余的字符进行插空。
具体的说,我们保证了构造出的ab是’ab’,当A>B;ab是’ba’,当B>A.即出现次数多的字符在前面。然后我们统计一下剩余的字符还有多少个,很显然是A - B个。然后把剩余的A-B个a插入到ab中间,会构成了aabaab…abab的样子。如果还有剩余的ab对放到后面即可。
这个思路的好处在于,我们优先构造出ab对,在插空的时候不会产生连续aaa或者bbb,而且剩余的一定是abab的形式,因为题目已经保证了可以构造出来,所以不会出现A>>B导致不能构造。
class Solution(object):
def strWithout3a3b(self, A, B):
"""
:type A: int
:type B: int
:rtype: str
"""
_len = A + B
# to make A > B
a, b = ('a', 'b') if A > B else ('b', 'a')
A, B = (A, B) if A > B else (B, A)
ab = [a + b] * B
A -= B
res = []
while A:
res.append(a)
if ab:
res.append(ab.pop())
A -= 1
res += ab
return "".join(res)
日期
2019 年 1 月 27 日 —— 这个周赛不太爽
最新文章
- 使用插件实现一般处理程序导出excel
- 用matlab实现同一个序列重复N倍
- centos搭建https协议的tomcat和apache服务器以及nginx服务器,mysql php
- 临时存存储页面上的数据---js中的cookie
- ARM 汇编的一些规范
- Linux下lzop命令安装
- Win7 系统引导盘(C盘)空间越来越小怎么办?
- C#拼音转换,将简体中文转换成拼音
- Java [leetcode 8] String to Integer (atoi)
- 【转】于request.getSession(true/false/null)的区别
- 微信小程序资料集合
- [原]C++关于运算符重载的程序报错error…
- C语言 realloc为什么要有返回值,realloc返回值具体解释/(解决随意长度字符串输入问题)。
- 移动web点5像素的秘密(转)
- layer弹出层
- java spring mvc 全注解
- WCF-Oracel适配器针对UDT的使用配置与注意事项
- [SCOI2007]排列
- [Ubuntu] 14.04 外接显示器分辨率调整
- 团队作业7——第二次项目冲刺(Beta版本)day1