資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中將字串重新排列成k距離
假設我們有一個非空字串s和一個整數k；我們必須重新排列字串，使得相同的字元之間至少相隔k個距離。給定的字串都是小寫字母。如果沒有辦法重新排列字串，則返回空字串。
因此，如果輸入類似於s = "aabbcc"，k = 3，則輸出將為"abcabc"，這是因為相同的字母之間至少相隔3個距離。
為了解決這個問題，我們將遵循以下步驟：
ret := 空字串
定義一個map m
n := s的長度
for i := 0 to n-1 do −
(m[s[i]]++)
定義一個優先佇列pq
對於m中的每個鍵值對it，執行：
temp := 一個包含it的鍵和值的鍵值對
將temp插入pq
(it++)
定義一個雙端佇列dq
while (pq非空) do −
curr := pq的頂部元素
從pq中刪除元素
ret := ret + curr.first
(curr.second--)
將curr插入dq的末尾
if dq的長度 >= k then −
curr := dq的第一個元素
從dq中刪除第一個元素
if curr.second > 0 then −
將curr插入pq
while (dq非空且dq的第一個元素為0) do −
從dq中刪除第一個元素
return (如果dq為空，則返回ret，否則返回空字串)
示例
讓我們來看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(pair<char, int> a, pair<char, int> b) {
return !(a.second > b.second);
}
};
class Solution {
public:
string rearrangeString(string s, int k) {
string ret = "";
unordered_map<char, int> m;
int n = s.size();
for (int i = 0; i < n; i++) {
m[s[i]]++;
}
unordered_map<char, int>::iterator it = m.begin();
priority_queue<pair<char, int<, vector<pair<char, int>>,
Comparator> pq;
while (it != m.end()) {
pair<char, int> temp = {it->first, it->second};
pq.push(temp);
it++;
}
deque<pair<char, int>> dq;
while (!pq.empty()) {
pair<char, int> curr = pq.top();
pq.pop();
ret += curr.first;
curr.second--;
dq.push_back(curr);
// cout << ret << " " << dq.size() << endl;
if (dq.size() >= k) {
curr = dq.front();
dq.pop_front();
if (curr.second > 0)
pq.push(curr);
}
}
while (!dq.empty() && dq.front().second == 0)
dq.pop_front();
return dq.empty() ? ret : "";
}
};
main() {
Solution ob;
cout << (ob.rearrangeString("aabbcc", 3));
}輸入
"aabbcc", 3
輸出
bacbac
更新於：2020年7月21日
491 次瀏覽
廣告