新闻详情

新闻详情

首页 / 资讯中心 / 详情

贪心题目:不含 AAA 或 BBB 的字符串

发布时间:2026/11/22 2:25:17来源:尧图网络
贪心题目:不含 AAA 或 BBB 的字符串
文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题不含 AAA 或 BBB 的字符串出处984. 不含 AAA 或 BBB 的字符串难度4 级题目描述要求给定两个整数a \texttt{a}a和b \texttt{b}b返回任意满足以下要求的字符串s \texttt{s}ss \texttt{s}s的长度为a b \texttt{a} \texttt{b}ab且正好包含a \texttt{a}a个字母‘a’ \texttt{a}‘a’与b \texttt{b}b个字母‘b’ \texttt{b}‘b’。子串aaa \texttt{aaa}aaa没有出现在s \texttt{s}s中。子串bbb \texttt{bbb}bbb没有出现在s \texttt{s}s中。示例示例 1输入a 1, b 2 \texttt{a 1, b 2}a 1, b 2输出abb \texttt{abb}abb解释abb \texttt{abb}abb、bab \texttt{bab}bab和bba \texttt{bba}bba都是正确答案。示例 2输入a 4, b 1 \texttt{a 4, b 1}a 4, b 1输出aabaa \texttt{aabaa}aabaa数据范围0 ≤ a, b ≤ 100 \texttt{0} \le \texttt{a, b} \le \texttt{100}0≤a, b≤100对于给定的a \texttt{a}a和b \texttt{b}b保证存在满足要求的s \texttt{s}s解法思路和算法这道题要求构造字符串s ss满足由a aa个字母‘a’ \text{a}‘a’和b bb个字母‘b’ \text{b}‘b’组成且不存在三个相同的连续字母因此相同字母最多连续出现两次。在b bb的值确定的情况下a aa的值最大时对应的s ss由b bb组“aab \text{aab}“aab以及一组“aa \text{aa}“aa构成此时s ss的长度是a b 3 b 2 a b 3b 2ab3b2因此a 2 b 2 a 2b 2a2b2。当b 0 b 0b0时也适用。同理可知在a aa的值确定的情况下b bb的最大值是2 a 2 2a 22a2。因此非负整数a aa和b bb满足0 ≤ a ≤ 2 b 2 0 \le a \le 2b 20≤a≤2b2和0 ≤ b ≤ 2 a 2 0 \le b \le 2a 20≤b≤2a2。当a b a bab时用x xx表示每个字母的出现次数则s ss可以由x xx组“ab \text{ab}“ab构成此时s ss中的任意两个相邻字母都不相同。当a ≠ b a \ne bab时出现次数较多的字母将在s ss中连续出现构造时应满足相同字母最多连续出现两次。以下考虑a b a bab的情况对于a b a bab的情况做法相同只要将两个字母交换即可。当a b 0 a b 0ab0时每次将一组“aab \text{aab}“aab拼接到s ss的末尾则每次使用两个‘a’ \text{a}‘a’和一个‘b’ \text{b}‘b’因此将a aa的值减2 22将b bb的值减1 11此时s ss中不存在三个相同的连续字母。重复该操作直到a b a bab或b 0 b 0b0。如果a b a bab则每次将一组“ab \text{ab}“ab拼接到s ss的末尾每次使用一个‘a’ \text{a}‘a’和一个‘b’ \text{b}‘b’因此将a aa的值减1 11将b bb的值减1 11此时s ss中不存在三个相同的连续字母。重复该操作直到a b 0 a b 0ab0。如果a 0 a 0a0且b 0 b 0b0则将剩余的‘a’ \text{a}‘a’拼接到s ss的末尾。上述做法使用贪心策略贪心策略的正确性说明如下。当a b 0 a b 0ab0时每次将一组“aab \text{aab}“aab拼接到s ss的末尾因此s ss为空或者s ss的最后一个字母是‘b’ \text{b}‘b’。由于每一次拼接的两个或三个字母都以‘a’ \text{a}‘a’开始且最多有两个连续的‘a’ \text{a}‘a’因此不会出现三个相同的连续字母。由于保证存在满足要求的s ss因此当a 0 a 0a0且b 0 b 0b0时必有a ≤ 2 a \le 2a≤2此时s ss为空或者s ss的最后一个字母是‘b’ \text{b}‘b’将剩余的‘a’ \text{a}‘a’拼接到s ss的末尾不会出现三个相同的连续字母。代码classSolution{publicStringstrWithout3a3b(inta,intb){StringBuffersbnewStringBuffer();while(abb0){sb.append(aab);a-2;b--;}while(baa0){sb.append(bba);b-2;a--;}while(a0b0){sb.append(ab);a--;b--;}while(a0){sb.append(a);a--;}while(b0){sb.append(b);b--;}returnsb.toString();}}复杂度分析时间复杂度O ( a b ) O(a b)O(ab)其中a aa和b bb分别是s ss中的字母‘a’ \text{a}‘a’和字母‘b’ \text{b}‘b’的个数。需要构造长度为a b a bab的字符串拼接每个字母的时间是O ( 1 ) O(1)O(1)。空间复杂度O ( a b ) O(a b)O(ab)其中a aa和b bb分别是s ss中的字母‘a’ \text{a}‘a’和字母‘b’ \text{b}‘b’的个数。需要创建一个长度为a b a bab的StringBuffer \texttt{StringBuffer}StringBuffer或StringBuilder \texttt{StringBuilder}StringBuilder类型的对象。由于 Java 中的String \texttt{String}String类型的对象不可变因此空间复杂度至少为O ( a b ) O(a b)O(ab)。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/21 14:14:45

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/21 14:14:26

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/21 21:08:55

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/22 1:51:41

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/21 19:02:25

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/21 14:13:11

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉