Một vài vấn đề về tối ưu code c++

#1

Mọi người giúp mình đưa ra hướng giải quyết với nha:

  1. Mình có 1 mảng gồm nhiều phần tử ví dụ các chữ cái a,b,c,…z. Trong mảng sẽ có 1 ký tự duy nhất không lập lại 2 lần, các ký tự còn lại sẽ lập lại 2 lần. Yêu cầu là phải tìm ra ký tự duy nhất không lập lại đó và phải tối ưu code đó.
  2. Mình muốn viết 1 code tạo ra các chuỗi ký tự dựa theo bảng chữ cái. Ví dụ: A,B,C…Z khi tới Z sẽ tăng lên chuỗi có độ dài là 2 AA,AB,AC…BA,BB,BC…ZZ sau đó lại tăng độ dài lên 3
  3. Trong excel các cột được đánh dấu giống như trong câu 2. Mình phải làm sao để khi nhập vào AA thì sẽ biết được đó là cột thứ mấy trong excel.
  4. Tìm chuỗi con trong 1 chuỗi cha, tính số lần xuất hiện. Tối ưu nó luôn

Câu 1 mình làm nhưng chưa biết cách tối ưu nó
Câu 2 mình đã làm được nhưng phải dùng nhiều for và phải giới hạn độ dài tối đa của chuỗi được tạo ra
Câu 3 mình đang bí @@
Câu 4 câu này mình có ý tưởng là cắt chuỗi cha thành nhiều phần dựa theo độ dài của chuỗi con, sau đó so sánh đếm số lần xuất hiện. Nhưng thấy nó ko phải là giải pháp hay.

Mình đang nghiên cứu C++ nên có nhiều câu hỏi ngu ngơ mong mọi người giúp đỡ. Không cần phải code ra chỉ cần cho mình hướng xử lý, giải quyết thuật toán là được. Cám ơn

1 Like
#2

câu 1 thì có 1 cách cực kì gian lận là xài XOR

result = 0
for c in s: result ^= c
return result

cho bit a và bit b, phép tính a XOR b trả về 0 nếu a==b, trả về 1 nếu a!=b. XOR có đặc điểm là nếu XOR cùng 1 số n 2 lần thì sẽ trở lại số ban đầu: (a XOR n) XOR n = a. Số 0 XOR với số n bất kì sẽ cho kết quả là n. Nó cũng có tính chất giao hoán a XOR b = b XOR a. Lợi dụng đặc điểm này thì lấy result = 0, vì trong mảng tất cả các ký tự đều lặp lại 2 lần nên result = result XOR c sẽ trả về kết quả ban đầu là 0. Thứ tự ko quan trọng vì nó có tính giao hoán. Duy nhất chỉ có 1 ký tự duy nhất ko xuất hiện 2 lần thì XOR với 0 sẽ cho ra chính nó, chính là ký tự cần tìm.

câu 3 thì coi như chuỗi đó là số có hệ nhị thập lục phân (thay vì hệ thập phân mình đang sử dụng). A=0, B=1, …, Z=25. Có thêm 1 cái trick nữa là chuỗi có n chữ số thì sẽ phải cộng thêm (26n - 1) / 25 nữa.
Ví dụ ở hệ 26 thì ACZ = 25260 + 2261 + 0*261 = 25 + 52 = 77. Nhưng trước ACZ có 26 chuỗi có 1 chữ số và 262 chuỗi có 2 chữ số, và bắt đầu từ 1 chữ ko phải từ 0, nên phải cộng thêm 1 + 26 + 262 nữa, đó chính là (263 - 1) / 25 = 703 => ACZ là chuỗi thứ 77 + 703 = 780.

câu 2 tìm ngược lại từ câu 3: viết 1 hàm chuyển số n (n bắt đầu từ 1) thành chuỗi s dựa theo bảng chữ cái đó. Tạo ra nhiều khoảng: ví dụ n nằm trong [1,26] thì s có độ dài là 1. n nằm trong [27,703] thì s có độ dài 2, v.v… Có độ dài rồi thì viết hàm chuyển thành chữ dễ dàng:
Ví dụ cho số n=98 tức là chuỗi thứ 98, nằm trong khoảng [27,703] nên sẽ có 2 chữ số, nhưng giá trị cần chuyển là 98 - 27 = 71 chứ ko phải 98. Chuyển 71 hệ thập phân thành hệ 26: 71/26 = 2 dư 19. 2=>C, 19=>T Vậy chuỗi đó là CT.
ví dụ khác: n = 27 thì n trong khoảng [27,703], chuyển số 27-27 thành hệ 26: 0/26 = 0 dư 0 => AA.

để cho dễ tìm n trong khoảng nào thì tạo 1 mảng:
range = {1, 27, 703, 18279, 475255, 12356631, 321272407}
rồi tìm số range[i] sao cho n > range[i] và n < range[i+1] là được. Chuỗi đó sẽ có i+1 ký tự (range index bắt đầu từ 0). Nếu n lớn hơn số lớn nhất trong range thì có thể báo lỗi. (chắc 321 triệu số là quá đủ rồi)

câu 4 thì https://vi.wikipedia.org/wiki/Thuật_toán_Knuth–Morris–Pratt

6 Likes
#3

Thank bạn nhiều! Giải thích rõ ràng chi tiết quá.

1 Like
#4

câu 2 có thể dùng map trong STL với key số sinh ra theo cách của bạn trên ( cách rất hay) và value là chuỗi bạn sinh ra. Độ phức tạp tăng tỉ lệ với độ dài bạn muốn. Tất nhiên là chạy chậm, nhưng đề bài của bạn là phải sinh chuỗi ra, chẳng còn cách nào khác brute-force.

Câu 3 thì cứ dùng hàm find của map tìm key là ra value.

#5

Bài 1 :smile:

unsigned char [] s = "....";
unsigned char Count[256];
unsigned char r=0;
for(int i=0;i<s.Lenght;i++)
    Count[(int)s[i])++;
for(int i=0;i<256;i++){
    if(Count[i]==1) { r = Count[i]; break;} // tìm được ký tự r xuất hiện 1 lần.
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?