Kỹ thuật mảng đánh dấu trong lập trình là gì năm 2024
B1: khoi ta.o: s := 0. B2: Tìm sô' 9 đâ`u tiên,nêu' có, g/s vi tri' là i => tăng s lên 1, d[i] := s; Tiê'p tuc tìm các sô' 9 còn lai, nê'u có => d[j] = s; Thuc hiê.n vòng la.p vo'i sô' 8, 7, ..., 0; \=> kê't qua. kha? năng diên đa.t cua min`h hoi kém, hi vo.ng ba.n hiê?u. -
char n=[9 8 1 2 4 5 6 7] và 1 mảng k cùng chiều dài với mảng trên ,mảng này đánh dấu là 0 hết làm 1 vòng lâp while ta cộng các pt mảng n với 1 phần tử nào tới 10 thì không + nữa và ta sẽ đánh dấu pt của màng k tương ứng với giá trị hạng (RANK) mỗi lần đánh dấu xong thì RANK sẽ tang lên 1 ,vòng lặp kết thúc khi nào mảng k không còn phần tữ nào chứa số 0 Code: include "conio.h" >include "stdio.h" >int Continue(char *p,int n) > { > int s=false; > for(int i=0;i{ >
if(n[i]==10) >
{ >
Mark++; >
break; >
} >
} >
Marking(op,n,k,Mark); >
} >
for(int i=0;i Đếm tần suất ký tự trong xâu và các bài toán liên quan tới sự xuất hiện của ký tự trong xâu các bạn có thể sử dụng mảng đánh dấu hoặc map. Trong bài viết này mình sẽ hướng dẫn các bạn dạng bài tập này và một vài bài tập ví dụ minh họa NỘI DUNG :
image 1. Đếm tần suất ký tự bằng mảng đánh dấu Để đếm xem mỗi ký tự trong xâu xuất hiện bao nhiêu lần bạn có thể sử dụng kỹ thuật mảng đánh dấu, nếu bạn chưa biết kỹ thuật này có thể tham khảo tại đây Ý tưởng là mình sẽ sử dụng mã ASCII của các ký tự để đếm tần suất tương ứng của ký tự đó, các ký tự trong bảng mã ASCII có thứ tự từ 0 tới 255 nên bạn chỉ cần sử dụng một mảng đánh dấu có 256 phần tử là có thể đếm được tần suất. Ví dụ khi gặp kí tự 'a' trong xâu ký tự thì bạn sẽ đếm tần suất của nó thông qua phần tử có chỉ số 97 của mảng đánh dấu, vì 'a' có mã ASCII là 97 Sau khi bạn tìm được tần suất của từng ký tự bạn có thể triển khai nhiều bài toán mở rộng khác. Độ phức tạp : O(N) Mã nguồn : include "iostream"include "string"using namespace std; int main(){ string s = "28tech 28tech aaa"; int cnt[256] = {0}; for(int i = 0; i < s.size(); i++){ Output : xuat hien 2lan 2 xuat hien 2lan 8 xuat hien 2lan a xuat hien 3lan c xuat hien 2lan e xuat hien 2lan h xuat hien 2lan t xuat hien 2lan 2. Đếm tần suất ký tự bằng map Ngoài cách sử dụng mảng đánh dấu bạn có thể sử dụng map, nếu bạn chưa biết cách dùng map thì có thể tham khảo tại blog của mình bài viết về map nhé. Ý tưởng là mình sẽ dùng một map Cách này thì ngắn gọn tuy nhiên độ phức tạp tệ hơn so với mảng đánh dấu Độ phức tạp : O(NlogN) Mã nguồn : include "iostream"include "string"include "map"using namespace std;
int main(){
string s = "28tech 28tech aaa";
map Output : xuat hien 2 lan 2 xuat hien 2 lan 8 xuat hien 2 lan a xuat hien 3 lan c xuat hien 2 lan e xuat hien 2 lan h xuat hien 2 lan t xuat hien 2 lan 3. Bài tập áp dụng Bài tập 1 : Đếm số lượng ký tự khác nhau trong xâu Bài này mình sẽ sử dụng mảng đánh dấu để đánh dấu sự xuất hiện của ký tự trong xâu sau đó đếm số lần xuất hiện của các ký tự khác nhau. include "iostream"include "string"include "map"using namespace std; int main(){ string s = "28tech 28tech aaa"; int cnt[256] = {0}; for(int i = 0; i < s.size(); i++){ Output : So luong ki tu khac nhau : 8 Bài tập 2 : Liệt kê các ký tự trong xâu và tần suất của nó theo thứ tự xuất hiện trong xâu Trong mục 1 mình đã hướng dẫn các bạn cách duyệt theo thứ tự từ điển abc, nếu yêu cầu duyệt theo thứ tự xuất hiện trong xâu thì bạn duyệt xâu và in ra tần suất tương ứng. |
