Lmao

Lmao

http://liveexample.pearsoncmg.com/liang/animation/web/AVLTree.html
Chuỗi con chung dài nhất : 
+ Nếu bằng thì đường chéo trên + 1
+ Nếu khác thì max 2 bên

// Chuỗi con đối xứng :
// + Nếu bằng thì lấy đường chéo trên
// + Nếu khác => lấy max 2 bên

// Done
Tìm Kiếm : 
+ mảng một chiều : O(n)
+ có thứ tự : O(lg2n)
+ nội suy có tt : O(lglgn)
+ ds lk đơn : O(n)
+ nhị phân : O(n)
+ nhị phân tìm kiếm : O(h)
+ AVL : O(h) ~ O(lgn) ~ log2(n)
+ bảng băm : O(1)

Bảng băm gồm có 3 phần:
- Dữ liệu cần lưu trữ x
- Hàm băm H(x)
- Bảng để lưu trữ dữ liệu T

Hiện tượng đụng độ: hai khoá chung một vị trí trên
bảng băm

Xử lý đụng độ : chaining, random probing, overflow areas (vùng nhớ được cấp trước, truy cập nhanh, tốn vùng nhớ), re-hashing , using neighbour slots (Linear probing (nhanh, tụ tập)), quadratic probing

Chèn x vào cây AVL TNode *chenx( TNode *&T, int x)
Nếu T= rỗng thì T= new TNode(x);
Ngược lại nếu x= T->data thì báo đã có trong cây
Ngược lại {
if(x<T->data) T->left= chenx(T->left,x); else T->right= chenx(T->right,x);
int h1= cao(T->left); int h2= cao(T->right);
if(h1>h2+1) {
int h11= cao(T->left->left); int h12= cao(T->left->right);
if(h11>h12) T= qL(T); else T= qLR(T);
}
else if (h2>h1+1 ) {
int h22= cao(T->right->right); int h21= cao(T->right->left);
if(h22>h21) T= qR(T); else T= qRL(T); }
}
return T;

- Ngăn xếp : LIFO - 4 - K cố định - (Tạo mới, check rỗng, thêm 1 pt vào đỉnh, lấy 1 pt khỏi đỉnh)

100n , n^2 , n^3/2, 2^n

- Tháp Hà Nội :
1 giây 1000 lần chuyển đĩa.
31536000000 = 365 * 24 * 60 * 60 * 1000
Số đĩa tối đa có thể chuyển là : log2 (31536000000+1) = 34
Số lần chuyển đĩa : 2n- 1
O(2n)

- Xoay dãy A về bên trái k lần
for (int ll=1; ll<=k; ll++) {
int t= a[0];
for(int i=0; i<n-1; i++) a[i]= a[i+1];
    a[n-1]= t;
}
O(kn)

bool SolveSudoku(int grid[9][9]) {
int row, col;
if (!EmptyCell(grid, row, col)) return true;
for (int num = 1; num <= 9; num++)
if (isSafe(grid, row, col, num)) { // số num có thể đặt vào ô r,c
grid[row][col] = num;
if (SolveSudoku(grid)) return true; // đã điền hết thì trả về true
grid[row][col] = 0;
}
return false;
}