Khương Nguyễn
Trong quá trình giải một số bài code thì tôi nhận thấy một phương pháp(tất nhiên là nó đã tồn tại rồi)
có vẻ khá tiện, tuy nhiên thì nó cũng có những điểm trừ nhất định.
Để khởi động chúng ta sẽ cùng đến với một bài tập kinh điển như sau:
Bài tập 1. Cho một mảng gồm \(n\) số nguyên. Tìm số phần tử bằng 0 liên tiếp nhiều nhất.
P/s: Ví dụ 1 test case:
8
1 0 0 0 2 0 0 1
Output: 3
Các bạn hãy thử post lời giải bên dưới nhé,...
Trả lờiGiả sử mảng được xét là arr, các phần tử từ a[0] tới a[n-1].
Đặt 2 biến ans = 0, count = 0
for (int i = 0; i < n; ++i) {
if (a[i] == 0) {
count++;
ans = max(count, ans);
} else {
count = 0;
}
} Khi đó sẽ ra được ans là đáp án
Mô tả giải thuật như sau: có 1 biến đếm ảo và 1 biến đếm lưu khi bị sai điều kiện thì refresh lại biến đếm ảo.
int n;
cin>>n;
int max=0;
int a[100000];
int x=0;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
if(a[i]==0){
x++;
if(x>max){
max=x;
};
}else{
x=0; //refresh lại biến x
}
}
cout<<max;
Mở rộng bài code trên, ta được 1 giải thuật khá tốt cho 2 bài kinh điển khác.
Bài tập 2. Cho mảng gồm n phần tử. In ra và đếm các phần tử chỉ xuất hiện 1 lần.
Bài tập 3. Cho 1 xâu. Xâu đó được gọi là xâu chẵn nếu các phần tử của xâu đều xuất hiện chẵn lần. Ví dụ: "vvllxx"
Xâu đó được gọi là xâu lẻ nếu các phần tử đều xuất hiện lẻ lần. Ví dụ: "xxxkkklllwww".
Viết chương trình để kiểm tra xem xâu đó là chẵn hay lẻ?
Câu 2 thì hiện mình có 2 giải thuật:
1, ( O(n) )
Tạo 1 map<int,int> m;
for (int i = 0; i < n; ++i) {
m[a[i]] = 0;
}
for (int i = 0; i < n; ++i) {
m[a[i]]++;
}
Cuối cùng kiểm tra từ a[0] đến a[n-1], khi nào m[a[i]] = 1 thì cộng vào biến đếm 1.
2, ( O(nlogn) )
Sort mảng a, sau đó
int count = 1;
int ans = 0;
for (int i = 1; i < n; ++i) {
if ( a[i] != a[i-1] ) {
if (count == 1){
ans++;
}
count = 0;
}
count++;
}
Mở rộng cách làm từ việc đánh dấu chỉ 1 biến ở bài số 1, chúng ta sẽ đánh dấu bằng cả 1 mảng.
Có thể lấy ví dụ như phía trên từ phía bạn cokhibachkhoa.
Ở bài 4 thì việc đánh dấu mảng là tối ưu khi độ phức tạp chỉ là O(130)...
(Với các bài toán chuỗi thì việc đánh dấu 1 mảng là cực kì tiện vì giá trị của các chữ trong bảng ASCII <=130).
#include<iostream>
using namespace std;
int main(){
int count_chan=0;
int count_le=0;
string x;
cin>>x;
int b[130]={0};
for(int i=0; i<x.length(); i++){
b[x[i]]++;
}
for(int i=0; i<130; i++){
if(b[i]%2==0 && b[i]!=0){
count_chan++;
}
if (b[i]%2==1){
count_le++;
}
}
if(count_chan==0){
cout<<"Xau nay la xau le";
}
if(count_le==0){
cout<<"Xau nay la xau chan";
}
if(!(count_chan==0||count_le==0)){
cout<<"Xau nay la xau khong chan khong le";
}
}