資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 最長快樂字串
假設有一個字串。如果該字串不包含任何諸如“aaa”、“bbb”或“ccc”之類的子字串，則稱其為快樂字串。如果我們有三個整數 a、b 和 c，則返回任何滿足以下條件的字串 s：
s 是快樂的，並且儘可能長。
s 最多包含 an 次字母“a”、最多 b 次字母“b”和最多 c 次字母“c”。
s 僅包含字母“a”、“b”和“c”。
如果沒有這樣的字串，則返回空字串。
因此，如果輸入類似於 a = 1、b = 1、c = 7，則輸出將為“ccaccbcc”。
為了解決這個問題，我們將遵循以下步驟：
定義一個數據結構，其中包含字元 a、inx 和 cnt。
定義一個優先順序佇列 pq，這將根據資料 cnt 的值進行優先順序排序。
如果 a 不為零，則：
將 new Data('a', a, 0) 插入到 pq 中。
如果 b 不為零，則：
將 new Data('b', b, 0) 插入到 pq 中。
如果 c 不為零，則：
將 new Data('c', c, 0) 插入到 pq 中。
idx := 1
ret := 空字串
當 true 不為零時，執行以下操作：
temp := pq 的頂部元素。
從 pq 中刪除元素。
如果 ret 的大小不為 0 且 ret 的最後一個元素與 temp.a 相同，則：
如果 pq 為空，則：
退出迴圈。
x := temp
temp := pq 的頂部元素。
從 pq 中刪除元素。
將 x 插入到 pq 中。
val := 0
如果 pq 不為空且 temp 的 cnt - pq 的第一個元素的 cnt < 2，則：
val := 1
否則
val := temp 的 cnt 和 2 的最小值。
ret := ret 連線從 temp.a 的索引到 val 結尾的 val。
temp.cnt := temp.cnt - val
如果 pq 為空，則：
退出迴圈。
temp.idx := idx
如果 temp.cnt > 0，則：
將 temp 插入到 pq 中。
(將 idx 增加 1)
返回 ret。
示例
讓我們看一下以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
struct Data{
char a;
int cnt;
int idx ;
Data(char c, int x, int k){
a = c;
cnt = x;
idx = k;
}
};
struct Cmp{
bool operator()(Data& a, Data& b) {
return !(a.cnt>b.cnt);
}
};
class Solution {
public:
string longestDiverseString(int a, int b, int c) {
priority_queue<Data, vector<Data>, Cmp> pq;
if (a)
pq.push(Data('a', a, 0));
if (b)
pq.push(Data('b', b, 0));
if (c)
pq.push(Data('c', c, 0));
int idx = 1;
string ret = "";
while (true) {
Data temp = pq.top();
pq.pop();
if (ret.size() && ret.back() == temp.a) {
if (pq.empty())
break;
Data x = temp;
temp = pq.top();
pq.pop();
pq.push(x);
}
int val = 0;
if (!pq.empty() && temp.cnt - pq.top().cnt < 2) {
val = 1;
}
else
val = min(temp.cnt, 2);
ret += string(val, temp.a);
temp.cnt -= val;
if (pq.empty())
break;
temp.idx = idx;
if (temp.cnt > 0)
pq.push(temp);
idx++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestDiverseString(1,1,7));
}輸入
1,1,7
輸出
ccbccacc
586 次瀏覽
