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>
#include <algorithm>

using namespace std;

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

    map<int, int> dem;

    for (int pt : a) {
        dem[pt]++;
    }

    int ptMax = -1;
    int maxDem = 0;

    for (auto const& [p, d] : dem) {
        if (d > maxDem) {
            maxDem = d;
            ptMax = p;
        }
    }

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

    if (maxDem > 0) {
        cout << "Phan tu xuat hien nhieu nhat: " << ptMax << " (xuat hien " << maxDem << " lan)\n";
    } else {
        cout << "Mang rong hoac khong co phan tu nao.\n";
    }

    return 0;
}

Output:

Mang ban dau: 1 2 2 3 1 4 2 1 5 1 2 
Phan tu xuat hien nhieu nhat: 1 (xuat hien 4 lan)

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>

using namespace std;

void xoayPhai(vector<int>& a, int k) {
    int n = a.size();
    if (n == 0 || k <= 0) return;

    k %= n;

    reverse(a.begin(), a.end());
    reverse(a.begin(), a.begin() + k);
    reverse(a.begin() + k, a.end());
}

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

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

    xoayPhai(a, k);

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

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

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

    xoayPhai(b, k2);

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

    return 0;
}

Output:

Mang truoc khi xoay: 1 2 3 4 5 6 7 
Mang sau khi xoay phai 3 buoc: 5 6 7 1 2 3 4 
Mang truoc khi xoay: -1 -100 3 99 
Mang sau khi xoay phai 2 buoc: 3 99 -1 -100

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>

using namespace std;

void tachChanLe(vector<int>& a) {
    int l = 0;
    int r = a.size() - 1;

    while (l < r) {
        while (l < r && a[l] % 2 == 0) {
            l++;
        }

        while (l < r && a[r] % 2 != 0) {
            r--;
        }

        if (l < r) {
            swap(a[l], a[r]);
            l++;
            r--;
        }
    }
}

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

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

    tachChanLe(a);

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

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

    return 0;
}

Output:

Mang truoc khi tach chan le: 3 1 4 1 5 9 2 6 5 3 5 
Mang sau khi tach chan le: 6 2 4 1 5 9 1 3 5 3 5 
Mang truoc khi tach chan le: 2 4 6 8 1 3 5 7 
Mang sau khi tach chan le: 2 4 6 8 1 3 5 7

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>
#include <limits>

using namespace std;

int tongMaxMangCon(const vector<int>& a) {
    if (a.empty()) {
        return 0;
    }

    int gMax = numeric_limits<int>::min();
    int cMax = 0;

    for (int gt : a) {
        cMax = max(gt, cMax + gt);
        gMax = max(gMax, cMax);
    }

    return gMax;
}

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

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

    int maxTong = tongMaxMangCon(a);

    cout << "Tong lon nhat cua mang con lien tuc: " << maxTong << "\n";

    vector<int> b = { 5, 4, -1, 7, 8 };
    cout << "Mang: ";
    for (int x : b) {
        cout << x << " ";
    }
    cout << "\n";
    maxTong = tongMaxMangCon(b);
    cout << "Tong lon nhat cua mang con lien tuc: " << maxTong << "\n";

     vector<int> c = { -1, -2, -3, -4 };
    cout << "Mang: ";
    for (int x : c) {
        cout << x << " ";
    }
    cout << "\n";
    maxTong = tongMaxMangCon(c);
    cout << "Tong lon nhat cua mang con lien tuc: " << maxTong << "\n";

    return 0;
}

Output:

Mang: -2 1 -3 4 -1 2 1 -5 4 
Tong lon nhat cua mang con lien tuc: 6
Mang: 5 4 -1 7 8 
Tong lon nhat cua mang con lien tuc: 23
Mang: -1 -2 -3 -4 
Tong lon nhat cua mang con lien tuc: -1

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.