数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中不包含 AAA 或 BBB 的字符串
假设我们有两个整数 A 和 B，我们需要返回任何字符串 S，使得 -
S 的长度为 A + B，并且恰好包含 A 个字母 'a' 和 B 个字母 'b'。
字符串 S 中不包含子字符串 “aaa” 和 “bbb”。
所以如果给定的整数是 A = 4，B = 1，则结果将是 “aabaa”。
为了解决这个问题，我们将遵循以下步骤 -
定义一个字符串 ret，初始为空
当 |A – B| >= 2 时，
如果 A > B，则
ret := ret 连接 'aa'
将 A 减 2
如果 B 不为零，则将 'b' 连接到 ret 并将 B 减 1
否则
ret := ret 连接 'bb'
将 B 减 2
如果 A 不为零，则将 'a' 连接到 ret 并将 A 减 1
当 A 或 B 不为零时
如果 A 不为零且（ret 的大小 < 2 或不满足（ret 的大小 >= 2 且 ret 的最后一个元素等于 ret 的倒数第二个元素）且 ret 的最后一个元素为 'a'），则
ret := ret + 'a'，将 A 减 1
如果 B 不为零
ret := ret 连接 'b'，将 B 减 1
否则 ret 连接 'b'，将 B 减 1，如果 A 不为 0，则将 a 连接到 ret 并将 A 减 1
返回 ret
让我们看一下以下实现，以便更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string strWithout3a3b(int A, int B) {
string ret = "";
while(abs(A - B) >= 2){
if(A > B){
ret += 'a';
ret += 'a';
A -= 2;
if(B) {
ret += 'b';
B--;
}
}else{
ret += 'b';
ret += 'b';
B -= 2;
if(A) {
ret += 'a';
A--;
}
}
}
while(A || B){
if(A && (ret.size() < 2 || !(ret.size() >= 2 && ret[ret.size() - 1] == ret[ret.size() - 2] && ret[ret.size() - 1] == 'a') ) ){
ret += 'a';
A--;
if(B) {
ret += 'b';
B--;
}
}else{
ret += 'b';
B--;
if(A) {
ret += 'a';
A--;
}
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.strWithout3a3b(4, 1));
}输入
4 1
输出
"aabaa"
更新于: 2020-04-30
232 次查看
广告