Khóa học CTDL và GT

Bài 6.4. Kỹ thuật Two Pointers và ứng dụng

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Trong thế giới lập trình cạnh tranh ngày nay, việc tối ưu hiệu suất của code là cực kỳ quan trọng. Một trong những kỹ thuật kinh điển và mạnh mẽ giúp cải thiện đáng kể thời gian chạy cho nhiều bài toán trên mảng (arrays), chuỗi (strings) hay danh sách liên kết (linked lists) chính là Kỹ thuật Two Pointers.

Nếu bạn đã từng vật lộn với các vòng lặp lồng nhau (nested loops) O(n^2) và ước ao có cách nào đó nhanh hơn, thì Two Pointers chính là lời giải mà bạn đang tìm kiếm cho nhiều trường hợp!

Two Pointers là gì? Ý tưởng cốt lõi

Đúng như tên gọi, kỹ thuật Two Pointers (hai con trỏ) sử dụng hai con trỏ (thường là các chỉ số - index trong mảng hoặc chuỗi, hoặc các node trong danh sách liên kết) để duyệt qua hoặc thao tác trên một cấu trúc dữ liệu theo một cách có định hướng.

Ý tưởng trung tâm là: thay vì duyệt qua tất cả các cặp phần tử khả thi (thường dẫn đến O(n^2)), chúng ta sử dụng mối quan hệ giữa hai con trỏ để thu hẹp không gian tìm kiếm hoặc hoàn thành thao tác trong một lần duyệt duy nhất hoặc một số lần duyệt tuyến tính.

Điểm đặc biệt của kỹ thuật này là cách chúng ta di chuyển hai con trỏ:

1. Di chuyển từ hai đầu vào giữa: Một con trỏ bắt đầu từ đầu (index 0), con trỏ còn lại bắt đầu từ cuối (index n-1). Cả hai di chuyển dần về phía trung tâm. Kỹ thuật này cực kỳ hiệu quả khi làm việc với dữ liệu đã được sắp xếp.
2. Di chuyển cùng hướng (thường là từ đầu): Cả hai con trỏ bắt đầu ở hoặc gần đầu của cấu trúc dữ liệu và di chuyển theo cùng một hướng, nhưng với tốc độ khác nhau hoặc có điều kiện riêng để di chuyển. Một con trỏ có thể đi trước ("fast pointer"), con còn lại theo sau ("slow pointer").
3. Di chuyển song song: Hai con trỏ duy trì một khoảng cách cố định hoặc di chuyển cùng nhau theo một logic nhất định.

Việc di chuyển các con trỏ phụ thuộc vào điều kiện mà bài toán đặt ra. Mỗi bước di chuyển của một hoặc cả hai con trỏ sẽ giúp chúng ta tiến gần hơn đến lời giải.

Hãy cùng đi sâu vào các ví dụ cụ thể để thấy sức mạnh thực sự của Two Pointers!

Ứng dụng thực tế: Các bài toán kinh điển

Ví dụ 1: Tìm cặp số có tổng bằng X trong mảng đã sắp xếp

Đây là bài toán kinh điển minh họa cho kỹ thuật Two Pointers di chuyển từ hai đầu vào giữa trên mảng đã sắp xếp.

Bài toán: Cho một mảng số nguyên a đã được sắp xếp theo thứ tự tăng dần và một số nguyên X. Hãy kiểm tra xem có tồn tại cặp chỉ số i, j nào sao cho a[i] + a[j] == X hay không.

Cách tiếp cận thông thường (Naive): Dùng hai vòng lặp lồng nhau, duyệt qua mọi cặp (i, j) và kiểm tra tổng. Độ phức tạp thời gian: O(n^2). Với n lớn, cách này sẽ rất chậm.

Cách tiếp cận Two Pointers: Vì mảng đã được sắp xếp, chúng ta có thể tận dụng lợi thế này.

1. Khởi tạo hai con trỏ: left ở vị trí đầu tiên (index 0), right ở vị trí cuối cùng (index n-1).
2. Trong khi left < right:
   • Tính tổng của hai phần tử hiện tại: current_sum = a[left] + a[right].
   • Nếu current_sum == X, chúng ta đã tìm thấy cặp số, trả về true.
   • Nếu current_sum < X, điều đó có nghĩa là tổng hiện tại quá nhỏ. Vì a[left] là phần tử nhỏ nhất ở phía bên trái còn chưa được xem xét, để tăng tổng lên, chúng ta phải tăng giá trị của a[left] bằng cách di chuyển con trỏ left sang phải (left++). Các phần tử ở bên trái a[left] đều nhỏ hơn hoặc bằng nó, nên không thể tạo ra tổng bằng X nếu kết hợp với a[right].
   • Nếu current_sum > X, điều đó có nghĩa là tổng hiện tại quá lớn. Tương tự, vì a[right] là phần tử lớn nhất ở phía bên phải còn chưa được xem xét, để giảm tổng xuống, chúng ta phải giảm giá trị của a[right] bằng cách di chuyển con trỏ right sang trái (right--). Các phần tử ở bên phải a[right] đều lớn hơn hoặc bằng nó.
3. Nếu vòng lặp kết thúc mà không tìm thấy cặp nào có tổng bằng X, trả về false.

Tại sao lại hiệu quả? Với mỗi bước lặp, chúng ta loại bỏ được ít nhất một phần tử (hoặc a[left] hoặc a[right]) khỏi không gian tìm kiếm khả thi. Điều này đảm bảo vòng lặp sẽ kết thúc sau tối đa n bước, đưa độ phức tạp thời gian xuống còn O(n). Độ phức tạp không gian là O(1) vì chúng ta chỉ dùng vài biến con trỏ.

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <algorithm> // Chỉ cần cho std::sort nếu mảng chưa sắp xếp, nhưng bài toán giả định đã sắp xếp

bool findPairWithSum(const std::vector<int>& arr, int targetSum) {
    // Kỹ thuật Two Pointers chỉ hoạt động hiệu quả trên mảng ĐÃ SẮP XẾP
    // Giả định mảng arr đã được sắp xếp tăng dần.
    // Nếu mảng chưa sắp xếp, bạn cần sắp xếp trước:
    // std::vector<int> sorted_arr = arr;
    // std::sort(sorted_arr.begin(), sorted_arr.end());
    // Sau đó áp dụng kỹ thuật Two Pointers trên sorted_arr.

    int left = 0; // Con trỏ bắt đầu từ đầu mảng
    int right = arr.size() - 1; // Con trỏ bắt đầu từ cuối mảng

    // Tiếp tục tìm kiếm trong khi hai con trỏ chưa gặp nhau hoặc vượt qua nhau
    while (left < right) {
        int currentSum = arr[left] + arr[right];

        // Trường hợp 1: Tổng hiện tại bằng với tổng mục tiêu
        if (currentSum == targetSum) {
            // Tìm thấy cặp số có tổng bằng targetSum
            // Bạn có thể trả về true hoặc cặp chỉ số (left, right)
            std::cout << "Found pair: " << arr[left] << " + " << arr[right] << " = " << targetSum << std::endl;
            return true; 
        } 
        // Trường hợp 2: Tổng hiện tại nhỏ hơn tổng mục tiêu
        // Cần tăng tổng lên. Di chuyển con trỏ 'left' sang phải
        // để sử dụng một số lớn hơn ở phía bên trái.
        else if (currentSum < targetSum) {
            left++; 
        } 
        // Trường hợp 3: Tổng hiện tại lớn hơn tổng mục tiêu
        // Cần giảm tổng xuống. Di chuyển con trỏ 'right' sang trái
        // để sử dụng một số nhỏ hơn ở phía bên phải.
        else { // currentSum > targetSum
            right--;
        }
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy cặp nào
    std::cout << "No pair found with sum " << targetSum << std::endl;
    return false;
}

int main() {
    std::vector<int> sorted_arr = {2, 7, 11, 15, 20, 25};
    int target = 32; // 7 + 25

    findPairWithSum(sorted_arr, target); // Output: Found pair: 7 + 25 = 32

    target = 10; // No pair
    findPairWithSum(sorted_arr, target); // Output: No pair found with sum 10

    target = 13; // 2 + 11
    findPairWithSum(sorted_arr, target); // Output: Found pair: 2 + 11 = 13

    return 0;
}

Giải thích code:

• Hàm findPairWithSum nhận vào mảng arr (giả định đã sắp xếp) và targetSum.
• Chúng ta khởi tạo left = 0 và right = arr.size() - 1.
• Vòng lặp while (left < right) tiếp diễn cho đến khi hai con trỏ gặp nhau hoặc vượt qua nhau.
• Bên trong vòng lặp, chúng ta tính currentSum.
• Dựa vào giá trị currentSum so với targetSum, chúng ta quyết định di chuyển left sang phải (nếu tổng quá nhỏ) hoặc right sang trái (nếu tổng quá lớn).
• Nếu tìm thấy tổng bằng targetSum, hàm in ra cặp số và trả về true.
• Nếu vòng lặp kết thúc mà không tìm thấy, hàm in ra thông báo và trả về false.

Kỹ thuật này là một ví dụ điển hình về việc sử dụng tính chất của dữ liệu đã sắp xếp để tối ưu hóa.

Ví dụ 2: Xóa các phần tử trùng lặp khỏi mảng đã sắp xếp (In-place)

Bài toán này sử dụng một biến thể của Two Pointers, thường gọi là "slow and fast pointers" hoặc "read and write pointers", di chuyển cùng hướng.

Bài toán: Cho một mảng số nguyên nums đã được sắp xếp theo thứ tự tăng dần. Xóa các phần tử trùng lặp tại chỗ (in-place) sao cho mỗi phần tử duy nhất chỉ xuất hiện một lần. Trả về độ dài mới của mảng. Các phần tử sau độ dài mới không quan trọng.

Cách tiếp cận thông thường: Dùng std::set để lưu các phần tử duy nhất, sau đó sao chép trở lại mảng (O(n) space). Hoặc tạo mảng mới (O(n) space). Bài toán yêu cầu in-place (O(1) space).

Cách tiếp cận Two Pointers: Chúng ta sẽ dùng hai con trỏ:

• write_idx (hoặc slow): Chỉ vị trí tiếp theo mà một phần tử duy nhất mới sẽ được ghi vào.
• read_idx (hoặc fast): Duyệt qua tất cả các phần tử của mảng để kiểm tra.

1. Khởi tạo write_idx = 1. (Giả sử phần tử đầu tiên nums[0] luôn là duy nhất và sẽ ở vị trí 0). read_idx sẽ bắt đầu từ 1.
2. Duyệt read_idx từ 1 đến cuối mảng (nums.size() - 1).
3. Tại mỗi vị trí read_idx, so sánh nums[read_idx] với phần tử duy nhất cuối cùng đã được ghi vào vị trí write_idx - 1 (nums[write_idx - 1]).
4. Nếu nums[read_idx] khác với nums[write_idx - 1], điều đó có nghĩa là nums[read_idx] là một phần tử duy nhất mới mà chúng ta chưa gặp. Chúng ta ghi nó vào vị trí write_idx: nums[write_idx] = nums[read_idx]. Sau đó, tăng write_idx lên để chuẩn bị cho vị trí ghi tiếp theo: write_idx++.
5. Nếu nums[read_idx] bằng với nums[write_idx - 1], đó là phần tử trùng lặp. Chúng ta không ghi nó vào vị trí write_idx và không tăng write_idx. Chỉ đơn giản là bỏ qua nó bằng cách tiếp tục vòng lặp (tăng read_idx).
6. Vòng lặp kết thúc khi read_idx duyệt hết mảng. Giá trị cuối cùng của write_idx chính là độ dài mới của mảng sau khi xóa trùng lặp.

Tại sao lại hiệu quả? Con trỏ read_idx đi qua mảng một lần (O(n)). Con trỏ write_idx chỉ tiến lên khi gặp một phần tử duy nhất mới. Toàn bộ quá trình chỉ là một lần duyệt tuyến tính và một số thao tác gán tại chỗ. Độ phức tạp thời gian: O(n). Độ phức tạp không gian: O(1) (in-place).

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort if needed

int removeDuplicates(std::vector<int>& nums) {
    // Mảng nums đã được sắp xếp tăng dần.
    if (nums.empty()) {
        return 0; // Mảng rỗng, độ dài mới là 0
    }

    // write_idx là chỉ số nơi phần tử duy nhất tiếp theo sẽ được ghi
    // Nó cũng đồng thời là độ dài của mảng con chứa các phần tử duy nhất
    int write_idx = 1; 

    // read_idx duyệt qua tất cả các phần tử của mảng
    // Bắt đầu từ 1 vì nums[0] luôn được giữ lại
    for (int read_idx = 1; read_idx < nums.size(); ++read_idx) {
        // So sánh phần tử hiện tại (read_idx) với phần tử duy nhất cuối cùng đã ghi (write_idx - 1)
        if (nums[read_idx] != nums[write_idx - 1]) {
            // Nếu chúng khác nhau, đây là một phần tử duy nhất mới
            // Ghi nó vào vị trí write_idx
            nums[write_idx] = nums[read_idx];
            // Tăng write_idx lên để chuẩn bị cho vị trí ghi tiếp theo
            write_idx++;
        }
        // Nếu nums[read_idx] == nums[write_idx - 1], đó là phần tử trùng lặp,
        // chúng ta bỏ qua nó và read_idx tự động tăng ở cuối vòng lặp for.
    }

    // write_idx lúc này chính là độ dài mới của mảng không có phần tử trùng lặp
    return write_idx;
}

int main() {
    std::vector<int> nums1 = {1, 1, 2};
    int new_length1 = removeDuplicates(nums1);
    std::cout << "New length 1: " << new_length1 << std::endl; // Output: 2
    std::cout << "Modified array 1: ";
    for (int i = 0; i < new_length1; ++i) {
        std::cout << nums1[i] << (i == new_length1 - 1 ? "" : ", "); // Output: 1, 2
    }
    std::cout << std::endl;

    std::vector<int> nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    int new_length2 = removeDuplicates(nums2);
    std::cout << "New length 2: " << new_length2 << std::endl; // Output: 5
    std::cout << "Modified array 2: ";
    for (int i = 0; i < new_length2; ++i) {
        std::cout << nums2[i] << (i == new_length2 - 1 ? "" : ", "); // Output: 0, 1, 2, 3, 4
    }
    std::cout << std::endl;

    return 0;
}

Giải thích code:

• Hàm removeDuplicates nhận mảng nums bằng tham chiếu (&) để có thể sửa đổi tại chỗ.
• Chúng ta xử lý trường hợp mảng rỗng.
• write_idx bắt đầu ở 1. Phần tử nums[0] mặc nhiên được giữ lại. write_idx sẽ chỉ ra vị trí trống đầu tiên trong "vùng duy nhất" để ghi một phần tử mới vào.
• read_idx là vòng lặp for duyệt từ index 1 đến hết mảng.
• Trong mỗi lần lặp, chúng ta so sánh nums[read_idx] với phần tử ở nums[write_idx - 1]. nums[write_idx - 1] là phần tử cuối cùng trong vùng đã được xác định là duy nhất.
• Nếu nums[read_idx] khác, nó là một phần tử duy nhất mới. Chúng ta sao chép nó đến vị trí write_idx và tăng write_idx.
• Nếu trùng lặp, write_idx đứng yên, và chúng ta chỉ đơn giản là bỏ qua nó khi read_idx tiến lên.
• Cuối cùng, write_idx chứa số lượng phần tử duy nhất, đồng thời cũng là độ dài "hiệu quả" của mảng sau khi loại bỏ trùng lặp.

Ví dụ 3: Kiểm tra chuỗi Palindrome (có xem xét ký tự không phải chữ-số)

Bài toán này sử dụng kỹ thuật Two Pointers di chuyển từ hai đầu vào giữa trên một chuỗi, nhưng có thêm điều kiện xử lý ký tự.

Bài toán: Cho một chuỗi s. Kiểm tra xem nó có phải là palindrome hay không. Chỉ xem xét các ký tự chữ và số, bỏ qua chữ hoa/thường.

Cách tiếp cận thông thường: Tạo một chuỗi mới chỉ chứa các ký tự chữ và số, chuyển hết về chữ thường, sau đó kiểm tra xem chuỗi mới này có bằng chuỗi đảo ngược của nó hay không. Độ phức tạp không gian O(n).

Cách tiếp cận Two Pointers (O(1) space):

1. Khởi tạo hai con trỏ: left ở đầu chuỗi (index 0), right ở cuối chuỗi (index s.length() - 1).
2. Trong khi left < right:
   • Di chuyển left: Bỏ qua các ký tự không phải chữ và số từ bên trái. Tăng left lên cho đến khi left chỉ vào một ký tự chữ hoặc số, hoặc left >= right.
   • Di chuyển right: Bỏ qua các ký tự không phải chữ và số từ bên phải. Giảm right xuống cho đến khi right chỉ vào một ký tự chữ hoặc số, hoặc left >= right.
   • Kiểm tra điều kiện dừng: Sau khi bỏ qua, nếu left >= right, điều đó có nghĩa là các ký tự còn lại giữa hai con trỏ tạo thành một chuỗi rỗng hoặc chỉ có một ký tự, luôn là palindrome. Trả về true.
   • So sánh ký tự: Chuyển cả s[left] và s[right] về cùng một trường hợp (ví dụ: chữ thường) bằng tolower(). So sánh hai ký tự đã chuyển đổi. Nếu chúng khác nhau, chuỗi không phải là palindrome. Trả về false.
   • Di chuyển vào trong: Nếu hai ký tự khớp nhau, di chuyển cả hai con trỏ vào trong: left++, right--.
3. Nếu vòng lặp kết thúc mà không trả về false, điều đó có nghĩa là tất cả các cặp ký tự chữ-số tương ứng đều khớp nhau. Chuỗi là palindrome. Trả về true.

Tại sao lại hiệu quả? Chúng ta chỉ duyệt qua chuỗi một lần từ hai phía (tối đa O(n) bước). Các thao tác bỏ qua và so sánh là O(1). Độ phức tạp thời gian: O(n). Độ phức tạp không gian: O(1) vì không cần lưu trữ thêm chuỗi mới.

Code minh họa (C++):

#include <iostream>
#include <string>
#include <cctype> // For isalnum and tolower

bool isPalindrome(const std::string& s) {
    if (s.empty()) {
        return true; // Chuỗi rỗng được coi là palindrome
    }

    int left = 0; // Con trỏ từ đầu chuỗi
    int right = s.length() - 1; // Con trỏ từ cuối chuỗi

    // Duyệt trong khi hai con trỏ chưa gặp nhau hoặc vượt qua nhau
    while (left < right) {
        // Bỏ qua các ký tự không phải chữ hoặc số từ bên trái
        while (left < right && !std::isalnum(s[left])) {
            left++;
        }

        // Bỏ qua các ký tự không phải chữ hoặc số từ bên phải
        while (left < right && !std::isalnum(s[right])) {
            right--;
        }

        // Sau khi bỏ qua, kiểm tra lại điều kiện left < right
        // Nếu left >= right, các ký tự còn lại (nếu có) đã được kiểm tra
        if (left >= right) {
            break; // Hoặc có thể return true ở đây
        }

        // So sánh các ký tự chữ/số, không phân biệt chữ hoa/thường
        if (std::tolower(s[left]) != std::tolower(s[right])) {
            // Nếu không khớp, chuỗi không phải palindrome
            return false;
        }

        // Nếu khớp, di chuyển cả hai con trỏ vào trong
        left++;
        right--;
    }

    // Nếu vòng lặp hoàn thành mà không trả về false, chuỗi là palindrome
    return true;
}

int main() {
    std::string s1 = "A man, a plan, a canal: Panama";
    std::cout << "\"" << s1 << "\" is palindrome: " << (isPalindrome(s1) ? "True" : "False") << std::endl; // Output: True

    std::string s2 = "race a car";
    std::cout << "\"" << s2 << "\" is palindrome: " << (isPalindrome(s2) ? "True" : "False") << std::endl; // Output: False

    std::string s3 = " ";
    std::cout << "\"" << s3 << "\" is palindrome: " << (isPalindrome(s3) ? "True" : "False") << std::endl; // Output: True (sau khi bỏ qua khoảng trắng)

    std::string s4 = "ab@a";
    std::cout << "\"" << s4 << "\" is palindrome: " << (isPalindrome(s4) ? "True" : "False") << std::endl; // Output: True ('a' == 'a')

    return 0;
}

Giải thích code:

• Hàm isPalindrome nhận chuỗi s.
• Chúng ta xử lý trường hợp chuỗi rỗng.
• left và right được khởi tạo ở hai đầu.
• Vòng lặp while (left < right) là vòng lặp chính.
• Bên trong vòng lặp chính, chúng ta có hai vòng lặp while nhỏ hơn để di chuyển left và right qua các ký tự không phải chữ hoặc số. Điều kiện left < right được kiểm tra trong cả các vòng lặp nhỏ để đảm bảo con trỏ không đi quá nhau.
• Sau khi bỏ qua, chúng ta kiểm tra lại left < right. Nếu không còn ký tự chữ-số để so sánh (ví dụ: chuỗi chỉ chứa dấu câu), vòng lặp sẽ kết thúc hoặc điều kiện left >= right sẽ đúng, và chúng ta trả về true.
• Nếu vẫn còn cặp ký tự chữ-số để so sánh, chúng ta dùng std::tolower() để chuyển chúng về chữ thường rồi so sánh. Nếu không khớp, trả về false.
• Nếu khớp, di chuyển cả left và right vào trong và lặp lại.
• Nếu vòng lặp chính kết thúc mà không tìm thấy sự không khớp nào, chuỗi là palindrome.

Ví dụ 4: Đảo ngược mảng hoặc chuỗi (In-place)

Một ứng dụng đơn giản nhưng hiệu quả của Two Pointers di chuyển từ hai đầu vào giữa.

Bài toán: Đảo ngược thứ tự các phần tử trong một mảng số nguyên hoặc các ký tự trong một chuỗi tại chỗ (in-place).

Cách tiếp cận thông thường: Tạo mảng/chuỗi mới và sao chép các phần tử/ký tự theo thứ tự ngược lại (O(n) space).

Cách tiếp cận Two Pointers (O(1) space):

1. Khởi tạo hai con trỏ: left ở đầu (index 0), right ở cuối (index n-1).
2. Trong khi left < right:
   • Đổi chỗ (swap) phần tử tại vị trí left với phần tử tại vị trí right.
   • Di chuyển left sang phải (left++).
   • Di chuyển right sang trái (right--).
3. Vòng lặp kết thúc khi left và right gặp nhau hoặc vượt qua nhau (ở giữa mảng/chuỗi). Toàn bộ mảng/chuỗi đã được đảo ngược.

Tại sao lại hiệu quả? Mỗi lần lặp, chúng ta xử lý một cặp phần tử ở hai đầu và di chuyển vào trong. Chỉ cần n/2 lần lặp là đủ để đảo ngược toàn bộ mảng/chuỗi. Độ phức tạp thời gian: O(n). Độ phức tạp không gian: O(1) (in-place).

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // For std::swap

template <typename T>
void reverse(std::vector<T>& arr) {
    int left = 0; // Con trỏ từ đầu mảng
    int right = arr.size() - 1; // Con trỏ từ cuối mảng

    // Duyệt trong khi hai con trỏ chưa gặp nhau
    while (left < right) {
        // Đổi chỗ phần tử ở vị trí left và right
        std::swap(arr[left], arr[right]);

        // Di chuyển con trỏ vào trong
        left++;
        right--;
    }
}

void reverse(std::string& s) {
    int left = 0; // Con trỏ từ đầu chuỗi
    int right = s.length() - 1; // Con trỏ từ cuối chuỗi

    // Duyệt trong khi hai con trỏ chưa gặp nhau
    while (left < right) {
        // Đổi chỗ ký tự ở vị trí left và right
        std::swap(s[left], s[right]);

        // Di chuyển con trỏ vào trong
        left++;
        right--;
    }
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::cout << "Original vector: ";
    for (int x : numbers) std::cout << x << " ";
    std::cout << std::endl;

    reverse(numbers);
    std::cout << "Reversed vector: ";
    for (int x : numbers) std::cout << x << " ";
    std::cout << std::endl; // Output: 5 4 3 2 1

    std::string text = "hello";
    std::cout << "Original string: " << text << std::endl;

    reverse(text);
    std::cout << "Reversed string: " << text << std::endl; // Output: olleh

    return 0;
}

Giải thích code:

• Chúng ta tạo hai hàm reverse quá tải (overload) cho std::vector và std::string vì cú pháp truy cập phần tử hơi khác nhau một chút (mặc dù về mặt logic, cả hai đều hoạt động trên cấu trúc tuần tự).
• Khởi tạo left và right ở hai đầu.
• Vòng lặp while (left < right) chạy cho đến khi các cặp ở hai đầu đã được đổi chỗ và các con trỏ gặp nhau hoặc vượt qua nhau.
• Hàm std::swap được sử dụng để đổi chỗ hiệu quả hai phần tử/ký tự.
• Sau mỗi lần đổi chỗ, left tăng và right giảm, tiến dần vào giữa.

Lợi ích của Kỹ thuật Two Pointers

• Hiệu suất thời gian vượt trội: Thường biến các giải pháp O(n^2) sử dụng vòng lặp lồng nhau thành giải pháp O(n) chỉ với một hoặc vài lần duyệt tuyến tính.
• Hiệu suất không gian tối ưu: Thường cho phép giải quyết bài toán tại chỗ (in-place), chỉ sử dụng không gian bổ sung hằng số O(1) cho các con trỏ, thay vì O(n) cho các cấu trúc dữ liệu phụ trợ.
• Đơn giản và thanh lịch: Khi bạn nhận ra rằng Two Pointers có thể áp dụng, giải pháp thường trở nên rất gọn gàng và dễ hiểu.

Khi nào nên nghĩ đến Kỹ thuật Two Pointers?

Bạn nên cân nhắc sử dụng Kỹ thuật Two Pointers khi bài toán liên quan đến:

• Duyệt hoặc thao tác trên các cấu trúc dữ liệu tuần tự: Mảng, chuỗi, danh sách liên kết.
• Tìm kiếm cặp phần tử hoặc các phần tử có mối quan hệ: Đặc biệt khi mối quan hệ đó phụ thuộc vào vị trí tương đối của chúng (ví dụ: cặp có tổng bằng X, tìm phần tử trùng lặp, kiểm tra đối xứng).
• Yêu cầu giải quyết bài toán tại chỗ (in-place) hoặc tối ưu không gian.
• Dữ liệu đầu vào đã được sắp xếp: Đây là dấu hiệu nhận biết mạnh mẽ nhất cho kỹ thuật Two Pointers di chuyển từ hai đầu vào giữa. Kỹ thuật này tận dụng triệt để tính chất của mảng đã sắp xếp để loại bỏ các khả năng một cách hiệu quả.

Bài tập ví dụ:

Đếm cặp số nguyên tố cùng nhau

Cho một dãy số nguyên dương có n phần tử. Hãy đếm các cặp số nguyên tố cùng nhau trong mảng.

Input Format

Dòng đầu tiên là số lượng phần tử trong mảng n. Dòng thứ 2 là các phần tử ai trong mảng(1≤n≤1000; 1≤ai≤10^9).

Constraints

.

Output Format

In ra số lượng cặp số nguyên tố cùng nhau trong mảng.

Ví dụ:

Dữ liệu vào

5
2 4 3 6 7

Dữ liệu ra

6

Để giải bài toán "Đếm cặp số nguyên tố cùng nhau", bạn cần thực hiện các bước sau:

1. Hiểu khái niệm: Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau (hoặc coprime) nếu ước chung lớn nhất (ƯCLN - GCD) của chúng bằng 1, tức là ƯCLN(a, b) = 1.

2. Ý tưởng chính: Duyệt qua tất cả các cặp số phân biệt trong mảng đã cho. Với mỗi cặp, kiểm tra xem chúng có nguyên tố cùng nhau hay không. Nếu có, tăng bộ đếm lên 1.

3. Cách duyệt các cặp phân biệt: Sử dụng hai vòng lặp lồng nhau.

   • Vòng lặp ngoài: Chạy chỉ số i từ 0 đến n-2.
   • Vòng lặp trong: Chạy chỉ số j từ i+1 đến n-1. Điều này đảm bảo bạn xét từng cặp (a[i], a[j]) chỉ một lần và không xét các cặp (a[i], a[i]) hay các cặp trùng lặp như (a[j], a[i]).

4. Tính ƯCLN: Đối với mỗi cặp số (a[i], a[j]), bạn cần tính ước chung lớn nhất của chúng. Thuật toán Euclid là phương pháp hiệu quả để làm điều này. Trong C++, bạn có thể sử dụng hàm std::gcd có sẵn trong thư viện <numeric> (từ C++17 trở lên), hoặc tự cài đặt hàm tính ƯCLN bằng thuật toán Euclid.

5. Kiểm tra và đếm: Sau khi tính được UCLN(a[i], a[j]), kiểm tra xem nó có bằng 1 hay không. Nếu UCLN == 1, tăng một biến đếm đã được khởi tạo ban đầu bằng 0.

6. Kết quả: Sau khi hoàn thành việc duyệt qua tất cả các cặp, giá trị cuối cùng của biến đếm chính là số lượng cặp số nguyên tố cùng nhau trong mảng. In giá trị này ra màn hình.

Làm thêm nhiều bài tập miễn phí tại đây