Hướng dẫn giải của Tần suất xuất hiện các ký tự

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, lehongxn4gmail, haibui, bnguyet

Hiểu bài toán

Viết chương trình đếm tần suất xuất hiện của tất cả các ký tự (không phân biệt hoa thường) có trong chuỗi s được nhập từ bàn phím. In kết quả theo thứ tự từ điển:先 in các chữ số (0-9), sau đó là các chữ cái (a-z). Chỉ đếm và in các ký tự thuộc bảng chữ cái tiếng Anh (a-z, A-Z) và chữ số (0-9) có tần suất > 0. Ký tự in ra phải là dạng viết thường.

Các cách tiếp cận

Cách Brute Force (Lặp kép)

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Xóa ký tự newline

    // Đếm và in các chữ số 0-9
    for (char c = '0'; c <= '9'; c++) {
        int count = 0;
        for (int i = 0; s[i]; i++) {
            if (s[i] == c) count++;
        }
        if (count > 0) printf("%c %d\n", c, count);
    }

    // Đếm và in các chữ cái a-z (không phân biệt hoa/thường)
    for (char c = 'a'; c <= 'z'; c++) {
        int count = 0;
        for (int i = 0; s[i]; i++) {
            if (tolower(s[i]) == c) count++;
        }
        if (count > 0) printf("%c %d\n", c, count);
    }
    return 0;
}

Time Complexity: O(N * M) ~ O(10000 * 36) ~ 3.6*10^5
Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Ta duyệt qua từng ký tự cần đếm (từ '0' đến '9', rồi từ 'a' đến 'z'). Với mỗi ký tự đó, ta duyệt lại toàn bộ chuỗi đầu vào để đếm số lần xuất hiện. Nếu số đếm lớn hơn 0, ta in ra. Phương pháp này không cần bộ nhớ phụ, nhưng chạy chậm do duyệt lại chuỗi nhiều lần.

Cách Hash Map (Mảng đánh dấu)

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    char s[10001];
    int freq[256] = {0}; // Mảng lưu tần suất cho mỗi ký tự ASCII

    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;

    // Bước 1: Duyệt chuỗi 1 lần để đếm tần suất
    for (int i = 0; s[i]; i++) {
        char c = tolower(s[i]); // Chuẩn hóa về thường
        // Chỉ đếm nếu là chữ số hoặc chữ cái
        if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
            freq[(int)c]++;
        }
    }

    // Bước 2: In kết quả theo thứ tự ưu tiên (0-9 rồi a-z)
    // In số
    for (char c = '0'; c <= '9'; c++) {
        if (freq[(int)c] > 0) printf("%c %d\n", c, freq[(int)c]);
    }
    // In chữ
    for (char c = 'a'; c <= 'z'; c++) {
        if (freq[(int)c] > 0) printf("%c %d\n", c, freq[(int)c]);
    }

    return 0;
}

Time Complexity: O(N)
Space Complexity: O(1) (Mảng 256 phần tử)

Sử dụng một mảng kích thước 256 (bảng mã ASCII) để lưu trữ tần suất. Chỉ cần duyệt chuỗi đầu vào một lần để cập nhật số đếm. Sau đó, ta chỉ cần duyệt qua các ký tự mong muốn ('0'-'9' và 'a'-'z') để in kết quả. Đây là phương pháp tối ưu về thời gian thực thi.

Cách Tối ưu hóa với chỉ số mảng

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    char s[10001];
    int freq[36] = {0}; // 10 số + 26 chữ cái

    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;

    for (int i = 0; s[i]; i++) {
        char c = tolower(s[i]);
        int idx = -1;

        if (c >= '0' && c <= '9') {
            idx = c - '0'; // 0 -> 9
        } else if (c >= 'a' && c <= 'z') {
            idx = c - 'a' + 10; // a -> 35 (a là index 10)
        }

        if (idx != -1) {
            freq[idx]++;
        }
    }

    // In số (0->9)
    for (int i = 0; i < 10; i++) {
        if (freq[i] > 0) printf("%c %d\n", (char)(i + '0'), freq[i]);
    }
    // In chữ (a->z)
    for (int i = 10; i < 36; i++) {
        if (freq[i] > 0) printf("%c %d\n", (char)(i - 10 + 'a'), freq[i]);
    }

    return 0;
}

Time Complexity: O(N)
Space Complexity: O(1)

Cách này tương tự Approach 2 nhưng sử dụng mảng nhỏ hơn (36 phần tử thay vì 256). Nó ánh xạ ký tự '0'-'9' vào chỉ số 0-9 và 'a'-'z' vào chỉ số 10-35. Điều này giúp tiết kiệm bộ nhớ RAM một chút và che giấu bảng tần suất tốt hơn, dù hiệu năng không khác biệt nhiều với Approach 2 trong bài toán này.

Phân tích độ phức tạp

Cách tiếp cận	Time	Space	Tên
1	O(N * M) ~ O(10000 * 36) ~ 3.6*10^5	O(1)	Brute Force (Lặp kép)
2	O(N)	O(1) (Mảng 256 phần tử)	Hash Map (Mảng đánh dấu)
3	O(N)	O(1)	Tối ưu hóa với chỉ số mảng

Bài học kinh nghiệm

Sử dụng hàm tolower() (hoặc toupper()) là chìa khóa để giải quyết việc 'không phân biệt hoa thường'.
Thứ tự xuất hiện yêu cầu là 0-9 rồi a-z, nên ta có thể chia vòng lặp in kết quả thành 2 phần riêng biệt.
Phương pháp đếm tần suất sử dụng mảng (Hash Map cơ bản) có độ phức tạp thời gian O(N) tốt nhất, chỉ duyệt chuỗi 1 lần.

Lỗi thường gặp

Quên xử lý ký tự newline (\n) được fgets đọc vào, dẫn đến việc đếm sai hoặc in thừa dòng trống.
Duyệt chuỗi trong vòng lặp kép (Approach 1) sẽ gây chạy chậm nếu độ dài chuỗi lớn (TLE), tuy nhiên với giới hạn 10000 ký tự thì vẫn có thể chấp nhận được nhưng không tối ưu.
Chỉ đếm các ký tự chữ số và chữ cái, cần bỏ qua các ký tự đặc biệt và khoảng trắng.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.