Tôi ứng dụng cấp phát động trên mảng 2 chiều như thế nào?

Sau khi buồn chán vì nhiều chuyện xã hội, tôi có cảm giác mình không thể tìm được niềm vui trong chuyện học hành. Tôi muốn tìm một việc gì đó thật hứng thú để làm.

Trong lúc đang loay hoay suy nghĩ, tôi vô tình đọc được 1 chia sẻ trên Facebook về coder VN đứng thứ 3 thế giới gì đó… thế là tôi Login ngay vào Hackerrank, thôi thì cứ làm cho vui, với rèn luyện tiếng Anh 1 chút. Tôi dễ dàng Accept các bài dễ đầu tiên (Thật ra nó khá dễ, chủ yếu giúp bạn rèn luyện, và nhớ đến các lệnh). Accept một vài bài If, for, cin cout, printf, scan… Tôi chợt thấy “Pointer”!!, tự nghĩ trong đầu, sao nó nâng tầm nhanh nhỉ (Thật ra là do tôi vừa học C++ =))) ) Thế là làm thử và Accept luôn. Tiếp đến 1 bài căn bản về mảng, nhập vào và xuất ngược, quá Easy…

Thế là tôi vô tư bấm tiếp Next Challenge, nhìn sơ qua, kinh khủng, đề dài, mô tả lung tung, input nhập cả đống!. Tôi định tắt máy đi ăn cơm :)) nhưng cố gắng dịch đề, dịch qua lần đầu tôi không hiểu gì cả, chỉ hiểu cách nhập mà đề nói.

1. Đề bài Variable Sized Arrays

Link bài: https://www.hackerrank.com/challenges/variable-sized-arrays

Sau đó tôi quyết định nhìn vào mô tả đề bài, và input mẫu, số đầu tiên ở dòng thứ 2 chắc là số phần tử của dòng đó, tiếp đến tôi tự hỏi, số nguyên N để làm gì nhỉ?? Do tôi không hiểu nội dung đề lắm nên thôi cứ vậy =)) Suy nghĩ 1 lát à, chắc là nhập N cái dòng mảng 1 chiều. Lúc này vẫn chưa hiểu ý đồ của bài, thế là tôi quyết định đọc 2 dòng giải thích truy vấn, “Tìm các mảng nằm ở chỉ số i = 0, tương ứng với a[0] = [1,5,4].  Chúng ta phải in các giá trị ở chỉ số j=1 trong mảng đó….. pla pla nhìn thấy số 5”, Ahh thì ra các mảng 1 chiều này được đánh số bắt đầu từ 0. Lúc này tôi kéo lên hình hình minh họa, nhìn vô mảng số 0, vị trí 1, thì nó là số 1 mà?? đâu phải số 5?? lúc này tôi nhìn giải thích của truy vấn 2, j=3 là số 8, chứ đâu phải 9, ahh thì ra là mảng nó đánh số từ 0. thế là oke hiểu đề rồi.

Lúc này tôi nhìn sơ qua đoạn hướng dẫn đọc input. Dòng ghi 3*10^5 @@ mà n<=k nữa chứ. @@ lúc này thoáng nghĩ 3*10^5 mà bình phương lên cũng cỡ 10^10 rồi. mảng 2 chiều sao khai báo ta??? Thôi xong, nhìn lại dòng 3*10^5, ủa có dấu xích ma tổng K pla pla gì đó. à, lúc này nghĩ chắc chả sao, nhưng khai báo mảng 10^10 sẽ lỗi, nên chợt nghĩ đến Cấp phát động trong mảng 2 chiều, nó dùng bao nhiêu thì mình cấp bấy nhiêu, khỏi vượt quá bộ nhớ là được :v

2. Tóm lại đề bài

Yêu cầu mình nhập n, q

n dòng sau mỗi dòng nhập 1 mảng 1 chiều có k phần tử.

q dòng sau, mỗi dòng gồm 2 số i,j.

Với mỗi truy vấn i,j đề bài yêu cầu mình xuất ra phần tử ở mảng được đánh số là i, và nằm ở vị trí thứ j.

Thế là mình viết ngay một code dùng cấp phát động như sau:

int **a = new int*[n]; Thực chất bài trên chính là nhập vào mảng 2 chiều, nên ngay dòng này mình dùng con trỏ cấp 2, để cấp phát cho a, có n dòng trước.

tiếp đến mình duyệt qua từng dòng của input, đầu tiên mình nhập số phần tử vào biến k.

sau khi có giá trị k, chắc chắn mình sẽ biết được mảng 1 chiều này sẽ có k phần tử, thế nên cấp phát ngay cho nó k phần tử bằng lệnh a[i] = new int[k];

sau khi cấp phát thì cứ nhập bình thường thôi :d

Bây giờ đến q cái truy vấn i,j , lúc này mình chỉ việc xuất ra a[i][j] thôi là xong…

Thế là mình submit code, Ahhh “Congrats, you solved this challenge!” Vậy là đã Accept rồi :v

Lúc viết bài viết này mình định thu hồi bộ nhớ, không nhiều bạn lại bảo cấp xong mà không thu hồi, không chuẩn mực 🙁 nhưng lười quá 18h30 rồi, đi ăn cơm đã =)) thế nên kệ nó luôn, vì thật ra khi judge online, đối vấn đề dữ liệu, giả sử trình chấm nó cho bạn dùng 1GB ram, thì ở Thời điểm nào bạn dùng quá 1gb đó thì nó sẽ báo lỗi ngay, chứ không đợi bạn thu hồi 😀 nên… ngay đây khỏi thu hồi cũng chẳng sao, nhưng học để biết nên thôi các bạn cứ việc thu hồi.

Nhưng mà nếu bạn muốn thu hồi thì có thể dùng dòng này ngay trước return 0

for (int i=0; i<n; i++)
    delete [] a[i]; //  thu hồi từng mảng 1 chiều a[i]
delete [] a; // thu hồi mảng a

3. Code tham khảo về cấp phát động

#include <iostream>
using namespace std;

int main() {
    int n, q, k;
    cin >> n >> q;
    int **a = new int*[n];
    for (int i=0; i<n; i++)
    {
        cin >> k;
        a[i] = new int[k];
        for (int j=0; j<k; j++)
            cin >> a[i][j];
    }
    int u,v;
    for (int i=0; i<q; i++)
    {
        cin >> u>> v;
        cout << a[u][v]<<endl;
    }
	return 0;
}

P/s: viết cho vui 🙂 tại đôi lúc search trên google bài tập về pointer còn khá ít 😀