iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 1
0
自我挑戰組

30天 HackerRank 解解解 系列 第 1

Day 1 - 2D Array - DS

今天是開賽的第一天, 以後的解題會優先以 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();
	}
}


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


下一篇
Day 2 - Arrays: Left Rotation
系列文
30天 HackerRank 解解解 2

尚未有邦友留言

立即登入留言