Hiểu bài toán

Bài toán yêu cầu đếm số lượng các số nguyên nằm trong một xâu ký tự S. Xâu S chỉ chứa các chữ số từ 1 đến 9 và dấu cách. Các số được ngăn cách nhau bởi một hoặc nhiều dấu cách. Nhiệm vụ là đếm xem có bao nhiêu số như vậy trong xâu.

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

Cách Duyệt từng ký tự và kiểm tra điều kiện

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    int cnt = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '1' && s[i] <= '9') {
            if (i == 0 || s[i-1] == ' ') {
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

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

Cách tiếp cận này duyệt qua từng ký tự của xâu S. Nếu ký tự hiện tại là một chữ số từ 1 đến 9, nó kiểm tra xem đây có phải là ký tự đầu tiên của một số hay không. Điều kiện để một ký tự là bắt đầu của một số là: nó là ký tự đầu tiên của xâu (i == 0) hoặc ký tự ngay trước nó là dấu cách (s[i-1] == ' '). Nếu điều kiện này đúng, ta tăng biến đếm lên 1. Cách này bỏ qua các số 0 vì đề bài chỉ định các số từ 1 đến 9.

Cách Sử dụng stringstream

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    int count = 0;
    string token;
    stringstream ss(s);
    while (ss >> token) {
        count++;
    }
    cout << count;
    return 0;
}

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

Cách tiếp cận này sử dụng stringstream để tự động phân tách xâu S thành các token (đoạn con) dựa trên dấu cách. Vòng lặp while(ss >> token) sẽ lần lượt lấy ra từng từ (số) bị ngăn cách bởi dấu cách. Mỗi lần lấy được một token, ta tăng biến đếm lên 1. stringstream mặc định bỏ qua các dấu cách thừa và chỉ trích xuất các cụm ký tự không phải dấu cách. Vì mỗi token đều là một số, số lượng token chính là số lượng số.

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

Bài học kinh nghiệm

• Vì chỉ có 9 chữ số từ 1 đến 9, ta không cần lo lắng về việc xử lý số 0 ở vị trí đầu tiên của một số.
• Các số luôn được ngăn cách bởi dấu cách, do đó việc xác định ranh giới giữa các số là chìa khóa.
• Dùng stringstream là cách đơn giản nhất trong C++ để tách các từ trong một câu.

Lỗi thường gặp

• Sử dụng cin >> s thay vì getline(cin, s). cin sẽ chỉ đọc được đến dấu cách đầu tiên, trong khi input có thể chứa nhiều số ngăn cách nhau.
• Quên kiểm tra điều kiện s[i-1] == ' ' có thể dẫn đến việc đếm sai nếu số nằm ngay sau các ký tự khác (tuy nhiên trong bài này chỉ có số và dấu cách nên rủi ro thấp, nhưng vẫn là lỗi logic thường gặp).
• Xử lý sai các trường hợp input rỗng hoặc chỉ chứa toàn dấu cách (các giải pháp trên đều xử lý đúng trường hợp này).