Hướng dẫn giải của [200 đề thầy Đức] Bài 141: Đếm chữ số
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.
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.
Hướng dẫn giải
Đếm số lần chữ số k xuất hiện trong tất cả các số của dãy.
Sub 1: Đổi sang chuỗi rồi đếm — ~O(n · số chữ số)~
Mỗi số đổi thành chuỗi bằng to_string, rồi đếm từng ký tự bằng với k. Cách này tự xử lý đúng số 0. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
long long dem = 0;
char kc = '0' + k;
// Vét cạn: đổi mỗi số thành chuỗi, đếm từng ký tự
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
string s = to_string(x);
for (char c : s)
if (c == kc) dem++;
}
cout << dem << "\n";
}
return 0;
}
Sub 2: Tách chữ số bằng phép chia 10 — ~O(n · số chữ số)~
Với mỗi số, lấy lần lượt chữ số cuối bằng x % 10 rồi x /= 10. Số 0 được xử lý riêng vì vòng lặp không chạy với x = 0. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
long long dem = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (x == 0) { // số 0 có một chữ số 0
if (k == 0) dem++;
continue;
}
// tách lần lượt từng chữ số bằng phép chia 10
while (x > 0) {
if (x % 10 == k) dem++;
x /= 10;
}
}
cout << dem << "\n";
}
return 0;
}
Bình luận