Hướng dẫn giải của [200 đề thầy Đức] Bài 133: Kí tự duy nhất đầu tiên
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
Tìm vị trí đầu tiên của ký tự xuất hiện đúng một lần trong chuỗi, hoặc in -1 nếu không có.
Sub 1: Vét cạn đếm từng vị trí — ~O(n^2)~
Với mỗi vị trí i, đếm số lần s[i] xuất hiện trong cả chuỗi. Vị trí đầu tiên có số lần bằng 1 là đáp án. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
string s;
cin >> s;
int n = s.size();
int ketQua = -1;
// Vét cạn: với mỗi vị trí i, đếm số lần ký tự s[i] xuất hiện trong cả chuỗi
for (int i = 0; i < n; i++) {
int dem = 0;
for (int j = 0; j < n; j++)
if (s[j] == s[i]) dem++;
if (dem == 1) {
ketQua = i + 1; // vị trí tính từ 1
break;
}
}
cout << ketQua << "\n";
}
return 0;
}
Sub 2: Mảng đếm 26 chữ cái — ~O(n)~
Đếm số lần xuất hiện của 26 chữ cái trong một lượt, sau đó duyệt lại chuỗi và lấy vị trí đầu tiên có số lần bằng 1. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
string s;
cin >> s;
int n = s.size();
// Đếm số lần xuất hiện của 26 chữ cái
int dem[26] = {0};
for (char c : s) dem[c - 'a']++;
int ketQua = -1;
for (int i = 0; i < n; i++) {
if (dem[s[i] - 'a'] == 1) { // ký tự đầu tiên xuất hiện đúng 1 lần
ketQua = i + 1;
break;
}
}
cout << ketQua << "\n";
}
return 0;
}
Bình luận