Bài 24.4: Bài tập thực hành mảng 1 chiều nâng cao trong C++

Chào mừng các bạn quay trở lại với chuỗi bài học về C++! Chúng ta đã cùng nhau đi qua những kiến thức cơ bản về mảng một chiều trong các bài trước. Mảng là một cấu trúc dữ liệu vô cùng quan trọng và được sử dụng rộng rãi trong lập trình. Nắm vững cách làm việc với mảng không chỉ giúp bạn giải quyết được nhiều bài toán thực tế mà còn là nền tảng để tiếp cận với các cấu trúc dữ liệu phức tạp hơn.

Ở bài học này, chúng ta sẽ không đi sâu vào lý thuyết nữa mà sẽ tập trung vào thực hành. Thông qua việc giải quyết các bài tập nâng cao hơn, chúng ta sẽ củng cố lại kiến thức, học hỏi thêm các kỹ thuật xử lý mảng hiệu quả và rèn luyện tư duy giải quyết vấn đề. Hãy cùng bắt tay vào thực hành thôi nào!

Chúng ta sẽ xem xét một số dạng bài tập thường gặp liên quan đến mảng một chiều, từ những bài yêu cầu xử lý dữ liệu phức tạp hơn đến những bài cần thuật toán đặc thù.

Bài Tập 1: Tìm Phần Tử Xuất Hiện Nhiều Nhất Trong Mảng

Yêu cầu: Cho một mảng các số nguyên, hãy tìm phần tử xuất hiện với tần suất cao nhất.

Phân tích: Bài toán này yêu cầu chúng ta đếm số lần xuất hiện của mỗi phần tử trong mảng và sau đó tìm phần tử nào có số lần đếm cao nhất. Cách tiếp cận đơn giản nhất là sử dụng một cấu trúc dữ liệu phụ để lưu trữ tần suất, chẳng hạn như map hoặc unordered_map trong C++.

Ý tưởng:

Duyệt qua toàn bộ mảng.
Với mỗi phần tử, tăng bộ đếm tương ứng trong map. Nếu phần tử chưa có trong map, thêm mới với bộ đếm là 1.
Sau khi đếm xong, duyệt qua map để tìm cặp (phần tử, tần suất) có tần suất lớn nhất.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <map>      // Sử dụng map để đếm tần suất
#include <algorithm> // Để dùng max (không bắt buộc ở đây nhưng hữu ích)

int main() {
    vector<int> arr = {1, 2, 2, 3, 1, 4, 2, 1, 5, 1, 2};

    map<int, int> counts; // Map lưu trữ {phần tử : số lần xuất hiện}

    // Bước 1 & 2: Đếm tần suất xuất hiện của từng phần tử
    for (int x : arr) {
        counts[x]++; // Nếu x chưa có trong map, nó sẽ được thêm vào với giá trị 0, sau đó tăng lên 1. Nếu có rồi thì chỉ tăng giá trị.
    }

    // Bước 3: Tìm phần tử có tần suất cao nhất
    int mostFrequentElement = -1; // Giả sử phần tử không âm. Có thể khởi tạo bằng phần tử đầu tiên của map.
    int maxCount = 0;

    // Duyệt qua map để tìm tần suất lớn nhất
    for (auto const& [element, count] : counts) { // Sử dụng structured binding (C++17 trở lên) cho code gọn hơn
        if (count > maxCount) {
            maxCount = count;
            mostFrequentElement = element;
        }
    }

    cout << "Mang ban dau: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << "\n";

    if (maxCount > 0) {
        cout << "Phan tu xuat hien nhieu nhat: " << mostFrequentElement << " (xuất hiện " << maxCount << " lần)\n";
    } else {
        cout << "Mang rong hoac khong co phan tu nao.\n";
    }


    return 0;
}

Giải thích mã nguồn:

Chúng ta sử dụng vector<int> arr để lưu trữ mảng đầu vào.
map<int, int> counts được khai báo để lưu trữ tần suất. Khóa (int) là giá trị của phần tử trong mảng, và giá trị (int) là số lần nó xuất hiện. map tự động sắp xếp khóa, nếu không cần sắp xếp và muốn hiệu suất tốt hơn, bạn có thể dùng unordered_map.
Vòng lặp for (int x : arr) duyệt qua từng phần tử x trong mảng. counts[x]++ là thao tác chính: nó truy cập vào map với khóa là x. Nếu khóa x chưa tồn tại, map sẽ tự động tạo một mục nhập mới với khóa x và giá trị mặc định của int (là 0), sau đó tăng giá trị đó lên 1. Nếu khóa x đã tồn tại, nó chỉ đơn giản là tăng giá trị hiện tại lên 1.
Sau khi đếm xong, chúng ta duyệt qua map bằng vòng lặp for (auto const& [element, count] : counts). Đây là cách duyệt map hiệu quả và cú pháp structured binding ([element, count]) giúp truy cập trực tiếp khóa và giá trị của mỗi cặp trong map.
Chúng ta duy trì hai biến maxCount để lưu tần suất cao nhất tìm được cho đến hiện tại và mostFrequentElement để lưu phần tử tương ứng. Nếu tần suất của phần tử hiện tại (count) lớn hơn maxCount, chúng ta cập nhật cả hai biến.
Cuối cùng, in ra kết quả.

Bài Tập 2: Xoay Vòng Mảng (Rotate Array)

Yêu cầu: Cho một mảng và một số nguyên k không âm, xoay vòng mảng sang phải k bước. Xoay vòng sang phải nghĩa là phần tử cuối cùng chuyển thành phần tử đầu tiên, phần tử kế cuối chuyển thành phần tử thứ hai, v.v. lặp lại k lần.

Ví dụ: Mảng [1, 2, 3, 4, 5, 6, 7], k = 3. Xoay 1 bước: [7, 1, 2, 3, 4, 5, 6] Xoay 2 bước: [6, 7, 1, 2, 3, 4, 5] Xoay 3 bước: [5, 6, 7, 1, 2, 3, 4]

Phân tích: Có nhiều cách để xoay mảng. Cách đơn giản nhất là lặp lại thao tác "đưa phần tử cuối lên đầu" k lần, nhưng cách này không hiệu quả với mảng lớn và k lớn. Một cách hiệu quả hơn là sử dụng một mảng tạm hoặc áp dụng kỹ thuật đảo ngược (reversal). Chúng ta sẽ sử dụng kỹ thuật đảo ngược vì nó in-place (không cần thêm bộ nhớ đáng kể) và hiệu quả về thời gian O(N).

Ý tưởng (kỹ thuật đảo ngược):

Xử lý trường hợp k lớn hơn kích thước mảng: k = k % n (với n là kích thước mảng).
Đảo ngược toàn bộ mảng.
Đảo ngược k phần tử đầu tiên.
Đảo ngược n - k phần tử còn lại.

Ví dụ minh họa kỹ thuật đảo ngược: Mảng [1, 2, 3, 4, 5, 6, 7], n=7, k=3.

k = 3 % 7 = 3.
Đảo ngược toàn bộ: [7, 6, 5, 4, 3, 2, 1]
Đảo ngược 3 phần tử đầu tiên: [5, 6, 7, 4, 3, 2, 1] (Đảo ngược [7, 6, 5] thành [5, 6, 7])
Đảo ngược 7 - 3 = 4 phần tử còn lại: [5, 6, 7, 1, 2, 3, 4] (Đảo ngược [4, 3, 2, 1] thành [1, 2, 3, 4]) Kết quả cuối cùng là mảng đã xoay đúng.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <algorithm> // Sử dụng reverse

void rotateRight(vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0 || k <= 0) return; // Xử lý trường hợp mảng rỗng hoặc k không hợp lệ

    k = k % n; // Xử lý trường hợp k lớn hơn kích thước mảng

    // Bước 2: Đảo ngược toàn bộ mảng
    reverse(arr.begin(), arr.end());

    // Bước 3: Đảo ngược k phần tử đầu tiên
    reverse(arr.begin(), arr.begin() + k);

    // Bước 4: Đảo ngược n - k phần tử còn lại
    reverse(arr.begin() + k, arr.end());
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7};
    int k = 3;

    cout << "Mang truoc khi xoay: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << "\n";

    rotateRight(arr, k);

    cout << "Mang sau khi xoay phai " << k << " buoc: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << "\n";

    vector<int> arr2 = { -1, -100, 3, 99 };
    int k2 = 2;

    cout << "Mang truoc khi xoay: ";
    for (int x : arr2) {
        cout << x << " ";
    }
    cout << "\n";

    rotateRight(arr2, k2);

    cout << "Mang sau khi xoay phai " << k2 << " buoc: ";
    for (int x : arr2) {
        cout << x << " ";
    }
    cout << "\n";


    return 0;
}

Giải thích mã nguồn:

Hàm rotateRight nhận vào một tham chiếu đến vector<int> (arr) và số bước xoay k. Sử dụng tham chiếu (&) giúp chúng ta sửa đổi trực tiếp mảng ban đầu.
int n = arr.size(); lấy kích thước của mảng.
Kiểm tra mảng rỗng hoặc k <= 0 để tránh lỗi và xử lý các trường hợp không cần xoay.
k = k % n; đảm bảo rằng k luôn nằm trong phạm vi từ 0 đến n-1. Ví dụ, xoay 7 bước một mảng 7 phần tử cũng giống như không xoay (k=0).
Chúng ta sử dụng hàm reverse từ thư viện <algorithm>. Hàm này nhận hai iterator chỉ định phạm vi cần đảo ngược (arr.begin(), arr.end() là toàn bộ mảng; arr.begin(), arr.begin() + k là từ đầu đến vị trí k-1).
Các bước đảo ngược được thực hiện đúng như ý tưởng đã phân tích.
Trong main, chúng ta tạo mảng, in ra trước khi xoay, gọi hàm rotateRight, và in ra mảng sau khi xoay để kiểm tra kết quả.

Bài Tập 3: Tách Chẵn Lẻ trong Mảng

Yêu cầu: Sắp xếp lại mảng sao cho tất cả các số chẵn nằm ở phía trước và tất cả các số lẻ nằm ở phía sau. Thứ tự tương đối của các số chẵn với nhau hoặc các số lẻ với nhau không quan trọng.

Ví dụ: Mảng [3, 1, 4, 1, 5, 9, 2, 6] có thể trở thành [4, 2, 6, 3, 1, 5, 9, 1].

Phân tích: Bài toán này là một biến thể của bài toán phân hoạch (partitioning), giống như bước phân hoạch trong thuật toán QuickSort. Chúng ta có thể sử dụng kỹ thuật hai con trỏ.

Ý tưởng:

Sử dụng hai con trỏ, left bắt đầu từ đầu mảng (index 0) và right bắt đầu từ cuối mảng (index n-1).
Di chuyển con trỏ left về phía trước cho đến khi gặp một số lẻ (vì số lẻ thuộc về phía bên phải).
Di chuyển con trỏ right về phía sau cho đến khi gặp một số chẵn (vì số chẵn thuộc về phía bên trái).
Nếu left vẫn nhỏ hơn right, điều đó có nghĩa là chúng ta đã tìm thấy một cặp phần tử bị sai vị trí (số lẻ ở bên trái, số chẵn ở bên phải). Hoán đổi vị trí của chúng.
Sau khi hoán đổi, tăng left và giảm right để tiếp tục tìm kiếm.
Lặp lại bước 2-5 cho đến khi left >= right.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <algorithm> // Sử dụng swap

void separateEvenOdd(vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        // Di chuyển 'left' cho đến khi gặp số lẻ
        while (left < right && arr[left] % 2 == 0) {
            left++;
        }

        // Di chuyển 'right' cho đến khi gặp số chẵn
        while (left < right && arr[right] % 2 != 0) {
            right--;
        }

        // Nếu left < right, có nghĩa là tìm thấy một cặp sai vị trí, tiến hành hoán đổi
        if (left < right) {
            swap(arr[left], arr[right]);
            // Sau khi hoán đổi, di chuyển cả hai con trỏ để tiếp tục tìm kiếm
            left++;
            right--;
        }
    }
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    cout << "Mang truoc khi tach chan le: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << "\n";

    separateEvenOdd(arr);

    cout << "Mang sau khi tach chan le: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << "\n";

    vector<int> arr2 = { 2, 4, 6, 8, 1, 3, 5, 7 };
     cout << "Mang truoc khi tach chan le: ";
    for (int x : arr2) {
        cout << x << " ";
    }
    cout << "\n";
    separateEvenOdd(arr2);
    cout << "Mang sau khi tach chan le: ";
    for (int x : arr2) {
        cout << x << " ";
    }
    cout << "\n";


    return 0;
}

Giải thích mã nguồn:

Hàm separateEvenOdd sử dụng hai con trỏ left và right.
Vòng lặp while (left < right) tiếp tục cho đến khi hai con trỏ gặp nhau hoặc vượt qua nhau.
Hai vòng lặp while bên trong dùng để di chuyển left và right đến vị trí cần xử lý: left dừng ở số lẻ đầu tiên từ trái sang, right dừng ở số chẵn đầu tiên từ phải sang, trong khi vẫn đảm bảo left < right. Điều kiện left < right trong các vòng lặp while bên trong là quan trọng để tránh con trỏ đi quá giới hạn sau khi vòng lặp chính while (left < right) kết thúc hoặc gần kết thúc.
Nếu left < right sau khi các vòng lặp con kết thúc, điều đó có nghĩa là arr[left] là một số lẻ (ở vị trí sai) và arr[right] là một số chẵn (ở vị trí sai). Chúng ta hoán đổi chúng bằng swap.
Sau khi hoán đổi, tăng left và giảm right để thu hẹp phạm vi tìm kiếm.
Quá trình này đảm bảo rằng mọi số chẵn được "đẩy" về bên trái và mọi số lẻ được "đẩy" về bên phải.

Bài Tập 4: Tìm Tổng Lớn Nhất Của Mảng Con Liên Tục (Maximum Subarray Sum)

Yêu cầu: Cho một mảng các số nguyên (có thể bao gồm số âm), tìm tổng lớn nhất của một mảng con liên tục bất kỳ trong mảng đó. Mảng con phải chứa ít nhất một phần tử.

Ví dụ: Mảng [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Mảng con liên tục có tổng lớn nhất là [4, -1, 2, 1], với tổng bằng 6.

Phân tích: Đây là một bài toán kinh điển trong lập trình động, có thể giải quyết hiệu quả bằng Thuật toán Kadane. Thuật toán này có độ phức tạp thời gian O(N).

Ý tưởng (Thuật toán Kadane):

Duy trì hai biến: current_max (tổng lớn nhất của mảng con kết thúc tại vị trí hiện tại) và global_max (tổng lớn nhất của mảng con tìm được cho đến hiện tại trên toàn bộ mảng).
Khởi tạo global_max bằng một giá trị rất nhỏ (âm vô cùng hoặc giá trị của phần tử đầu tiên) và current_max bằng 0 (hoặc giá trị của phần tử đầu tiên).
Duyệt qua mảng từ phần tử thứ hai (hoặc từ đầu nếu khởi tạo current_max bằng 0).
Với mỗi phần tử x tại vị trí hiện tại:
- Cập nhật current_max: current_max = max(x, current_max + x). Nghĩa là tổng lớn nhất kết thúc tại vị trí hiện tại là chính phần tử x (nếu current_max + x nhỏ hơn x, tức là thêm mảng con trước đó làm giảm tổng) hoặc là tổng của mảng con lớn nhất kết thúc ở vị trí trước đó cộng thêm x.
- Cập nhật global_max: global_max = max(global_max, current_max). Nếu current_max hiện tại lớn hơn global_max đã tìm được, cập nhật global_max.
Sau khi duyệt hết mảng, global_max sẽ chứa tổng lớn nhất của mảng con liên tục.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <algorithm> // Sử dụng max
#include <limits>    // Sử dụng numeric_limits

int maxSubarraySum(const vector<int>& arr) {
    if (arr.empty()) {
        // Trường hợp mảng rỗng, có thể trả về 0, ném exception, hoặc trả về giá trị âm vô cùng
        // Tùy thuộc vào yêu cầu bài toán cụ thể. Ở đây trả về 0.
        return 0;
    }

    int global_max = numeric_limits<int>::min(); // Khởi tạo global_max với giá trị âm nhỏ nhất có thể
    int current_max = 0; // Khởi tạo current_max ban đầu là 0

    // Duyệt qua từng phần tử trong mảng
    for (int x : arr) {
        // Cập nhật current_max: Mảng con tốt nhất kết thúc tại vị trí hiện tại
        // Hoặc là chỉ có mình phần tử x, hoặc là tổng của mảng con tốt nhất kết thúc ở vị trí trước đó cộng với x
        current_max = max(x, current_max + x);

        // Cập nhật global_max: So sánh tổng tốt nhất hiện tại (current_max) với tổng tốt nhất đã tìm được
        global_max = max(global_max, current_max);
    }

    // Lưu ý: Nếu tất cả các số đều âm, global_max sẽ là số âm lớn nhất (gần 0 nhất).
    // Cách khởi tạo global_max = arr[0] và current_max = arr[0] và duyệt từ phần tử thứ 2 cũng hoạt động
    // và xử lý tốt trường hợp tất cả âm, nhưng cách khởi tạo current_max = 0 và global_max = MIN_INT cũng đúng
    // theo công thức chuyển trạng thái của DP.

    return global_max;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    cout << "Mang: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << "\n";

    int maxSum = maxSubarraySum(arr);

    cout << "Tong lon nhat cua mang con lien tuc: " << maxSum << "\n"; // Kết quả phải là 6

    vector<int> arr2 = { 5, 4, -1, 7, 8 };
    cout << "Mang: ";
    for (int x : arr2) {
        cout << x << " ";
    }
    cout << "\n";
    maxSum = maxSubarraySum(arr2);
    cout << "Tong lon nhat cua mang con lien tuc: " << maxSum << "\n"; // Kết quả phải là 23

     vector<int> arr3 = { -1, -2, -3, -4 };
    cout << "Mang: ";
    for (int x : arr3) {
        cout << x << " ";
    }
    cout << "\n";
    maxSum = maxSubarraySum(arr3);
    cout << "Tong lon nhat cua mang con lien tuc: " << maxSum << "\n"; // Kết quả phải là -1

    return 0;
}

Giải thích mã nguồn:

Hàm maxSubarraySum nhận mảng dưới dạng tham chiếu hằng (const vector<int>&) vì chúng ta không sửa đổi mảng gốc.
Kiểm tra mảng rỗng là cần thiết để tránh lỗi truy cập.
global_max được khởi tạo với numeric_limits<int>::min() để đảm bảo rằng bất kỳ tổng nào (kể cả các số âm) cũng lớn hơn giá trị khởi tạo này.
current_max được khởi tạo là 0. Nó đại diện cho tổng lớn nhất của mảng con kết thúc tại vị trí đang xét. Nếu current_max trở thành âm, nó sẽ không làm tăng tổng của các phần tử sau này, vì vậy khi gặp một phần tử dương, mảng con tốt nhất kết thúc tại đó có thể chỉ bắt đầu từ chính phần tử dương đó.
Vòng lặp duyệt qua mảng.
current_max = max(x, current_max + x); là trái tim của thuật toán Kadane. Nó quyết định xem việc mở rộng mảng con tốt nhất từ vị trí trước đó bằng cách thêm x có lợi hơn so với việc bắt đầu một mảng con mới chỉ với x.
global_max = max(global_max, current_max); liên tục cập nhật tổng lớn nhất tìm được trên toàn bộ mảng cho đến thời điểm hiện tại.
Hàm trả về global_max.

Tiếp Tục Thực Hành

Các bài tập trên chỉ là một vài ví dụ về các vấn đề bạn có thể gặp khi làm việc với mảng một chiều ở mức độ nâng cao hơn một chút. Để thực sự thành thạo, hãy thử sức với nhiều bài tập khác như:

Tìm kiếm phần tử theo điều kiện phức tạp.
Xóa/chèn phần tử vào mảng đã sắp xếp hoặc chưa sắp xếp (hiệu quả).
Tìm kiếm cặp/ba phần tử có tổng bằng một giá trị cho trước.
Tìm điểm cân bằng trong mảng (vị trí mà tổng các phần tử bên trái bằng tổng các phần tử bên phải).
Sử dụng mảng làm bộ đếm cho các bài toán liên quan đến tần suất hoặc phân bố. S

Comments

There are no comments at the moment.