Tính Tổng Các Số Trong Xâu

Nguồn: Codeforces Group Độ khó: Dễ Xâu ký tự Duyệt 1 lần

Đề bài

Cho xâu $S$ chỉ bao gồm các ký tự chữ cái ('a' – 'z', 'A' – 'Z') và ký tự số ('0' – '9'). Hãy tính tổng các số trong xâu. Dữ liệu được cho đảm bảo kết quả tổng không vượt quá $10^{18}$.

Input: Xâu $S$ có độ dài tối đa $10^6$.

Output: 1 số nguyên duy nhất là kết quả tổng.

Subtask:

50% số test đầu tiên có độ dài xâu $S \le 10^3$.
50% số test còn lại không có giới hạn gì thêm.

Ví dụ – input

Abc12d4f

Ví dụ – output

Giải thích: Có 2 số 12 và 4, tổng 2 số đó là 16.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

Thì bài này chỉ cần duyệt 1 lần qua chuỗi từ đầu đến cuối là ta có thể lấy ra được hết toàn bộ các số có trong chuỗi và tính tổng, để sau cùng khi duyệt xong ta sẽ có kết quả tổng. Tức là chỉ cần 1 vòng lặp duy nhất thôi nhé.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Ý tưởngQuy luật Cách làmChuỗi str Lưu ýi <= length CodeO(N)

Ý tưởngNhìn ra quy luật của một số trong xâu

Để làm được như vậy thì ta phải nhìn ra được quy luật của nó như sau: để ý thấy các ký tự số sẽ nằm liên tiếp nhau, và:

Dấu hiệu để biết bắt đầu của 1 số là khi đang là ký tự không phải ký tự số rồi tiếp theo là ký tự số.
Kết thúc của một số đó là khi đang là ký tự số và tiếp theo không phải là ký tự số nữa.
Còn tiếp tục của 1 số là khi ký tự hiện tại là ký tự số và ký tự liền trước đó cũng là ký tự số, nghĩa là nó vẫn đang tiếp tục.

Ký tự liền trước	Ký tự hiện tại	Ý nghĩa
không phải số	là số	Bắt đầu một số mới
là số	là số	Số đó vẫn đang tiếp tục
là số	không phải số	Số đó vừa kết thúc ở ký tự liền trước
không phải số	không phải số	Chẳng có số nào, bỏ qua

Rất dễ để nhìn ra được những quy luật này. Tuy nhiên giờ nhìn ra được rồi thì phải chọn cách giải quyết sao cho đơn giản nhất?

Cách làmDùng thêm 1 chuỗi str để gom chữ số

Thì mọi chuyện sẽ rất đơn giản nếu ta có thêm 1 biến chuỗi str dùng để lưu các ký tự số vào đó:

Đầu tiên biến chuỗi str khởi tạo rỗng, biến tổng sum = 0.
Duyệt chuỗi $s$ đầu vào, nếu gặp ký tự s[i] là ký tự số thì ta thêm ký tự s[i] đó vào cuối chuỗi str.
Nếu gặp ký tự s[i] không phải ký tự số thì ta kiểm tra xem hiện tại chuỗi str có đang rỗng hay không?
- Nếu đang rỗng thì bỏ qua không làm gì hết, cứ duyệt ký tự s[i] tiếp theo.
- Còn nếu chuỗi str đang khác rỗng, tức là đang tồn tại các ký tự số bên trong, thì lúc này ta hiểu rằng đây là dấu hiệu kết thúc: ta sẽ đi đổi chuỗi str sang số rồi cộng vào biến tổng, sau đó reset lại chuỗi str thành rỗng và tiếp tục duyệt qua ký tự s[i] tiếp theo, và cứ thế.

Em nhập xâu rồi bấm Tiếp để xem chuỗi str gom chữ số và biến sum thay đổi qua từng ký tự:

Xâu s

Ví dụ nhanh:

Lưu ýSố nằm ở cuối xâu và mẹo i <= s.length()

Cần lưu ý tình huống nếu giả sử ký tự s[i] cuối cùng của chuỗi $s$ là ký tự số (ví dụ ab123), thì như thế khi đưa nó vào chuỗi str rồi thì lúc này chuỗi $s$ đã duyệt xong, không còn ký tự nào để xét nữa. Vòng lặp kết thúc, ta nhớ phải kiểm tra tình trạng chuỗi str lúc này: nếu đang khác rỗng thì phải đi xử lý đổi sang số rồi cộng vào biến tổng nhé. Bản Python bên dưới làm đúng như vậy.

Hoặc để đơn giản hơn khỏi phải code dài dòng thêm thì ở bước duyệt chuỗi $s$, thay vì vòng lặp i < s.length() thì ta để luôn i <= s.length(), tức là cho thêm trường hợp i == s.length() nữa. Lúc này ký tự tại vị trí s.length() sẽ là ký tự '\0' kết thúc chuỗi, nó không phải là ký tự số, vì thế code sẽ làm công việc kiểm tra xem chuỗi str có đang rỗng hay không, và phát hiện nếu str đang không rỗng thì sẽ đi xử lý đổi str sang số rồi cộng vào tổng.

Vì sao được truy cập s[s.length()]?

Ta khỏi phải mất công xét riêng chuỗi str sau vòng lặp làm gì, chỉ cần thêm điều kiện cho vòng lặp for i duyệt thêm trường hợp i == s.length() thôi là tự nó sẽ xử lý thêm trường hợp xét chuỗi str. Và cũng không sợ sai, bởi vì với std::string (từ C++11) ta vẫn được quyền truy cập vào ký tự kết thúc chuỗi '\0' ở vị trí index s.length() mà 😁

CodeDuyệt 1 lần – O(N)

Source code để các bạn tham khảo thấy rõ những gì mình phân tích ở trên:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    getline(cin, s);
    string str = "";
    long long sum = 0;
    for(int i = 0; i <= (int)s.length(); ++i){
        if(s[i] >= '0' && s[i] <= '9'){
            str.push_back(s[i]);
        }
        else{
            if(str != ""){
                sum += stoll(str);
                str = "";
            }
        }
    }
    cout << sum;
    return 0;
}

s = input().strip()

str_num = ""
total = 0

for ch in s:
    if '0' <= ch <= '9':
        str_num += ch
    else:
        if str_num != "":
            total += int(str_num)
            str_num = ""

if str_num != "":
    total += int(str_num)

print(total)

C++▶ Chạy tay từng dòng codeGom chữ số vào str, gặp ký tự không phải số (kể cả \0 ở cuối) thì cộng vào sum – O(N).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 string s;

8 getline(cin, s);

9 string str = "";

10 long long sum = 0;

11 for(int i = 0; i <= (int)s.length(); ++i){

12 if(s[i] >= '0' && s[i] <= '9'){

13 str.push_back(s[i]);

14 }

15 else{

16 if(str != ""){

17 sum += stoll(str);

18 str = "";

19 }

20 }

21 }

22 cout << sum;

23 return 0;

24}

Đánh giá độ phức tạp của cách làm này:

Không gian$O(1)$

Thời gian$O(N)$ với $N$ là độ dài chuỗi $s$

Với $N = 10^6$ thì vòng lặp cũng chỉ chạy khoảng $10^6$ lần, mỗi ký tự số được thêm vào str đúng 1 lần và được đổi sang số đúng 1 lần, nên tổng công việc vẫn là $O(N)$, yên tâm không bị TLE nhé. Lưu ý biến tổng phải dùng long long vì kết quả có thể lên tới $10^{18}$.

Ghi chú của mình: code C++ và Python ở trên là của mình. Cả 2 bản đã được kiểm tra với 300 bộ test ngẫu nhiên (có số ở đầu xâu, cuối xâu, số có chữ số 0 ở đầu, xâu toàn chữ, xâu toàn số) so với cách vét cạn tách số bằng biểu thức chính quy: khớp hết. Với xâu dài $10^6$ ký tự, bản C++ chạy khoảng 0.06 giây, bản Python khoảng 0.3 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán