数据结构
网络
关系数据库管理系统 (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 次浏览
广告