Áp dụng phương pháp hai con trỏ để xử lý 7 bài toán liên quan đến mảng.

1. Tổng hai số II - Mảng đầu vào đã sắp xếp tăng dần: Cho mảng được sắp xếp theo thứ tự tăng dần, tìm hai phần tử có tổng bằng giá trị mục tiêu. Sử dụng kỹ thuật hai con trỏ đặt ở hai đầu mảng, di chuyển con trỏ dựa trên so sánh tổng và giá trị mục tiêu.
2. Xóa phần tử trùng lặp trong mảng đã sắp xếp: Với mảng có thứ tự, xóa các phần tử trùng lặp để chỉ còn duy nhất một lần xuất hiện, trả về độ dài mảng mới. Áp dụng hai con trỏ, một con trỏ duyệt mảng, con trỏ còn lại ghi nhận vị trí cuối cùng của mảng mới.
3. Loại bỏ giá trị cụ thể: Xóa toàn bộ phần tử có giá trị bằng một giá trị cho trước trong mảng, trả về độ dài mảng mới. Sử dụng hai con trỏ, một con trỏ duyệt mảng, con trỏ còn lại ghi nhận vị trí phần tử không trùng với giá trị mục tiêu.
4. Di chuyển phần tử 0 về cuối: Đưa toàn bộ số 0 về cuối mảng, giữ nguyên thứ tự các phần tử khác. Áp dụng hai con trỏ, một con trỏ duyệt mảng, con trỏ còn lại ghi nhận vị trí phần tử khác 0 để chuyển lên đầu.
5. Đảo ngược chuỗi ký tự: Đảo ngược chuỗi ký tự đầu vào. Sử dụng hai con trỏ, một con trỏ bắt đầu từ đầu mảng, con trỏ còn lại bắt đầu từ cuối mảng, hoán đổi các phần tử tương ứng.
6. Tìm chuỗi đối xứng dài nhất: Tìm chuỗi con đối xứng dài nhất trong chuỗi đầu vào. Sử dụng phương pháp mở rộng từ tâm kết hợp kỹ thuật hai con trỏ để xác định các chuỗi đối xứng trong quá trình duyệt.
7. Xóa phần tử trùng lặp trong danh sách liên kết đã sắp xếp: Loại bỏ các phần tử trùng lặp trong danh sách liên kết đã sắp xếp, đảm bảo mỗi phần tử chỉ xuất hiện duy nhất một lần. Áp dụng hai con trỏ, một con trỏ duyệt danh sách, con trỏ còn lại thực hiện xóa phần tử trùng lặp.

1. Đảo ngược chuỗi ký tự

Mô tả bài toán

Viết hàm để đảo ngược chuỗi ký tự đầu vào. Chuỗi được truyền dưới dạng mảng s. Yêu cầu thực hiện thay đổi trực tiếp mảng đầu vào mà không sử dụng thêm không gian lưu trữ ngoài, đảm bảo độ phức tạp không gian là O(1).

Ví dụ 1:

<strong>Đầu vào:</strong> s = ["h","e","l","l","o"]
<strong>Đầu ra:</strong> ["o","l","l","e","h"]

Ví dụ 2:

<strong>Đầu vào:</strong> s = ["H","a","n","n","a","h"]
<strong>Đầu ra:</strong> ["h","a","n","n","a","H"]

Gợi ý:

• 1 <= s.length <= 105
• s[i] là ký tự có thể in được trong bảng ASCII

Phương pháp giải và mã nguồn

Hầu hết ngôn ngữ lập trình đều có hàm reverse, nguyên lý hoạt động của hàm này rất đơn giản và có thể thực hiện bằng kỹ thuật hai con trỏ.

Bắt đầu từ hai đầu mảng, di chuyển về phía nhau và hoán đổi các ký tự tại vị trí tương ứng.

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        char temp;
        while (left < right) {
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

Kết quả chạy thử

2. Tìm chuỗi đối xứng dài nhất

Mô tả bài toán

Cho chuỗi s, hãy tìm chuỗi con đối xứng dài nhất trong s.

Chuỗi đối xứng là chuỗi mà khi đảo ngược vẫn giống với chuỗi gốc.

Ví dụ 1:

<strong>Đầu vào:</strong> s = "babad"
<strong>Đầu ra:</strong> "bab"
<strong>Giải thích:</strong> "aba" cũng là đáp án hợp lệ.

Ví dụ 2:

<strong>Đầu vào:</strong> s = "cbbd"
<strong>Đầu ra:</strong> "bb"

Gợi ý:

• 1 <= s.length <= 1000
• s chỉ chứa các chữ số và chữ cái tiếng Anh

Tư duy giải và mã nguồn

Bài toán tìm chuỗi đối xứng dài nhất có thể giải quyết bằng phương pháp mở rộng từ tâm, trong đó kỹ thuật hai con trỏ đóng vai trò quan trọng. Quy trình giải bài toán như sau:

• Với mỗi ký tự s[i], lấy ký tự này làm tâm, sử dụng hàm expandAroundCenter(s, i, i) để tìm chuỗi đối xứng có độ dài lẻ. Lúc này, tâm của chuỗi đối xứng chính là s[i].
• Với hai ký tự liền kề s[i] và s[i+1], lấy chúng làm tâm, sử dụng hàm expandAroundCenter(s, i, i+1) để tìm chuỗi đối xứng có độ dài chẵn.
• Trong quá trình mở rộng, liên tục cập nhật độ dài và vị trí bắt đầu của chuỗi đối xứng dài nhất.

Như vậy, bằng cách duyệt từng ký tự trong chuỗi và mở rộng từ từng tâm có thể, ta sẽ tìm được chuỗi đối xứng dài nhất.

Hàm expandAroundCenter(s, l, r) có nhiệm vụ mở rộng từ vị trí l và r về hai phía để tìm chuỗi đối xứng. Việc triển khai hàm này cần xem xét cả trường hợp chuỗi có độ dài lẻ và chẵn.

class Solution {
    public String longestPalindrome(String s) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            String odd = expandAroundCenter(s, i, i);
            String even = expandAroundCenter(s, i, i + 1);
            result = result.length() > odd.length() ? result : odd;
            result = result.length() > even.length() ? result : even;
        }
        return result;
    }

    private String expandAroundCenter(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        return s.substring(start + 1, end);
    }
}

Kết quả chạy thử