Hiểu bài toán

Bài toán yêu cầu tính tổng của tất cả các số nguyên xuất hiện trong một xâu ký tự. Các số có thể nằm rải rác trong xâu, được ngăn cách bởi các ký tự không phải số. Ví dụ: với xâu 'Abc12d4f', các số là 12 và 4, tổng là 16.

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

Cách Xử lý trực tiếp theo từng ký tự (Direct Iteration)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    getline(cin, s);

    long long total = 0;
    long long current_number = 0;

    for (char c : s) {
        if (c >= '0' && c <= '9') {
            // Nếu là chữ số, xây dựng số hiện tại
            current_number = current_number * 10 + (c - '0');
        } else {
            // Nếu không phải chữ số, cộng số đã xây dựng được vào tổng
            total += current_number;
            current_number = 0; // Reset về 0 để xử lý số tiếp theo
        }
    }

    // Xử lý số cuối cùng nếu xâu kết thúc bằng số
    total += current_number;

    cout << total;
    return 0;
}

• Time Complexity: O(n)
• 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ủa xâu. Nếu gặp ký tự số, ta cập nhật biến 'currentnumber' bằng cách nhân 10 và cộng giá trị ký tự số đó. Nếu gặp ký tự không phải số, ta cộng giá trị của 'currentnumber' hiện tại vào tổng rồi reset 'currentnumber' về 0. Cuối cùng, sau vòng lặp, ta cộng nốt giá trị 'currentnumber' vào tổng để xử lý trường hợp số nằm ở cuối xâu.

Cách Sử dụng chuỗi trung gian (String Accumulation)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    getline(cin, s);

    long long total = 0;
    string temp = "";

    for (char ch : s) {
        if (isdigit(ch)) {
            temp += ch;
        } else {
            if (!temp.empty()) {
                total += stoll(temp);
                temp = "";
            }
        }
    }

    // Xử lý số cuối cùng
    if (!temp.empty()) {
        total += stoll(temp);
    }

    cout << total;
    return 0;
}

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

Phương pháp này xây dựng các số dưới dạng chuỗi ký tự. Khi gặp chữ số, ta nối vào chuỗi tạm 'temp'. Khi gặp ký tự lạ, nếu 'temp' không rỗng, ta dùng hàm stoll (string to long long) để chuyển chuỗi thành số rồi cộng vào tổng. Ưu điểm là dễ hiểu, nhưng tốn bộ nhớ hơn do phải lưu chuỗi tạm.

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

Bài học kinh nghiệm

• Cần xử lý dãy số liên tục ngay cả khi chúng nằm ở đầu hoặc cuối xâu.
• Biến lưu số hiện tại cần được reset về 0 sau khi cộng vào tổng.

Lỗi thường gặp

• Quên cộng số cuối cùng vào tổng nếu xâu kết thúc bằng số.
• Không xử lý đúng số 0 nếu nó xuất hiện trong xâu (ví dụ: 'a0b' tổng phải là 0).
• Quá tải về bộ nhớ nếu sử dụng nhiều chuỗi phụ không cần thiết.