Đăng nhập để tham gia lộ trình luyện tập

Some problems in the training are missing or you do not have permission to view them.

65

Hai con trỏ (Two Pointers)

Hai con trỏ là một trong những kỹ thuật quan trọng khi xử lý mảng, dãy số và chuỗi trong lập trình thi đấu.

Thay vì kiểm tra mọi cặp phần tử bằng hai vòng lặp với độ phức tạp thường là $O(n^2)$, ta sử dụng hai vị trí được gọi là hai con trỏ và di chuyển chúng theo một quy luật thích hợp.

Trong nhiều bài toán, cách tiếp cận này có thể giảm độ phức tạp xuống:

hoặc:

nếu cần sắp xếp dữ liệu trước.

Mục tiêu

Sau khi hoàn thành lộ trình, học viên cần:

• hiểu bản chất của kỹ thuật Hai con trỏ;
• nhận biết khi nào có thể sử dụng Hai con trỏ;
• phân biệt vét cạn $O(n^2)$ với lời giải Hai con trỏ;
• xác định đúng vị trí ban đầu của hai con trỏ;
• xác định điều kiện di chuyển từng con trỏ;
• chứng minh được vì sao không bỏ sót đáp án;
• xử lý chính xác các trường hợp biên;
• tự chuyển từ ý tưởng sang chương trình hoàn chỉnh;
• sử dụng thành thạo Hai con trỏ trong các bài thi lập trình.

Các mô hình cần thành thạo

1. Hai con trỏ từ hai đầu

Khởi tạo:

Sau mỗi bước, dựa vào trạng thái hiện tại để tăng $L$ hoặc giảm $R$.

Mô hình này thường xuất hiện trong các bài:

• tìm hai phần tử có tổng cho trước;
• tìm cặp gần giá trị mục tiêu nhất;
• ghép cặp;
• kiểm tra palindrome;
• xử lý dãy đã sắp xếp.

2. Hai con trỏ cùng chiều

Khởi tạo hai vị trí:

Cả hai con trỏ đều di chuyển từ trái sang phải nhưng với tốc độ hoặc điều kiện khác nhau.

Mô hình này thường dùng để:

• loại bỏ phần tử trùng;
• nén mảng;
• gộp dữ liệu;
• duyệt hai dãy đã sắp xếp;
• duy trì hai vị trí có quan hệ với nhau.

3. Hai con trỏ trên hai dãy

Dùng một con trỏ cho mỗi dãy.

Ví dụ:

So sánh hai phần tử hiện tại rồi quyết định tăng $i$, tăng $j$ hoặc tăng cả hai.

Đây là mô hình quan trọng trong:

• trộn hai dãy đã sắp xếp;
• tìm phần tử chung;
• giao của hai dãy;
• so khớp hai dãy;
• ghép các phần tử theo thứ tự.

4. Hai con trỏ nhanh – chậm

Hai con trỏ cùng xuất phát trên một cấu trúc nhưng di chuyển với tốc độ khác nhau.

Ví dụ:

• một con trỏ đi từng bước;
• một con trỏ đi nhanh hơn.

Mô hình này giúp hình thành tư duy về quan hệ giữa hai vị trí và là nền tảng cho một số kỹ thuật xử lý dãy và cấu trúc liên kết.

Tư duy quan trọng

Khi gặp một bài toán có thể sử dụng Hai con trỏ, cần trả lời được các câu hỏi:

1. Hai con trỏ đại diện cho điều gì?
2. Chúng bắt đầu ở đâu?
3. Khi nào di chuyển con trỏ trái?
4. Khi nào di chuyển con trỏ phải?
5. Có trường hợp nào phải di chuyển cả hai?
6. Điều kiện dừng là gì?
7. Vì sao việc di chuyển một con trỏ không làm mất nghiệm?
8. Mỗi con trỏ có thể di chuyển tối đa bao nhiêu lần?

Nếu mỗi con trỏ chỉ đi qua dãy một lần thì tổng số lần dịch chuyển thường không vượt quá một hằng số nhân với $n$.

Vì vậy độ phức tạp có thể đạt:

Lộ trình học

Học viên nên luyện theo thứ tự:

1. Vét cạn mọi cặp phần tử.
2. Hai con trỏ từ hai đầu.
3. Tìm cặp trong dãy đã sắp xếp.
4. Ghép cặp tối ưu.
5. Hai con trỏ cùng chiều.
6. Loại bỏ phần tử trùng.
7. Trộn hai dãy đã sắp xếp.
8. Tìm giao của hai dãy.
9. Các bài cần sắp xếp trước khi dùng Hai con trỏ.
10. Các bài tổng hợp yêu cầu tự nhận ra quy luật di chuyển.

Yêu cầu khi luyện tập

Không nên chỉ ghi nhớ mẫu chương trình.

Với mỗi bài, hãy tự xác định:

• lời giải vét cạn;
• điểm gây chậm của lời giải vét cạn;
• tính chất giúp loại bỏ các trường hợp không cần xét;
• ý nghĩa của từng con trỏ;
• quy tắc di chuyển;
• điều kiện dừng;
• độ phức tạp cuối cùng.

Mục tiêu của lộ trình không phải chỉ biết viết một mẫu Hai con trỏ, mà là có thể tự nhận ra và xây dựng quy luật di chuyển hai con trỏ cho một bài toán mới.