Thuật toán trong lập trình - Phần 3: Two Pointer và Sliding Window
Trong bài viết cuối cùng của series này chúng ta sẽ cùng tìm hiểu về hai thuật toán/kỹ thuật được sử dụng khá rộng là: Two Pointer & Sliding Window.
Danh sách các bài viết:
Thuật toán Two Pointer
Two Pointer là một trong những kỹ thuật quan trọng của bất kì lập trình viên nào, thậm chí đối với những người mới bắt đầu, vì nó sẽ hỗ trợ chúng ta trong suốt hành trình làm trong lĩnh vực lập trình. Bây giờ, chúng ta sẽ cùng nhau tìm hiểu về Two Pointer thông qua ba câu hỏi Là gì?, Tại sao? và Thực hiện như thế nào?
Kỹ thuật Two Pointer là gì?
Với Two Pointer chúng ta sẽ sử dụng hai con trỏ để di chuyển trên một danh sách/mảng/chuỗi để thực hiện các thao tác tìm kiếm trong một vòng lặp trên cấu trúc dữ liệu. Nó bao gồm hai biến thể:
Opposite-Directional: mỗi con trỏ được đặt ở hai đầu của mảng và chúng di chuyển về phía nhau cho đến khi chúng gặp nhau hoặc thỏa mãn một số điều kiện.
Equi-Directional: mỗi con trỏ đều bắt đầu ở đầu mảng, một con là con trỏ di chuyển chậm trong khi con còn lại là con trỏ nhanh hơn, di chuyển theo cùng một hướng cho đến khi thỏa một điều kiện nhất định nào đó.
Tại sao sử dụng kỹ thuật Two Pointer?
Lý do quan trọng nhất đằng sau việc sử dụng kỹ thuật này là để giảm độ phức tạp về thời gian của một bài toán từ O(n3) hoặc O(n2) thành O(n) hoặc O(nlogn) tùy thuộc vào việc mảng có được sắp xếp hay không.
Làm thế nào để sử dụng kỹ thuật Two Pointer?
Chúng ta sẽ tìm hiểu kỹ thuật này bằng cách xem qua ví dụ sau:
Đề bài: Cho một mảng các số nguyên number đã được sắp xếp theo thứ tự tăng dần, hãy tìm hai số sao cho tổng của chúng thành một số target. Kết quả trả về là một mảng lưu vị trí của 2 số đó.
Trong đó: 1 <= answer [0] < answer [1] <= number.length.
Ví dụ:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Giải thích: Tại vì 2 + 7 = 9 mà 2 ở vị trí số 1, 7 ở vị trí số 2 nên kết quả trả về là [1,2].
Như đề bài, chúng ta được cho một mảng và một số đã được sắp xếp, chúng ta phải duyệt qua mảng và xác định vị trí hai số cộng lại bằng với số đã cho, rồi trả về vị trí của những số đó. Bây giờ chúng ta hãy nói về các cách tiếp cận có thể được sử dụng để giải quyết vấn đề này:
Brute Force có Độ phức tạp thời gian: O(n2)
Two Pointer có Độ phức tạp thời gian: O(n)
Cách tiếp cận đầu tiên về bản chất rất đơn giản nhưng mất rất nhiều thời gian. Dưới đây là chi tiết về 2 thuật toán:
Brute Force: Trong thuật toán vét cạn này, chúng ta sẽ sử dụng hai vòng lặp, vòng lặp bên ngoài lặp lại từng phần tử một và vòng lặp bên trong thực hiện tương tự nhưng với mỗi lần duyệt qua một phần tử của vòng ngoài, vòng lặp bên trong sẽ lặp toàn bộ mảng. Trong cách tiếp cận này, chúng ta sẽ kiểm tra tổng của tất cả các trường hợp có thể có và sau đó so sánh với tổng đã cho để kiểm tra xem chúng có bằng nhau không.
Two Pointer: Chúng ta sẽ sử dụng hai con trỏ trong phương pháp này để khám phá các phần tử trong mảng đã sắp xếp có giá trị mong muốn hay không. Chúng ta bắt đầu bằng cách khởi tạo hai con trỏ, một con trỏ ở chỉ mục ngoài cùng bên trái: start = 0 và con trỏ còn lại ở cuối mảng: end = length (array) -1. Bây giờ chúng ta sẽ lặp lại mảng cho đến khi chỉ mục start < end, sau đó cộng các phần tử được con trỏ tham chiếu để xem chúng có bằng với số được yêu cầu hay không. Chúng ta có thể trả về start và end nếu thỏa mãn yêu cầu. Nếu tổng lớn hơn số yêu cầu, chúng ta sẽ giảm end đi một đơn vị (end -1). Nếu không, chúng ta sẽ tăng start lên một đơn vị (start + 1). Bởi vì mảng đã được sắp xếp nên chúng ta có thể tận dụng lợi thế là nếu chúng ta giảm biến end, số được trỏ bởi nó sẽ nhỏ hơn số phía trước nó, từ đó giảm tổng của hai số. Tương tự khi tăng biến start tổng của hai số sẽ tăng.
Thuật toán Sliding Window
Sau khi tìm hiểu về thuật toán Two Pointer, chúng ta sẽ nói về thuật toán Sliding Window vì sau kỹ thuật Two Pointer, nó là một kỹ thuật mà chúng ta nên học. Tương tự, chúng ta cũng sẽ tìm hiểu kỹ thuật này thông qua ba câu hỏi là: Là gì?, Tại sao?, Thực hiện như thế nào?.
Thuật toán Sliding Window là gì?
Các vấn đề liên quan đến chuỗi tuyến tính, chẳng hạn như mảng, có thể được giải quyết bằng cách sử dụng phương pháp Sliding Window - cửa sổ trượt. Một dãy liền kề là một phần của mảng hay được gọi là cửa sổ (Window). Giống như tên của kỹ thuật này, cửa sổ sẽ được trượt trên mảng khi hoàn thành một số thao tác được thực hiện trên các phần tử bên trong. Có nhiều biến thể khác nhau của thuật toán này nhưng chúng ta sẽ chỉ đề cập đến một biến thể chung nhất.
Tại sao sử dụng thuật toán Sliding Window?
Thuật toán này giúp chúng ta giảm độ phức tạp về thời gian giống như thuật toán Two Pointer. Các biến thể của thuật toán này được một phần lớn cộng đồng lập trình sử dụng.
Làm thế nào để sử dụng thuật toán Sliding Window?
Chúng ta sẽ tìm hiểu điều này bằng cách xem qua ví dụ sau:
Đề bài: Cho một số mảng số nguyên n phần tử và một số nguyên k. Tìm một mảng con liền kề nhau có độ dài bằng k có giá trị trung bình lớn nhất và trả về giá trị này. Bất kỳ kết quả nào có sai số tính toán nhỏ hơn 10-5 sẽ được chấp nhận.
Ví dụ:
Input: numbers = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Giải thích: Giá trị trung bình lớn nhất của mảng con là: (12-5-6+50)/4 = 51/4 = 12.75
Bây giờ, hãy nói về các phương pháp có thể được sử dụng để giải quyết vấn đề này:
Brute Force có Độ phức tạp thời gian: O(n2)
Sliding Window có Độ phức tạp thời gian: O(n)
Cách đầu tiên về bản chất rất đơn giản nhưng tốn rất nhiều thời gian. Đối với cách tiếp cận này, các bạn có thể tự mình thực hiện vì nó rất đơn giản. Chúng ta sẽ chỉ tìm hiểu về cách tiếp cận Sliding Window cho vấn đề này thôi nhé!
Phương pháp tiếp cận Sliding Window: Ý tưởng chính là thiết lập một cửa sổ có kích thước k, sau đó dịch cửa sổ đó trên toàn mảng nghĩa là thêm phần tử sau và loại bỏ phần tử trước, sau đó chia nó cho k để tìm và so sánh giá trị trung bình để tìm ra mảng có giá trị trung bình lớn nhất. Vì vậy, chúng ta sẽ tạo ra hai biến: current_sum và max_sum. Chúng ta lưu trữ tổng của k phần tử đầu tiên trong current_sum trước khi đặt max_sum bằng current_sum. Bây giờ chúng ta bắt đầu duyệt mảng, bắt đầu từ chỉ số k và đi đến cuối mảng, cập nhật biến current_sum bằng cách thêm phần tử sau và xóa phần trước đó. Thực hiện cho đến khi đạt được tổng lớn nhất tương ứng với kích thước cửa sổ k. Cuối cùng chúng ta chỉ cần chia nó cho k để lấy giá trị trung bình.
Đây cũng là bài viết cuối cùng, kết thúc loạt bài về “Thuật toán trong lập trình” bao gồm những thuật toán cơ bản nhất dành cho những người mới tiếp xúc với khái niệm lập trình và thuật toán. Hi vọng series này sẽ giúp ích cho bạn. Happy coding!!!