2D Array – HackerRank Solution

Bắt đầu với Series giải các bài toán trong bộ Interview Preparation Kit của Hackerrank, chúng ta sẽ giải một bài về mảng 2 chiều khá đơn giản có tựa đề là 2D Array – DS.

Tác giả: Shafaet

Độ khó: Dễ

Điểm: 15

Link bài toán: HackerRank – 2D Array DS

Đề bài toán

Tóm tắt đề bài

Đầu vào (input):

• Một mảng 2 chiều kích thước cố định 6×6: arr
• -9 <= arr[i][j] <= 9
• 0 <= i, j <= 5

Giải thích (Explanation):

• Đầu vào của chúng ta là một mảng 6×6, tức là chúng ta sẽ có 16 cái đồng hồ cát (hourglass) như đề bài đề cập.
• Với mỗi đồng hồ cát đó chúng ta sẽ tính tổng của nó.
• Tìm max trong 16 cái tổng đó.

Đầu ra (output):

In ra số lớn nhất của các tổng đồng hồ cát.

Ý tưởng

Cách 1: Giải đơn giản

• Chạy 2 vòng lặp lồng nhau ( 0 <= i, j < 4 )
• Tại mỗi vị trí i, j chúng ta sẽ tính tổng của một hourglass bằng cách nhập thô các vị trí cần cộng vào.
• Tìm max của các giá trị vừa tính là xong.

Cách 2: Giải linh động

Cách này tuy phức tạp hơn nhưng sẽ linh động hơn với các bài toán khác tương tự với kích thước mảng lớn hơn.

• Mình sẽ xây dựng một hàm getHourglass để xác định một cái đồng hồ cát ở vị trí nhất định.
  • Hàm này sẽ nhận 3 tham số là mảng 2D 6×6, vị trí của phần tử bắt đầu của đồng hồ cát đó (hàng và cột).
  • Hàm này sẽ trả ra một mảng 2 chiều 3×3 bằng chứa hourglass chúng ta cần.
• Tiếp đến là một hàm để tính tổng của một hourglass từ hàm getHourglass trả ra (mình gọi hàm này là sumHourglass).
  • Hàm này đơn giản là tính tổng của mảng 2 chiều 3×3 và bỏ đi 2 phần tử arr[1][0] và arr[1][2].
• Và cuối cùng, là một hàm chạy qua mảng 2 chiều 6×6 để tính tổng 16 cái hourglass. Sau đó, tìm giá trị lớn nhất trong đó và trả về.

Triển khai

Ngôn ngữ sử dụng: JavaScript

Ghi chú: Do mảng đầu vào là cố định và có ràng buộc rõ ràng nên các hàm mình sẽ bỏ qua bước kiểm tra dữ liệu đầu vào.

Cách 1

function hourglassSum(arr) {
  let sumArray = [];

  for (let i = 0; i < 4; ++i) {
    for (let j = 0; j < 4; ++j) {
      const sum = arr[i][j] + arr[i][j+1] + arr[i][j+2] 
                  + arr[i+1][j+1] 
                  + arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2];
      
      sumArray.push(sum);
    }
  }

  return Math.max(...sumArray);
}

Cách 2

function getHourglass(arr, rowPos, colPos) {
  let i = 0;
  let j = rowPos;
  let res = [];

  while (i < 3) {
    const hourglass = arr[j++].slice(colPos, colPos + 3)
    res.push(hourglass);
    ++i;
  }

  return res;
}

function sumHourglass(arr) {
  let sum = 0;

  for (let i = 0; i < 3; ++i) {
    for (let j = 0; j < 3; ++j) {
      sum += arr[i][j];
    }
  }

  return sum - arr[1][0] - arr[1][2];
}

function hourglassSum(arr) {
  let sumArray = [];

  for (let i = 0; i < 4; ++i) {
    for (let j = 0; j < 4; ++j) {
      const hourglass = getHourglass(arr, i, j);
      const sum = sumHourglass(hourglass);
      sumArray.push(sum);
    }
  }

  return Math.max(...sumArray);
}

Tạm Kết

Rất dễ đúng không nào, anh em nào còn cách giải nào khác thì comment phía dưới cho mình biết nhé. Cùng theo dõi cách giải cách bài toán khác của Hackerrank ở đây nhé Series Phá Đảo HackerRank

Cảm ơn mọi người đã đọc bài viết ❤