今天是開賽的第一天, 以後的解題會優先以 HackerRank 中的 Interview Preparation Kit 為主
此題會給一個 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
輸入:
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();
}
}
以上是今天的解題分享! 感謝!