HarckerRank二维阵列沙漏挑战

Question

关于二维阵列 HackerRank问题。

任务是在二维数组中找到区域的最大和。具体来说，它是寻找一个“沙漏”区域的最大和，定义为一个3x3平方，左边和右边没有中间项，如这个掩码所示。

1 1 1
0 1 0
1 1 1

这是我的解决办法。

我希望能对代码质量进行一些评论。

# Begin of HackerRank code: data entries for testing the user code
# ----------------------------------------------------------------
arr = []

for _ in range(6):
    arr.append(list(map(int, input().rstrip().split())))
# ----------------------------------------------------------------
# End of HackerRank code


my_hourglasses = list()

for i in range(0,4):
    for j in range(0,4):
        hourglass = list()
        hourglass += arr[i][j:j+3]
        hourglass.append(arr[i+1][j+1])
        hourglass += arr[i+2][j:j+3]
        my_hourglasses.append(hourglass)

hourglasses_sums = [sum(item) for item in my_hourglasses]

print(max(hourglasses_sums))

Answer 1

你有一个识别和提取沙漏的部分。然后你把各个沙漏相加。那你就能找到最大的。

计算机科学家托尼·霍尔( Tony )有句名言：“有两种编写代码的方法:编写代码如此简单，其中显然没有错误，或者编写代码如此复杂，以至于没有明显的错误。”例如，在引用实现或测试用例中，我希望看到这类代码。

另一方面，这种简单是要付出代价的。您的实现需要分配一组额外的内存来保存所有的临时沙漏，并且需要更多的内存来保存所有的总和。

原则上，您可以在沙漏中标识元素之后立即将它们添加起来，然后只存储hourglasses_sums而不是my_hourglasses。然后你就会得到这样的东西：

max_hourglass_score = -63  # Minimum possible score = -9 * 7
for i in range(0,4):
    for j in range(0,4):
        hourglass = list()
        hourglass += arr[i][j:j+3]
        hourglass.append(arr[i+1][j+1])
        hourglass += arr[i+2][j:j+3]
        hourglass_sum = sum(hourglass)
        max_hourglass_score = max(max_hourglass_score, hourglass_sum)

print(max_hourglass_score)

当然，可以应用相同的模式来完成和，而不是将其选择到中间的hourglass列表中。

max_hourglass_score = -63  # Minimum possible score
for i in range(0,4):
    for j in range(0,4):
        hourglass_sum = 0
        hourglass_sum += sum(arr[i][j:j+3])
        hourglass_sum += arr[i+1][j+1]
        hourglass_sum += sum(arr[i+2][j:j+3])
        max_hourglass_score = max(max_hourglass_score, hourglass_sum)

print(max_hourglass_score)

这只分配了几个基本变量，而不是以前所有的额外数组。

事实上，仍然有更聪明的算法，需要较少的算术运算。关键的想法更容易用方块来解释，而不是沙漏。如果您查看左上角的方块，并将其与对面的正方形进行比较，那么许多条目都是相同的。具体来说，在一个正方形的九个条目中，有六个是重叠的。加速程序的潜力在于不再寻找重叠平方，而是从最后一次和开始，去掉它中不再存在的值，并添加新的值。

这个算法，无论多么聪明，都是复杂的。这是很难得到正确的，甚至很难看出它是否正确。因此，这是一个判断，判断您有多重视让代码尽可能快地运行，以及您有多喜欢以一种易于理解的方式编写它。没有最好的答案。这取决于你想用它做什么。如果这是在视频帧上实时运行，并且是程序中最大的瓶颈(在某种程度上是合适的)，那么您可能更喜欢更快。如果它在一个小网格上移动，您将需要清晰的代码。

另有几项一般性意见：

• 变量命名很重要。虽然“沙漏”通常看起来是一个非常具体和有用的词来识别正在发生的事情，但是当你的三个主要变量围绕同一个单词构建时，人们应该会怀疑它是否真的变得混乱了。(而且，"my_“通常是不必要的。)
• 我很欣赏Python理解的用法。如果您只想使用它一次，生成器的理解往往更好。就其编写方式而言，只需将sum(item) for item in my_hourglasses周围的方括号替换为括号即可。就它所做的事情而言，它避免了实际的计算，直到你需要它，给空间，有时节省时间。
• 小心神奇的数字。我意识到，4是大网格的宽度，减去2，因为沙漏的宽度是3，重叠的宽度是1。但这并不是很明显，所以值得详细说明4的含义。