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

Sau khi buồn chán vì nhiều chuyện xã hội, tôi có cảm xúc mình không hề tìm được niềm vui trong chuyện học tập. Tôi muốn tìm một việc gì đó thật hứng thú để làm .Trong lúc đang loay hoay tâm lý, tôi vô tình đọc được 1 san sẻ trên Facebook về coder việt nam đứng thứ 3 quốc tế 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 thuận tiện Accept những bài dễ tiên phong ( Thật ra nó khá dễ, hầu hết giúp bạn rèn luyện, và nhớ đến những 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ơ 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 điển, đề dài, diễn đạt lung tung, input nhập cả đống !. Tôi định tắt máy đi ăn cơm :)) nhưng cố gắng nỗ lực 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 .

Tóm Tắt

1. Đề bài Variable Sized Arrays

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

Bạn đang đọc: Tôi ứng dụng cấp phát động trên mảng 2 chiều như thế nào? – Kiến Thức 24h

untitled

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, qn dòng sau mỗi dòng nhập 1 mảng 1 chiều có k thành phần .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 nhu yếu mình xuất ra thành phần ở 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ép cho a, có n dòng trước .tiếp đến mình duyệt qua từng dòng của input, tiên phong mình nhập số thành phần vào biến k .sau khi có giá trị k, chắc như đinh mình sẽ biết được mảng 1 chiều này sẽ có k thành phần, thế nên cấp phép ngay cho nó k thành phần bằng lệnh a [ i ] = new int [ k ] ;sau khi cấp phép thì cứ nhập thông thường thôi : dBâ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