今天是開賽的第一天, 以後的解題會優先以 HackerRank 中的 Interview Preparation Kit 為主

2D Array - DS

原題網址

https://www.hackerrank.com/challenges/2d-array/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

難度： easy

題目描述

此題會給一個 6*6 的二維陣列,
例如：

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

要計算出所謂的 hourglass (沙漏) 的總和
什麼是 hourglass（沙漏）呢？
就是如下圖所示

a b c
  d
e f g

這圖行是不是很像一個沙漏呢？ XD
於是 a + b + c + d + e + f + g = 一個 hourglass sum (沙漏總和)

如下例： 這個陣列裡包含了很多個 hourglass, 那我們就是要印出 最大的 hourglass sum

-9 -9 -9  1 1 1 
 0 -9  0  4 3 2
-9 -9 -9  1 2 3
 0  0  8  6 6 0
 0  0  0 -2 0 0
 0  0  1  2 4 0

計算後的 hourglass sum 如下：

-63, -34,  -9, 12, 
-10,   0,  28, 23, 
-27, -11,  -2, 10, 
  9,  17,  25, 18

由此可以得知 最大值的 hourglass sum 就是 28

也就是原本陣列中的這個 hourglass

0 4 3
  1
8 6 6

目的

那我們就是要寫一個方法, 來找出最大 hourglass

輸入限制

• input 會是個 6*6 的二維陣列
• 陣列中每個元素的值介於 9 ~ -9

範例

輸入：

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0

輸出：
19

解題概念：

由此題我們可以觀察到 hourglass (沙漏)的圖形

a b c
  d
e f g

其實是...
top : 3 個元素 a b c
middle : 中間一個元素 d
buttom : 3 個元素 e f g

所以其實我們只要這樣把 a ~ g 都加起來就對了

也就是如下
假定陣列是 arr[6][6] 6*6的二維陣列
那我們要算的其實就是

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]

這樣的 hourglass sum (沙漏和)

另外 由於

a b c
  d
e f g

在這樣的圖形中, 其實只有 7 個值,
陣列中每個元素的值介於 9 ~ -9
所以我們可以知道 最小的 hourglass sum 會是 7 * -9 = -63
所以可以把 -63 當作一個初始的基準值
只要算出的 hourglass sum 比之前算出的大, 我們就以這個最大的 hourglass sum 為答案

程式碼

package hourglass;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;

public class Solution {


	// Complete the hourglassSum function below.
	static int hourglassSum(int[][] arr) {
		int max = 7 * -9;

		for(int i = 0; i < 6; i++) {
			for(int j = 0; j < 6; j++) {
				if((i+2) < 6 && (j+2) < 6) { // 避免 outbound of index
					int top = arr[i][j] + arr[i][j+1] + arr[i][j+2];
					int middle = arr[i+1][j+1];
					int bottom = arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2];
					int sum = top + middle + bottom;
					if(sum > max) {
						max = sum;
					}

				}
			}
		} 
		return max;
	}

	private static final Scanner scanner = new Scanner(System.in);

	public static void main(String[] args) throws IOException {
		BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

		int[][] arr = new int[6][6];

		for (int i = 0; i < 6; i++) {
			String[] arrRowItems = scanner.nextLine().split(" ");
			scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

			for (int j = 0; j < 6; j++) {
				int arrItem = Integer.parseInt(arrRowItems[j]);
				arr[i][j] = arrItem;
			}
		}

		int result = hourglassSum(arr);

		bufferedWriter.write(String.valueOf(result));
		bufferedWriter.newLine();

		bufferedWriter.close();

		scanner.close();
	}
}

以上是今天的解題分享！ 感謝！