資料結構
網路
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 次檢視
廣告