Khóa học CTDL và GT

Bài 8.5. Bài tập tổng hợp về các cấu trúc dữ liệu

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

Chúng ta đã cùng nhau đi qua một hành trình khám phá nhiều loại cấu trúc dữ liệu quan trọng, từ những cấu trúc tuyến tính như danh sách liên kết, stack, queue, đến những cấu trúc phức tạp hơn như cây, đồ thị hay bảng băm. Việc hiểu rõ cách thức hoạt động của từng cấu trúc là cực kỳ quan trọng, nhưng để thực sự thành thạo và biết áp dụng chúng vào giải quyết vấn đề thực tế, không có cách nào tốt hơn là thực hành thông qua các bài tập.

Bài viết này là một điểm dừng quan trọng để chúng ta cùng nhau củng cố lại kiến thức đã học. Thay vì lý thuyết suông, chúng ta sẽ tập trung vào việc vận dụng các cấu trúc dữ liệu đã biết để giải quyết một số bài toán kinh điển và phổ biến. Mỗi bài tập sẽ là một cơ hội để bạn nhìn nhận vấn đề dưới góc độ cấu trúc dữ liệu, lựa chọn công cụ phù hợp và triển khai nó bằng ngôn ngữ C++.

Hãy cùng đi sâu vào các bài tập nhé!

Bài tập 1: Xóa các phần tử trùng lặp trong Danh sách liên kết đơn

Danh sách liên kết là một cấu trúc dữ liệu cơ bản nhưng lại rất linh hoạt. Một trong những bài toán thường gặp với danh sách liên kết là xử lý các phần tử trùng lặp.

Vấn đề: Cho một danh sách liên kết đơn (Singly Linked List). Hãy viết hàm xóa bỏ tất cả các nút (node) có giá trị trùng lặp, chỉ giữ lại duy nhất một lần xuất hiện đầu tiên của mỗi giá trị.

Ví dụ: Danh sách ban đầu: 1 -> 2 -> 3 -> 2 -> 1 -> 4 -> 3 Danh sách sau khi xóa trùng lặp: 1 -> 2 -> 3 -> 4

Tại sao sử dụng Danh sách liên kết? Đây là một bài toán trực tiếp trên cấu trúc danh sách liên kết. Thách thức ở đây là làm thế nào để duyệt qua danh sách và xóa bỏ các nút mà không làm mất đi liên kết giữa các nút còn lại.

Cách tiếp cận: Để xác định xem một giá trị đã xuất hiện trước đó hay chưa, chúng ta cần một cách để lưu trữ các giá trị đã thấy. Một Hash Set (Unordered Set trong C++) là lựa chọn tuyệt vời cho việc này vì nó cho phép kiểm tra sự tồn tại của một phần tử trong thời gian trung bình là O(1). Chúng ta sẽ duyệt qua danh sách liên kết. Với mỗi nút hiện tại, ta kiểm tra giá trị của nó trong Hash Set.

• Nếu giá trị đã có trong set, điều này có nghĩa là nó bị trùng lặp. Ta cần xóa nút hiện tại. Để xóa nút hiện tại current, ta cần nút trước đó (previous) để cập nhật con trỏ next của previous trỏ tới nút sau current. Sau đó, ta giải phóng bộ nhớ của nút current và cập nhật current tới nút tiếp theo (bằng cách dùng con trỏ tạm hoặc lấy từ previous->next). Con trỏ previous không di chuyển trong trường hợp này vì nút tiếp theo sẽ trở thành nút mới cần kiểm tra sau khi xóa.
• Nếu giá trị chưa có trong set, ta thêm nó vào set và di chuyển cả con trỏ previous lẫn current tới nút tiếp theo.

Code minh hoạ (C++):

#include <iostream>
#include <unordered_set>

// Định nghĩa cấu trúc Node cho danh sách liên kết đơn
struct Node {
    int data;
    Node* next;

    // Constructor
    Node(int val) : data(val), next(nullptr) {}
};

// Hàm để in danh sách liên kết
void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;
}

// Hàm xóa phần tử trùng lặp trong danh sách liên kết đơn
Node* removeDuplicates(Node* head) {
    if (head == nullptr) {
        return nullptr; // Danh sách rỗng
    }

    std::unordered_set<int> seen_values;
    Node* current = head;
    Node* previous = nullptr;

    while (current != nullptr) {
        // Nếu giá trị đã tồn tại trong set
        if (seen_values.count(current->data)) {
            // Xóa nút hiện tại
            // previous->next sẽ bỏ qua current và trỏ tới nút sau current
            previous->next = current->next;
            Node* node_to_delete = current;
            current = current->next; // Di chuyển current tới nút tiếp theo
            delete node_to_delete; // Giải phóng bộ nhớ
            // previous không di chuyển vì nút tiếp theo cần được kiểm tra
        } else {
            // Nếu giá trị chưa tồn tại, thêm vào set và di chuyển cả previous lẫn current
            seen_values.insert(current->data);
            previous = current;
            current = current->next;
        }
    }

    return head; // Trả về đầu danh sách (có thể đã thay đổi nếu head là phần tử trùng lặp đầu tiên)
}

// Hàm main để thử nghiệm
int main() {
    // Tạo danh sách liên kết: 1 -> 2 -> 3 -> 2 -> 1 -> 4 -> 3
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(2);
    head->next->next->next->next = new Node(1);
    head->next->next->next->next->next = new Node(4);
    head->next->next->next->next->next->next = new Node(3);

    std::cout << "Danh sach ban dau: ";
    printList(head);

    head = removeDuplicates(head);

    std::cout << "Danh sach sau khi xoa trung lap: ";
    printList(head);

    // Lưu ý: Trong thực tế, cần thêm code để giải phóng toàn bộ danh sách sau khi sử dụng.
    // Phần này chỉ để minh họa logic xóa trùng lặp.

    return 0;
}

Giải thích code:

1. Node struct: Định nghĩa cấu trúc cơ bản của một nút với data và con trỏ next.
2. printList: Hàm tiện ích để hiển thị nội dung danh sách.
3. removeDuplicates:
   • Hàm nhận con trỏ đầu danh sách (head). Xử lý trường hợp danh sách rỗng.
   • std::unordered_set<int> seen_values;: Khai báo một hash set để lưu trữ các giá trị đã xuất hiện.
   • Node* current = head;: Con trỏ current dùng để duyệt qua danh sách.
   • Node* previous = nullptr;: Con trỏ previous dùng để lưu lại nút trước current. Nó cần thiết để thay đổi liên kết khi xóa current. Bắt đầu là nullptr vì nút đầu tiên không có nút nào trước nó.
   • Vòng lặp while (current != nullptr): Duyệt cho đến hết danh sách.
   • seen_values.count(current->data): Kiểm tra xem giá trị của nút current có trong set chưa. count() trả về số lần xuất hiện (0 hoặc 1 trong set).
   • Nếu trùng lặp:
     • previous->next = current->next;: Bỏ qua nút current. Nút trước đó (previous) bây giờ trỏ đến nút sau current.
     • Node* node_to_delete = current;: Lưu lại con trỏ current để xóa sau.
     • current = current->next;: Di chuyển current tới nút tiếp theo trong danh sách (là nút mà previous->next đang trỏ tới).
     • delete node_to_delete;: Giải phóng bộ nhớ của nút bị xóa.
     • Quan trọng: previous không thay đổi. Nút mà previous đang trỏ tới vẫn giữ nguyên vị trí, và ở vòng lặp tiếp theo, nó sẽ được kết nối với nút mới mà current đang trỏ tới (hoặc tiếp tục bị bỏ qua nếu nút đó cũng trùng lặp).
   • Nếu không trùng lặp:
     • seen_values.insert(current->data);: Thêm giá trị vào set.
     • previous = current;: Cập nhật previous lên nút hiện tại (vì nút hiện tại sẽ là nút trước nút tiếp theo).
     • current = current->next;: Di chuyển current tới nút tiếp theo.
   • Hàm trả về head mới (hoặc nullptr nếu danh sách ban đầu rỗng).

Bài toán này thể hiện việc thao tác trực tiếp trên con trỏ của danh sách liên kết và cách sử dụng một cấu trúc dữ liệu phụ trợ (Hash Set) để cải thiện hiệu quả (duyệt O(N) và kiểm tra O(1) thay vì O(N^2) nếu duyệt lồng nhau).

Bài tập 2: Kiểm tra tính cân bằng của dấu ngoặc đơn

Stack là cấu trúc dữ liệu LIFO (Last-In, First-Out) và rất hữu ích trong việc xử lý các vấn đề đòi hỏi sự "quay lại" hoặc "lưu trữ tạm thời" theo thứ tự ngược. Kiểm tra tính cân bằng của dấu ngoặc là một ví dụ cổ điển.

Vấn đề: Cho một chuỗi chỉ chứa các ký tự (, ), {, }, [, ]. Hãy xác định xem chuỗi đó có phải là chuỗi dấu ngoặc cân bằng hay không. Chuỗi cân bằng là khi mỗi dấu ngoặc mở đều có một dấu ngoặc đóng tương ứng, đúng loại và đúng thứ tự.

Ví dụ:

• () - Cân bằng
• ()[]{} - Cân bằng
• ([{}]) - Cân bằng
• (] - Không cân bằng (đóng sai loại)
• ([)] - Không cân bằng (đóng sai thứ tự)
• (( - Không cân bằng (thiếu dấu đóng)
• )) - Không cân bằng (thừa dấu đóng)

Tại sao sử dụng Stack? Khi duyệt chuỗi từ trái sang phải, nếu gặp một dấu ngoặc mở, ta cần "ghi nhớ" nó để sau này kiểm tra với dấu ngoặc đóng tương ứng. Stack phù hợp vì khi gặp dấu ngoặc đóng, ta chỉ cần kiểm tra với dấu ngoặc mở gần nhất trước đó (phần tử nằm trên cùng của stack).

Cách tiếp cận: Duyệt qua chuỗi ký tự.

• Nếu gặp dấu ngoặc mở ((, {, [), đẩy (push) nó vào stack.
• Nếu gặp dấu ngoặc đóng (), }, ]), kiểm tra:
  • Stack có rỗng không? Nếu rỗng, tức là có dấu đóng mà không có dấu mở tương ứng, chuỗi không cân bằng.
  • Stack không rỗng: Lấy (pop) phần tử trên cùng của stack và kiểm tra xem nó có phải là dấu mở tương ứng với dấu đóng hiện tại không. Nếu không tương ứng, chuỗi không cân bằng.
• Sau khi duyệt hết chuỗi, nếu stack rỗng, điều này có nghĩa là tất cả các dấu mở đều có dấu đóng tương ứng. Chuỗi cân bằng. Nếu stack không rỗng, tức là còn dấu mở chưa được đóng, chuỗi không cân bằng.

Code minh hoạ (C++):

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

// Hàm kiểm tra tính cân bằng của dấu ngoặc
bool isBalanced(const std::string& s) {
    std::stack<char> st;
    // Sử dụng map để dễ dàng kiểm tra cặp ngoặc tương ứng
    std::unordered_map<char, char> bracket_map = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };

    for (char c : s) {
        // Nếu là dấu ngoặc mở, đẩy vào stack
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        }
        // Nếu là dấu ngoặc đóng
        else if (c == ')' || c == '}' || c == ']') {
            // Stack rỗng mà gặp dấu đóng -> không cân bằng
            if (st.empty()) {
                return false;
            }
            // Lấy dấu mở trên cùng stack và so sánh với dấu đóng hiện tại
            char top_char = st.top();
            st.pop();
            if (bracket_map[c] != top_char) {
                return false; // Dấu đóng không khớp với dấu mở trên cùng
            }
        }
        // Các ký tự khác (nếu có trong chuỗi đầu vào), ta bỏ qua
    }

    // Sau khi duyệt hết chuỗi, nếu stack rỗng là cân bằng, ngược lại là không
    return st.empty();
}

// Hàm main để thử nghiệm
int main() {
    std::string test_cases[] = {
        "()",
        "()[]{}",
        "([{}])",
        "(]",
        "([)]",
        "((",
        "))",
        "{[()]}",
        "" // Chuỗi rỗng
    };

    for (const std::string& tc : test_cases) {
        std::cout << "Chuoi \"" << tc << "\" is balanced: " << (isBalanced(tc) ? "True" : "False") << std::endl;
    }

    return 0;
}

Giải thích code:

1. std::stack<char> st;: Khai báo một stack để lưu trữ các ký tự dấu ngoặc mở.
2. std::unordered_map<char, char> bracket_map;: Sử dụng một map để lưu trữ ánh xạ giữa dấu ngoặc đóng và dấu ngoặc mở tương ứng. Điều này giúp việc kiểm tra sự khớp cặp trở nên gọn gàng.
3. Vòng lặp for (char c : s): Duyệt qua từng ký tự trong chuỗi đầu vào s.
4. if (c == '(' || c == '{' || c == '['): Nếu ký tự là dấu ngoặc mở, ta dùng st.push(c) để đẩy nó vào stack.
5. else if (c == ')' || c == '}' || c == ']'): Nếu ký tự là dấu ngoặc đóng:
   • if (st.empty()) return false;: Kiểm tra stack có rỗng không. Nếu rỗng, tức là gặp dấu đóng mà không có dấu mở nào trong stack chờ được đóng, nên chuỗi không cân bằng.
   • char top_char = st.top(); st.pop();: Lấy phần tử trên cùng của stack (st.top()) và sau đó xóa nó đi (st.pop()). Đây là dấu ngoặc mở gần nhất cần được khớp.
   • if (bracket_map[c] != top_char) return false;: Sử dụng map để tìm dấu mở tương ứng với dấu đóng c. Nếu dấu mở tìm được không giống với top_char vừa lấy từ stack, tức là cặp ngoặc không khớp, chuỗi không cân bằng.
6. return st.empty();: Sau khi vòng lặp kết thúc, nếu stack rỗng, nghĩa là tất cả các dấu mở đều đã tìm thấy dấu đóng tương ứng và đã bị pop khỏi stack. Chuỗi cân bằng. Nếu stack còn phần tử, tức là có dấu mở chưa được đóng, chuỗi không cân bằng.

Độ phức tạp thời gian của giải thuật này là O(N), với N là độ dài chuỗi, vì ta chỉ duyệt qua chuỗi một lần. Độ phức tạp không gian là O(N) trong trường hợp xấu nhất (ví dụ: chuỗi chỉ toàn dấu mở), vì stack có thể lưu trữ tối đa N/2 ký tự.

Bài tập 3: Duyệt cây nhị phân theo mức (Level Order Traversal)

Cây nhị phân (Binary Tree) là một cấu trúc phân cấp. Duyệt cây là thao tác cơ bản để truy cập các nút. Có nhiều cách duyệt (tiền thứ tự, trung thứ tự, hậu thứ tự) thường sử dụng đệ quy hoặc stack. Tuy nhiên, duyệt theo mức (tức là duyệt hết các nút ở mức 0, rồi mức 1, rồi mức 2,...) lại thường sử dụng Queue.

Vấn đề: Cho một cây nhị phân. Hãy thực hiện duyệt cây theo mức và trả về danh sách các giá trị của các nút được nhóm theo từng mức.

Ví dụ: Cây: 3 / \ 9 20 / \ 15 7

Kết quả duyệt theo mức: [[3], [9, 20], [15, 7]]

Tại sao sử dụng Queue? Queue là cấu trúc FIFO (First-In, First-Out). Điều này hoàn toàn phù hợp với logic duyệt theo mức: khi bạn thăm một nút, bạn muốn thăm các nút con của nó sau khi bạn đã thăm tất cả các nút ở cùng mức với nút hiện tại. Bằng cách đưa các nút con vào queue, chúng sẽ được xử lý sau tất cả các nút đã có sẵn trong queue (những nút ở cùng mức hoặc mức trước đó).

Cách tiếp cận:

1. Khởi tạo một queue và đưa nút gốc (root) vào queue.
2. Trong khi queue chưa rỗng:
   • Xác định số lượng nút hiện có trong queue. Đây chính là số lượng nút ở mức hiện tại.
   • Tạo một danh sách (hoặc vector) để lưu trữ giá trị của các nút ở mức hiện tại.
   • Lặp lại số lần bằng số lượng nút ở mức hiện tại:
     • Lấy nút ở đầu queue (dequeue).
     • Thêm giá trị của nút đó vào danh sách của mức hiện tại.
     • Nếu nút có con trái, đưa con trái vào queue (enqueue).
     • Nếu nút có con phải, đưa con phải vào queue (enqueue).
   • Thêm danh sách của mức hiện tại vào kết quả cuối cùng.
3. Kết thúc vòng lặp khi queue rỗng. Trả về kết quả.

Code minh hoạ (C++):

#include <iostream>
#include <vector>
#include <queue>
#include <vector> // Đã include ở trên nhưng không sao

// Định nghĩa cấu trúc Node cho cây nhị phân
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// Hàm duyệt cây nhị phân theo mức
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result; // Lưu trữ kết quả theo từng mức
    if (root == nullptr) {
        return result; // Cây rỗng
    }

    std::queue<TreeNode*> q;
    q.push(root); // Đưa nút gốc vào queue

    while (!q.empty()) {
        int level_size = q.size(); // Số lượng nút ở mức hiện tại
        std::vector<int> current_level_nodes; // Lưu trữ giá trị nút ở mức này

        // Duyệt qua tất cả các nút ở mức hiện tại
        for (int i = 0; i < level_size; ++i) {
            TreeNode* current_node = q.front();
            q.pop();

            current_level_nodes.push_back(current_node->val); // Thêm giá trị vào danh sách mức hiện tại

            // Đưa con trái và con phải (nếu tồn tại) vào queue cho mức tiếp theo
            if (current_node->left != nullptr) {
                q.push(current_node->left);
            }
            if (current_node->right != nullptr) {
                q.push(current_node->right);
            }
        }
        // Sau khi xử lý hết các nút ở mức hiện tại, thêm danh sách này vào kết quả
        result.push_back(current_level_nodes);
    }

    return result;
}

// Hàm main để thử nghiệm
int main() {
    // Xây dựng cây ví dụ:
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    std::vector<std::vector<int>> levels = levelOrder(root);

    std::cout << "Duyet cay theo muc:" << std::endl;
    for (const auto& level : levels) {
        std::cout << "[ ";
        for (int val : level) {
            std::cout << val << " ";
        }
        std::cout << "]" << std::endl;
    }

    // Lưu ý: Cần giải phóng bộ nhớ cho cây đã tạo.
    // (Để đơn giản, phần giải phóng bộ nhớ không được hiển thị ở đây)

    return 0;
}

Giải thích code:

1. TreeNode struct: Định nghĩa cấu trúc cơ bản của một nút trong cây nhị phân.
2. levelOrder:
   • std::vector<std::vector<int>> result;: Vector chứa các vector, mỗi vector con đại diện cho một mức của cây và chứa giá trị các nút ở mức đó.
   • Xử lý trường hợp cây rỗng.
   • std::queue<TreeNode*> q;: Khai báo một queue để lưu trữ các con trỏ tới các nút cần thăm.
   • q.push(root);: Đưa nút gốc vào queue để bắt đầu quá trình duyệt.
   • Vòng lặp while (!q.empty()): Tiếp tục cho đến khi không còn nút nào trong queue.
   • int level_size = q.size();: Lấy kích thước hiện tại của queue. Đây chính là số lượng nút ở mức mà chúng ta chuẩn bị xử lý trong vòng lặp for tiếp theo. Điều này rất quan trọng để phân biệt các mức.
   • std::vector<int> current_level_nodes;: Tạo một vector tạm để lưu trữ giá trị của các nút ở mức hiện tại.
   • Vòng lặp for (int i = 0; i < level_size; ++i): Lặp đúng level_size lần để xử lý chỉ các nút mà ban đầu nằm trong queue ở mức này.
   • TreeNode* current_node = q.front(); q.pop();: Lấy nút đầu tiên ra khỏi queue (đã được thêm vào từ mức trước).
   • current_level_nodes.push_back(current_node->val);: Thêm giá trị của nút vừa lấy ra vào vector của mức hiện tại.
   • if (current_node->left != nullptr) q.push(current_node->left);: Nếu nút hiện tại có con trái, thêm con trái vào cuối queue. Nó sẽ được xử lý ở mức tiếp theo.
   • if (current_node->right != nullptr) q.push(current_node->right);: Tương tự với con phải.
   • result.push_back(current_level_nodes);: Sau khi vòng lặp for kết thúc (tức là đã xử lý hết các nút ở mức hiện tại), thêm vector current_level_nodes vào kết quả cuối cùng.
   • Vòng lặp while tiếp tục với các nút mới được thêm vào queue, tạo thành mức tiếp theo.
   • Hàm trả về result.

Giải thuật duyệt theo mức có độ phức tạp thời gian O(N), với N là số lượng nút trong cây, vì mỗi nút được thăm đúng một lần. Độ phức tạp không gian là O(W), với W là chiều rộng lớn nhất của cây (số nút tối đa ở cùng một mức), vì queue có thể chứa tối đa số nút ở mức rộng nhất. Trong trường hợp cây hoàn chỉnh (complete binary tree), W có thể là O(N).

Bài tập 4: Kiểm tra xem một cây nhị phân có phải là Cây tìm kiếm nhị phân hợp lệ không

Cây tìm kiếm nhị phân (Binary Search Tree - BST) có các thuộc tính rất đặc trưng: với mỗi nút, tất cả các giá trị trong cây con bên trái của nó đều nhỏ hơn giá trị của nút đó, và tất cả các giá trị trong cây con bên phải của nó đều lớn hơn giá trị của nút đó. Quan trọng là thuộc tính này phải đúng cho tất cả các nút con trong cây con.

Vấn đề: Cho một cây nhị phân. Hãy xác định xem nó có phải là một Cây tìm kiếm nhị phân (BST) hợp lệ hay không.

Tại sao lại cần một phương pháp kiểm tra đặc biệt? Việc chỉ kiểm tra node->left->val < node->val và node->right->val > node->val cho từng nút là không đủ. Ví dụ, trong cây sau: 10 / \ 5 15 / \ 6 20 Nút 10 thỏa mãn (5<10, 15>10). Nút 15 cũng thỏa mãn (6<15, 20>15). Nhưng cây này không phải là BST hợp lệ vì giá trị 6 nằm trong cây con bên phải của 10, nhưng lại nhỏ hơn 10.

Cách tiếp cận: Để kiểm tra thuộc tính BST đúng cho toàn bộ cây con, chúng ta có thể sử dụng kỹ thuật đệ quy kết hợp việc truyền các giới hạn (min/max) cho giá trị của nút hiện tại.

1. Viết một hàm đệ quy helper nhận vào con trỏ tới nút hiện tại, giới hạn dưới (min_val) và giới hạn trên (max_val) cho giá trị của nút này.
2. Trường hợp cơ sở: Nếu nút hiện tại là nullptr, đây là một cây con rỗng, luôn được coi là BST hợp lệ. Trả về true.
3. Kiểm tra giá trị của nút hiện tại: Nếu node->val <= min_val hoặc node->val >= max_val, thì nút này vi phạm giới hạn được truyền xuống từ các nút tổ tiên, nên cây không phải là BST hợp lệ. Trả về false.
4. Gọi đệ quy cho cây con bên trái: Kiểm tra xem cây con bên trái có phải là BST hợp lệ không, với giới hạn mới: giá trị của các nút trong cây con trái phải nằm trong khoảng (min_val, node->val).
5. Gọi đệ quy cho cây con bên phải: Kiểm tra xem cây con bên phải có phải là BST hợp lệ không, với giới hạn mới: giá trị của các nút trong cây con phải phải nằm trong khoảng (node->val, max_val).
6. Nếu cả hai lời gọi đệ quy cho cây con trái và cây con phải đều trả về true, thì cây con gốc nút hiện tại là BST hợp lệ trong giới hạn cho phép. Trả về true.

Khi gọi hàm helper lần đầu tiên cho nút gốc, ta dùng giới hạn rất rộng, ví dụ (-infinity, +infinity). Cần sử dụng kiểu dữ liệu lớn hơn int (ví dụ: long long) cho giới hạn để tránh tràn số khi cây chứa giá trị bằng INT_MIN hoặc INT_MAX.

Code minh hoạ (C++):

#include <iostream>
#include <limits> // For LLONG_MIN, LLONG_MAX

// Định nghĩa cấu trúc Node cho cây nhị phân (BST)
// Có thể tái sử dụng TreeNode struct từ bài trước, nhưng định nghĩa lại cho rõ ràng
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// Hàm helper đệ quy để kiểm tra BST với giới hạn min/max
bool isValidBSTHelper(TreeNode* node, long long min_val, long long max_val) {
    // Trường hợp cơ sở: Cây con rỗng là BST hợp lệ
    if (node == nullptr) {
        return true;
    }

    // Kiểm tra giá trị của nút hiện tại có nằm trong giới hạn cho phép không
    if (node->val <= min_val || node->val >= max_val) {
        return false; // Vi phạm thuộc tính BST
    }

    // Kiểm tra đệ quy cây con trái: giá trị phải nhỏ hơn node->val, giới hạn dưới không đổi
    // Kiểm tra đệ quy cây con phải: giá trị phải lớn hơn node->val, giới hạn trên không đổi
    return isValidBSTHelper(node->left, min_val, node->val) &&
           isValidBSTHelper(node->right, node->val, max_val);
}

// Hàm chính để kiểm tra BST
bool isValidBST(TreeNode* root) {
    // Bắt đầu kiểm tra từ gốc với giới hạn ban đầu rất rộng
    return isValidBSTHelper(root, std::numeric_limits<long long>::min(), std::numeric_limits<long long>::max());
}

// Hàm main để thử nghiệm
int main() {
    // Cây là BST hợp lệ:
    //       2
    //      / \
    //     1   3
    TreeNode* root1 = new TreeNode(2);
    root1->left = new TreeNode(1);
    root1->right = new TreeNode(3);
    std::cout << "Cay 1 la BST hop le: " << (isValidBST(root1) ? "True" : "False") << std::endl; // Expected: True

    // Cây không phải là BST hợp lệ (ví dụ từ giải thích):
    //       10
    //      /  \
    //     5    15
    //         /  \
    //        6    20
    TreeNode* root2 = new TreeNode(10);
    root2->left = new TreeNode(5);
    root2->right = new TreeNode(15);
    root2->right->left = new TreeNode(6); // 6 < 10 but in right subtree
    root2->right->right = new TreeNode(20);
    std::cout << "Cay 2 la BST hop le: " << (isValidBST(root2) ? "True" : "False") << std::endl; // Expected: False

     // Cây là BST hợp lệ với giá trị MIN/MAX (sử dụng long long cho giới hạn)
     //       0
     //      / \
     // LL_MIN   LL_MAX (giả định TreeNode có thể lưu trữ LL_MIN/MAX, nhưng đây là INT)
     // Chúng ta sẽ dùng INT_MIN+1 và INT_MAX-1 để minh họa
     TreeNode* root3 = new TreeNode(0);
     root3->left = new TreeNode(std::numeric_limits<int>::min() + 1);
     root3->right = new TreeNode(std::numeric_limits<int>::max() - 1);
     std::cout << "Cay 3 la BST hop le: " << (isValidBST(root3) ? "True" : "False") << std::endl; // Expected: True

    // Cây không hợp lệ do giá trị trùng lặp
    //       2
    //      / \
    //     2   3
    TreeNode* root4 = new TreeNode(2);
    root4->left = new TreeNode(2);
    root4->right = new TreeNode(3);
    std::cout << "Cay 4 la BST hop le: " << (isValidBST(root4) ? "True" : "False") << std::endl; // Expected: False (vì BST thường không cho phép giá trị trùng lặp ở cây con trái <= root)

    // Lưu ý: Cần giải phóng bộ nhớ cho các cây đã tạo.

    return 0;
}

Giải thích code:

1. TreeNode struct: Cấu trúc cơ bản của một nút cây.
2. isValidBSTHelper(TreeNode* node, long long min_val, long long max_val):
   • Đây là hàm đệ quy chính thực hiện việc kiểm tra. Nó nhận nút hiện tại (node) và hai giá trị min_val và max_val đại diện cho khoảng giá trị hợp lệ mà node->val phải nằm trong để BST vẫn giữ tính chất từ nút gốc ban đầu đến các nút tổ tiên của node.
   • Base case: if (node == nullptr) return true; - Nếu đến một nút rỗng, điều đó không vi phạm tính chất BST, nên trả về true.
   • Check current node: if (node->val <= min_val || node->val >= max_val) return false; - Đây là kiểm tra cốt lõi. Giá trị của nút hiện tại phải lớn hơn giới hạn dưới và nhỏ hơn giới hạn trên. Lưu ý sử dụng < và > thay vì <= và >=. Quy tắc nghiêm ngặt cho BST thường là cây con trái nhỏ hơn, cây con phải lớn hơn (không bao gồm bằng). Nếu đề bài cho phép bằng, bạn sẽ cần điều chỉnh logic kiểm tra và giới hạn truyền xuống.
   • Recursive calls:
     • isValidBSTHelper(node->left, min_val, node->val): Khi đi sang cây con bên trái, giới hạn trên mới là node->val. Bất kỳ nút nào trong cây con trái đều phải nhỏ hơn giá trị của nút hiện tại. Giới hạn dưới min_val vẫn giữ nguyên vì giá trị trong cây con trái vẫn phải lớn hơn giới hạn dưới được kế thừa từ các nút tổ tiên.
     • isValidBSTHelper(node->right, node->val, max_val): Khi đi sang cây con bên phải, giới hạn dưới mới là node->val. Bất kỳ nút nào trong cây con phải đều phải lớn hơn giá trị của nút hiện tại. Giới hạn trên max_val vẫn giữ nguyên.
   • return ... && ...;: Cây con gốc node chỉ là BST hợp lệ nếu cả cây con trái và cây con phải đều là BST hợp lệ trong các giới hạn tương ứng của chúng.
3. isValidBST(TreeNode* root): Hàm này chỉ là một lớp bọc (wrapper function). Nó gọi isValidBSTHelper ban đầu với nút gốc và giới hạn ban đầu là toàn bộ phạm vi giá trị có thể của long long (LLONG_MIN, LLONG_MAX) để đảm bảo không có giới hạn nào bị vi phạm ngay từ đầu.

Cách tiếp cận đệ quy với việc truyền giới hạn này có độ phức tạp thời gian O(N), với N là số nút, vì mỗi nút được thăm đúng một lần. Độ phức tạp không gian là O(H), với H là chiều cao của cây, do đệ quy stack. Trong trường hợp cây bị lệch hoàn toàn, H có thể là O(N).

Bài tập 5: Đếm tần suất xuất hiện của các phần tử trong mảng

Hash Table (hay Hash Map, Unordered Map trong C++) là cấu trúc dữ liệu dựa trên bảng băm, cung cấp khả năng truy cập, thêm, xóa dữ liệu với thời gian trung bình O(1). Nó cực kỳ hiệu quả cho các bài toán cần lưu trữ và tìm kiếm dữ liệu theo cặp khóa-giá trị.

Vấn đề: Cho một mảng các số nguyên. Hãy đếm số lần xuất hiện của mỗi số trong mảng.

Ví dụ: Mảng: [1, 2, 3, 2, 1, 4, 3, 5, 3] Kết quả (thứ tự không quan trọng): 1: 2 lần 2: 2 lần 3: 3 lần 4: 1 lần 5: 1 lần

Tại sao sử dụng Hash Table (Unordered Map)? Chúng ta cần lưu trữ số lần đếm (giá trị) cho mỗi số duy nhất trong mảng (khóa). Hash Map cung cấp một cách hiệu quả để ánh xạ các số duy nhất thành số lần xuất hiện của chúng. Việc tra cứu và cập nhật số đếm cho mỗi số được thực hiện rất nhanh.

Cách tiếp cận:

1. Khởi tạo một Hash Map rỗng, trong đó khóa là kiểu dữ liệu của các phần tử trong mảng (ví dụ: int) và giá trị là kiểu dữ liệu để lưu số đếm (ví dụ: int).
2. Duyệt qua từng phần tử trong mảng đầu vào.
3. Đối với mỗi phần tử:
   • Sử dụng phần tử đó làm khóa để truy cập vào map.
   • Tăng giá trị (số đếm) tương ứng với khóa đó lên 1. Nếu khóa chưa tồn tại trong map, nó sẽ được thêm vào với giá trị mặc định (0 cho kiểu int), sau đó tăng lên 1.
4. Sau khi duyệt hết mảng, Hash Map sẽ chứa số lần xuất hiện của mỗi phần tử duy nhất.
5. Duyệt qua Hash Map và in ra kết quả.

Code minh hoạ (C++):

#include <iostream>
#include <vector>
#include <unordered_map> // For Hash Map

// Hàm đếm tần suất xuất hiện các phần tử trong mảng
void countFrequencies(const std::vector<int>& arr) {
    // Khai báo unordered_map: key là giá trị phần tử, value là số lần xuất hiện
    std::unordered_map<int, int> frequency_map;

    // Duyệt qua mảng và đếm tần suất
    for (int element : arr) {
        frequency_map[element]++; // Nếu element chưa có, nó được thêm với giá trị 0 rồi tăng lên 1. Nếu có, tăng giá trị hiện tại lên 1.
    }

    // In kết quả
    std::cout << "Tan suat xuat hien cua cac phan tu:" << std::endl;
    for (const auto& pair : frequency_map) {
        std::cout << pair.first << ": " << pair.second << " lan" << std::endl;
    }
}

// Hàm main để thử nghiệm
int main() {
    std::vector<int> my_array = {1, 2, 3, 2, 1, 4, 3, 5, 3};

    countFrequencies(my_array);

    return 0;
}

Giải thích code:

1. std::unordered_map<int, int> frequency_map;: Khai báo một unordered_map trong thư viện <unordered_map>. Kiểu khóa là int (các số trong mảng), kiểu giá trị là int (số lần đếm). unordered_map là cài đặt của Hash Table trong C++.
2. for (int element : arr): Vòng lặp range-based for để duyệt qua từng element trong vector arr.
3. frequency_map[element]++;: Đây là dòng code cốt lõi.
   • Khi bạn truy cập frequency_map[element], Hash Map sẽ dùng giá trị của element để tính toán vị trí băm.
   • Nếu element chưa tồn tại như một khóa trong map, một cặp khóa-giá trị mới sẽ được tạo ra với khóa là element và giá trị mặc định cho kiểu int, là 0. Sau đó, toán tử ++ sẽ tăng giá trị này lên 1.
   • Nếu element đã tồn tại, toán tử [] sẽ trả về tham chiếu tới giá trị hiện tại của khóa đó, và toán tử ++ sẽ tăng giá trị đó lên 1.
4. Vòng lặp for (const auto& pair : frequency_map): Duyệt qua tất cả các cặp khóa-giá trị (pair) trong frequency_map. pair.first là khóa (phần tử), pair.second là giá trị (số lần đếm).
5. In kết quả ra console.

Giải thuật này có độ phức tạp thời gian trung bình là O(N), với N là số phần tử trong mảng, vì mỗi phần tử được xử lý một lần và thao tác trên Hash Map (chèn/cập nhật) mất thời gian trung bình O(1). Độ phức tạp không gian trung bình là O(U), với U là số lượng các phần tử duy nhất trong mảng, vì Hash Map lưu trữ một mục nhập cho mỗi phần tử duy nhất. Trong trường hợp xấu nhất (tất cả phần tử đều duy nhất), không gian có thể là O(N).

Bài tập ví dụ:

Quái Vật Sát Thủ

Trong một buổi huấn luyện chiến đấu, FullHouse Dev được giao nhiệm vụ mô phỏng một chiến trường với các quái vật. Họ cần theo dõi số lượng quái vật còn sống sót sau mỗi phút khi các quái vật mới xuất hiện và tấn công những quái vật yếu hơn.

Bài toán

Cho một mảng \(a\) chứa sức mạnh của \(n\) quái vật. Ban đầu chiến trường trống, mỗi phút \(i\), quái vật thứ \(i\) sẽ xuất hiện và tiêu diệt tất cả quái vật có sức mạnh nhỏ hơn hoặc bằng sức mạnh của nó. Nhiệm vụ của nhóm là xác định số lượng quái vật còn sống sau mỗi phút.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Với mỗi test case:
  • Dòng đầu chứa số nguyên \(n\) - số lượng quái vật
  • Dòng tiếp theo chứa \(n\) số nguyên - sức mạnh của từng quái vật

OUTPUT FORMAT:

• Với mỗi test case, in ra \(n\) số nguyên thể hiện số lượng quái vật còn sống sau mỗi phút

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq a[i] \leq 10^9\)

Ví dụ:

INPUT

3
5
3 0 3 4 1
5
5 4 3 2 1
7
1 2 3 3 4 4 0

OUTPUT

1 2 1 1 2
1 2 3 4 5
1 1 1 1 1 1 2

Giải thích:

Với test case đầu tiên:

• Phút 1: Quái vật sức mạnh 3 xuất hiện → còn 1 quái vật
• Phút 2: Quái vật sức mạnh 0 xuất hiện → còn 2 quái vật (không ai bị tiêu diệt)
• Phút 3: Quái vật sức mạnh 3 xuất hiện, tiêu diệt quái vật sức mạnh 0 → còn 1 quái vật
• Phút 4: Quái vật sức mạnh 4 xuất hiện, tiêu diệt quái vật sức mạnh 3 → còn 1 quái vật
• Phút 5: Quái vật sức mạnh 1 xuất hiện → còn 2 quái vật (không ai bị tiêu diệt) Chào bạn, đây là hướng dẫn giải bài "Quái Vật Sát Thủ" bằng C++ một cách ngắn gọn, tập trung vào ý tưởng và cấu trúc dữ liệu phù hợp, không cung cấp code hoàn chỉnh.

Phân tích bài toán:

Bài toán yêu cầu theo dõi một tập hợp các quái vật còn sống. Mỗi phút, một quái vật mới xuất hiện và tiêu diệt các quái vật đang tồn tại có sức mạnh nhỏ hơn hoặc bằng sức mạnh của nó. Sau khi tiêu diệt, quái vật mới cũng tham gia vào tập hợp những con sống sót. Chúng ta cần biết số lượng quái vật còn sống sau mỗi phút.

Điểm mấu chốt là tập hợp quái vật sống sót thay đổi liên tục: thêm mới và xóa bỏ dựa trên sức mạnh. Số lượng quái vật có thể lên tới 10^5, sức mạnh có thể lên tới 10^9. Điều này gợi ý cần một cấu trúc dữ liệu hiệu quả cho các thao tác:

1. Thêm mới: Thêm sức mạnh của quái vật mới.
2. Tìm kiếm/Xóa theo điều kiện: Tìm và xóa tất cả các quái vật có sức mạnh <= một giá trị cho trước.
3. Đếm: Lấy số lượng phần tử hiện có.

Các thao tác này cần được thực hiện nhanh chóng để tránh quá tải khi N lớn. Duyệt qua toàn bộ danh sách quái vật sống mỗi phút (O(N^2) tổng cộng) sẽ không đáp ứng được ràng buộc thời gian.

Hướng giải:

Cấu trúc dữ liệu lý tưởng cho bài toán này là một cấu trúc có khả năng tự sắp xếp và cho phép tìm kiếm, thêm, xóa hiệu quả. std::multiset trong C++ là một lựa chọn phù hợp.

• std::multiset lưu trữ các phần tử (sức mạnh quái vật) theo thứ tự tăng dần và cho phép lưu trữ các phần tử trùng lặp.
• Nó hỗ trợ thêm phần tử (O(log K)), xóa phần tử (O(log K) cho một lần xóa), và tìm kiếm (O(log K)), trong đó K là số lượng phần vật trong set.
• Quan trọng nhất, nó cho phép tìm kiếm hiệu quả các phần tử trong một phạm vi (ví dụ: tất cả các phần tử <= một giá trị) và xóa một phạm vi các phần tử một cách tương đối hiệu quả.

Các bước thực hiện với std::multiset:

1. Khởi tạo một std::multiset rỗng để đại diện cho chiến trường (chứa sức mạnh của các quái vật đang sống).
2. Duyệt qua danh sách sức mạnh của n quái vật theo thứ tự từ phút 1 đến phút n.
3. Tại phút thứ i (với sức mạnh a[i-1] nếu dùng mảng 0-indexed):
   • Quái vật có sức mạnh a[i-1] xuất hiện.
   • Nó sẽ tiêu diệt tất cả quái vật đang sống có sức mạnh nhỏ hơn hoặc bằng a[i-1].
   • Trong multiset, các quái vật cần bị tiêu diệt là những quái vật có sức mạnh từ phần tử nhỏ nhất trong set đến phần tử có giá trị a[i-1].
   • Sử dụng hàm upper_bound(a[i-1]) của multiset để tìm iterator trỏ đến phần tử đầu tiên lớn hơn a[i-1].
   • Tất cả các phần tử từ multiset.begin() đến (nhưng không bao gồm) iterator trả về bởi upper_bound chính là những quái vật bị tiêu diệt.
   • Sử dụng hàm erase(begin_iterator, end_iterator) để xóa phạm vi các quái vật này khỏi multiset.
   • Sau khi tiêu diệt, quái vật mới (sức mạnh a[i-1]) tham gia vào chiến trường. Chèn sức mạnh a[i-1] vào multiset bằng hàm insert.
   • Số lượng quái vật còn sống sau phút i chính là kích thước hiện tại của multiset (multiset.size()). Ghi lại giá trị này.
4. Sau khi xử lý hết n phút, in ra n giá trị đã ghi lại.

Độ phức tạp:

• Mỗi lần chèn vào multiset mất O(log K), với K là số lượng phần tử hiện tại (tối đa là N).
• Tìm upper_bound mất O(log K).
• Xóa một phạm vi trong multiset (erase(begin, end)) có độ phức tạp trung bình khoảng O(M + log K), trong đó M là số lượng phần tử bị xóa.
• Tổng cộng qua N bước, mỗi quái vật được chèn 1 lần (N * O(log N)), và bị xóa tối đa 1 lần. Tổng số phần tử bị xóa trong tất cả các bước là tối đa N. Do đó, độ phức tạp tổng thể cho mỗi test case là khoảng O(N log N), phù hợp với ràng buộc N=10^5.

Lưu ý: Cần bao gồm các header cần thiết như <iostream>, <vector>, <set>, <algorithm>. Đừng quên xử lý nhiều test case theo định dạng input.

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