Câu hỏi về tần suất xuất hiện kí tự trong string

thi_Tran1 · December 20, 2021, 3:50pm

Em chào mọi người .
Em đang làm bài tập về tuần suất xuất hiện của kí tư trong 1 xâu kĩ tự. Nhưng lại code không đươc . Em mong được các anh chị hướng dẫn em ý tưởng để làm ạ .
Em đang học code bằng C++.
Cảm ơn mọi người nhiều.

kisuluoibieng · December 20, 2021, 5:32pm

bạn thử search c++ map xem có gì hay ho không

Red_Sand · December 21, 2021, 4:39am

Hiện tại hướng làm của bạn là gì. Không cần cao siêu, cũng không cần hoàn chỉnh, chỉ một vài suy nghĩ đơn giản nhất cũng được.
Bạn nghĩ sao về đề bài này?

thi_Tran1 · December 21, 2021, 11:28am

Em có tìm hiểu qua rồi . Vì em là newbie nên nhìn thấy hơi phức tạp .

thi_Tran1 · December 21, 2021, 11:38am

Hướng đi của em:
B1: là tạo 1 hàm đếm số lần xuất hiện của char x.
B2: gọi biến found=0 và char flag . Tạo ra 1 vòng lặp i=0 ; i<string.length() ; i++
B3: gọi hàm đếm với x=string[i]. Nếu > found thì gán found với giá trị đếm vừa tìm được và gán flag=string[i] .Làm vậy cho đến hết vòng lặp
B4: tìm được giá trị xuất hiện nhiều nhất.
Em có làm ra được rồi ạ. Nhưng em thấy cách này không tối ưu. Em mong mọi người hướng dẫn cách làm khác .

Minh_Vu · December 21, 2021, 12:37pm

Mặc dù không biết có tối ưu hơn không nhưng tôi lại nghĩ đến việc số hóa cái xâu đó bro ạ nãy tôi vừa viết thì nó như sau :>

#include <iostream>

using namespace std;

int toNum(char s){

    return s-'a';

}

int main () {

    int n, dem, a[100];

    string s;

    getline(cin, s);

    n=s.length();

    for (int i=0; i<n; i++){

        a[i]=toNum(s[i]);

    }

    for (int i=0; i<n; i++)

    {

        if (s[i]!=' ')

            if (a[i]!=-1)

            {

                dem = 1;

                for (int j=i+1; j<n; j++)

                {

                    if (a[j]==a[i]) {dem++; a[j] = -1;}

                }

                cout << s[i] << " " << dem << endl;

            }

    }

    return 0;

}

Red_Sand · December 21, 2021, 6:28pm

Đúng rồi, very good . Nhưng với chuỗi như ‘aabcadaaa’ thì hàm đếm ‘a’ được gọi tới 6 lần, mỗi lần lại loop qua cả chuỗi, có cách nào tránh được việc đếm char đã đếm rồi không nhỉ

Task 2: Nếu tránh được rồi thì với mỗi char phân biệt, vẫn phải loop qua cả chuỗi, có cách nào loop 1 lần là đếm hết được không nhỉ

Gợi ý:
Cách 1: cấu trúc dữ liệu hash map cho phép lưu data dưới dạng (key, value). Mỗi key tương ứng với một value. Thời gian truy xuất giữ liệu O(1).

Cách 2: Bảng chữ cái chỉ có 26 ký tự. Vậy có làm cách nào để lưu và update số lần xuất hiện của mỗi ký tự khi loop qua chuỗi 1 lần không nhỉ.

thi_Tran1 · December 24, 2021, 2:12pm

Dạ em cảm ơn anh và mọi người nhiều ạ.

newbie_lap_trinh · December 27, 2021, 2:40am

Bạn có thể đếm tần suất của chữ xuất hiện nhiều lần nhất theo cách này:

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

int main()
{
	string s;
	char c;

cin >> s;

unordered_map<char, int> map;

int ans = 0;

for (int j = 0; j < s.size(); j++)
{
	map[s[j]]++;

	if (map[s[j]] > ans) { ans = map[s[j]]; c = s[j]; }
}

cout << "Ky tu xuat hien nhieu nhat: " << c << endl;
cout << "So lan xuat hien: " << map[c] << endl;
return 0;

}

thi_Tran1 · December 27, 2021, 2:17pm

Em cảm ơn anh.
Em chưa học qua thư viện map nên lúc đầu nhìn hơi khó hiểu.
H em hiểu roiofiiii.