Thảo luận một vấn đề để sắp xếp lại một chuỗi bảng chữ cái theo thứ tự đã sắp xếp và thêm tất cả các số nguyên có trong chuỗi, chẳng hạn
Input : str = “adv4fc3” Output : “ acdfv7” Explanation: all the letters have been sorted to “acdfv” followed by the sum of integers 4 and 3. Input: str = “ h2d7e3f ” Output: “ defh12” Explanation: all the letters have been sorted to “defh” followed by the sum of integers 2, 7, and 3.
Phương pháp tiếp cận để tìm giải pháp
Chúng tôi có hai nhiệm vụ cần thực hiện trong vấn đề này, một là sắp xếp chuỗi và nhiệm vụ kia là thêm các giá trị số nguyên.
-
Việc sắp xếp chuỗi có thể được thực hiện bằng cách giữ nguyên số lượng của mọi chữ cái trong chuỗi và sau đó tạo thành một chuỗi mới bằng cách chèn tất cả các chữ cái theo số lượng của chúng.
-
Chúng ta có thể thực hiện phép cộng các số nguyên bằng cách thêm số nguyên vào một biến mỗi khi nó xuất hiện.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
int main(){
string str = "h2d7e3f";
int ch[26] = {0};
int count = 0;
// traverse through all the characters of string.
for (int i = 0; i < str.length(); i++){
// keeping count of occurance every character.
if (str[i]>='a' && str[i] <='z')
ch[str[i] - 97] = ch[str[i] - 97] + 1;
// If an Integer encounters.
else
count = count + (str[i]-'0');
}
string final = "";
// Making a sorted string with the help of ch array.
for (int i = 0; i < 26; i++){
char a = (char)('a'+i);
// insert the current character
// to new string untill it count ends
while (ch[i]-- != 0)
final = final + a;
}
// and finally insert sum of all integers in the string.
if (count>0)
final = final + to_string(count);
cout << "Rearranged string: " << final;
return 0;
} Đầu ra
Rearranged string: defh12
Giải thích về Quy tắc trên
-
Mảng ch được khởi tạo với kích thước 26 vì chúng ta cần giữ số lần xuất hiện của 26 bảng chữ cái.
-
Trong vòng lặp Đầu tiên, chúng ta đang duyệt qua chuỗi. Đối với mỗi bảng chữ cái, chúng tôi đang tăng số lượng của bảng chữ cái đó. Đối với mọi số nguyên, chúng tôi sẽ thêm nó vào biến đếm.
-
Trong vòng lặp thứ hai, chúng tôi đang tạo một chuỗi được sắp xếp mới từ tất cả các số đếm mà chúng tôi đang thêm ký tự trong chuỗi theo số lượng của chúng.
-
Và cuối cùng chúng tôi cũng đang nối chuỗi với tổng các số nguyên mà chúng tôi đã đếm được từ vòng lặp đầu tiên.
Kết luận
Trong hướng dẫn này, chúng tôi đã thảo luận về cách sắp xếp một chuỗi theo thứ tự đã sắp xếp và giải quyết vấn đề dựa trên nó từ phương pháp tiếp cận bảng băm. Chúng tôi cũng đã thảo luận về mã C ++ cho vấn đề này. Chúng tôi có thể viết bằng bất kỳ ngôn ngữ lập trình nào khác như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.