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

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 (26ⁿ - 1) / 25 nữa.
Ví dụ ở hệ 26 thì ACZ = 2526⁰ + 226¹ + 0*26¹ = 25 + 52 = 77. Nhưng trước ACZ có 26 chuỗi có 1 chữ số và 26² 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 + 26² nữa, đó chính là (26³ - 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

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

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.

Bài 1

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.
}