Chúng ta được cung cấp một chuỗi, giả sử, str có độ dài bất kỳ. Nhiệm vụ là sắp xếp lại chuỗi đã cho theo cách sao cho không có các ký tự liền kề giống nhau được sắp xếp cùng nhau trong chuỗi kết quả.
Hãy để chúng tôi xem các kịch bản đầu ra đầu vào khác nhau cho việc này -
Đầu vào - string str ="itinn"
Đầu ra - Sắp xếp lại các ký tự trong một chuỗi sao cho không có hai ký tự liền kề nào giống nhau là:initn.
Giải thích - Chúng tôi được cung cấp một biến kiểu chuỗi, giả sử, str. Bây giờ chúng ta sẽ sắp xếp lại các ký tự của một chuỗi đầu vào theo cách sao cho không có hai ký tự giống nhau nào xảy ra ở cùng một vị trí, tức là chuyển ‘nn’ vì chúng giống nhau và liền kề nhau. Vì vậy, chuỗi cuối cùng sẽ là ‘initn’.
Đầu vào - string str ="abbaabbaa"
Đầu ra - Sắp xếp lại các ký tự trong một chuỗi sao cho không có hai ký tự liền kề nào giống nhau là:ababababa
Giải thích - Chúng tôi được cung cấp một biến kiểu chuỗi, giả sử, str. Bây giờ chúng ta sẽ sắp xếp lại các ký tự của một chuỗi đầu vào theo cách sao cho không có hai ký tự giống nhau nào xuất hiện ở cùng một vị trí, tức là chuyển 'bb', 'aa', 'bb', 'aa' vì chúng giống nhau và liền kề với mỗi khác. Vì vậy, chuỗi cuối cùng sẽ là 'ababababa'.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập một biến kiểu chuỗi, giả sử, str và tính toán kích thước của một chuỗi và lưu trữ nó trong một biến có độ dài được đặt tên.
-
Kiểm tra độ dài IF là 0 rồi trả về.
-
Truyền dữ liệu vào hàm Sắp xếp lại (str, chiều dài).
-
Bên trong chức năng Sắp xếp lại (arr, length)
-
Đặt kích thước của một chuỗi với (chiều dài + 1) / 2.
-
Khai báo một biến kiểu vectơ là vec (26, 0) sẽ lưu dữ liệu kiểu số nguyên và một ptr kiểu chuỗi là ptr (length, ‘‘). Một biến tạm thời có kiểu số nguyên là 0.
-
Bắt đầu vòng lặp FOR để lặp lại str qua nó. Bên trong vòng lặp, đặt vec [it - ‘a’] ++.
-
Tạo một biến kiểu ký tự là ch và đặt nó bằng một lệnh gọi đến hàm tối đa (vec).
-
Khai báo một biến kiểu số nguyên là biến tổng và đặt nó bằng vec [ch - ‘a’].
-
Kiểm tra tổng NẾU lớn hơn kích thước rồi trả về.
-
Bắt đầu vòng lặp WHILE tổng, sau đó đặt ptr [temp] thành ch, đặt nhiệt độ thành temp + 2 và giảm tổng số đi 1.
-
Đặt vec [ch - 'a'] thành 0. Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn 26. Bên trong vòng lặp, bắt đầu trong khi vec [i] lớn hơn 0. Đặt temp thành (temp> =length)? 1:temp và ptr [temp] thành 'a' + i và temp thành temp + 2 và giảm vec [i] xuống 1.
-
Trả lại ptr
-
-
Bên trong hàm char tối đa (const vector
&vec) -
Khai báo một biến kiểu số nguyên là cao đến 0 và biến kiểu ký tự là ‘c’
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn 26. Trong vòng lặp, hãy kiểm tra NẾU vec [i] nhỏ hơn mức cao, sau đó đặt cao thành vec [i] và c thành 'a' + i.
-
Trả lại c
-
-
In kết quả.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Rearrangement of characters in a string such that no two adjacent are same is: initn