数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中重新排列字符串中的字符，使得没有两个相同的字符相邻
给定一个字符串，例如 str，其长度任意。任务是重新排列给定的字符串，使其结果字符串中没有两个相同的字符相邻。
让我们看看这个的各种输入输出场景 -
输入 - 字符串 str = "itinn"
输出 - 使得没有两个相同的字符相邻的字符串字符的重新排列是：initn。
解释 - 给定一个字符串类型的变量，例如 str。现在，我们将以这样的方式重新排列输入字符串的字符，即没有两个相同的字符出现在相同的位置，即移动 'nn'，因为它们是相同的并且彼此相邻。因此，最终字符串将是 'initn'。
输入 - 字符串 str = "abbaabbaa"
输出 - 使得没有两个相同的字符相邻的字符串字符的重新排列是：ababababa
解释 - 给定一个字符串类型的变量，例如 str。现在，我们将以这样的方式重新排列输入字符串的字符，即没有两个相同的字符出现在相同的位置，即移动 'bb'、'aa'、'bb'、'aa'，因为它们是相同的并且彼此相邻。因此，最终字符串将是 'ababababa'。
下面程序中使用的方案如下
输入一个字符串类型的变量，例如 str，并计算字符串的大小并将其存储在一个名为 length 的变量中。
检查 IF length 为 0 则返回。
将数据传递给函数 Rearrangement(str, length)。
在函数 Rearrangement(arr, length) 内部
将字符串的大小设置为 (length + 1)/2。
声明一个向量类型的变量为 vec(26, 0)，它将存储整数类型的数据，以及一个字符串类型的指针为 ptr(length, ‘ ‘)。一个整数类型的临时变量为 0。
开始循环 FOR 以迭代 str 通过它。在循环内部，设置 vec[it - ‘a’]++。
创建一个字符类型的变量为 ch 并将其设置为对 maximum(vec) 函数的调用。
声明一个整数类型的变量为 total 并将其设置为 vec[ch - ‘a’]。
检查 IF total 大于 size 则返回。
开始循环 WHILE total 然后将 ptr[temp] 设置为 ch，将 temp 设置为 temp + 2 并将 total 减 1。
将 vec[ch - 'a'] 设置为 0。开始循环 FOR 从 i 为 0 到 i 小于 26。在循环内部，开始 while vec[i] 大于 0。将 temp 设置为 (temp >= length) ? 1 : temp 并将 ptr[temp] 设置为 'a' + i 以及 temp 设置为 temp + 2 并将 vec[i] 减 1。
返回 ptr
在函数 char maximum(const vector<int>& vec) 内部
声明一个整数类型的变量为 high 为 0 以及字符类型的变量为 'c'
开始循环 FOR 从 i 为 0 到 i 小于 26。在循环内部，检查 IF vec[i] 是否小于 high，然后将 high 设置为 vec[i] 并将 c 设置为 'a' + i。
返回 c
打印结果。
示例
#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
int high = 0;
char c;
for(int i = 0; i < 26; i++){
if(vec[i] > high){
high = vec[i];
c = 'a' + i;
}
}
return c;
}
string Rearrangement(string str, int length){
int size = (length + 1) / 2;
vector<int> vec(26, 0);
string ptr(length, ' ');
int temp = 0;
for(auto it : str){
vec[it - 'a']++;
}
char ch = maximum(vec);
int total = vec[ch - 'a'];
if(total > size){
return "";
}
while(total){
ptr[temp] = ch;
temp = temp + 2;
total--;
}
vec[ch - 'a'] = 0;
for(int i = 0; i < 26; i++){
while (vec[i] > 0){
temp = (temp >= length) ? 1 : temp;
ptr[temp] = 'a' + i;
temp = temp + 2;
vec[i]--;
}
}
return ptr;
}
int main(){
string str = "itinn";
int length = str.length();
if(length == 0){
cout<<"Please enter a valid string";
}
string count = Rearrangement(str, length);
if(count == ""){
cout<<"Please enter a valid string";
}
else{
cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
}
return 0;
}输出
如果我们运行以上代码，它将生成以下输出
Rearrangement of characters in a string such that no two adjacent are same is: initn
864 次查看
