在Python中推广二维数组中的沙漏运动 - DS

Question

在完成此 HackerRank 挑战以准备面试时，偶然发现了一个拦截器。

基本上想要创建一个函数 hourglassSum ，它应该返回一个整数（数组中的最大沙漏总和）。给定一个 6 x 6 2D 数组，arr:

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

arr中有16个沙漏，一个沙漏总和就是一个沙漏值的总和。在这种情况下，沙漏的总和是 7。

这是我目前拥有的代码（已注释，因此应该很容易理解所做的决定）

def hourglassSum(arr):
    #print(f"arr: {arr}")
    #print(f"arr[1]: {arr[1]}")
    #print(f"arr[1][1]: {arr[1][1]}")
    num_rows = len(arr)
    num_cols = len(arr[0])
    hg_total = 0
    hg_current_sum = 0 
    hg_max_sum = 0
    i = 0
    j = 0
    
    # There's no hourglass
    if 0 <= num_rows <= 3 or 0 <= num_cols <= 3:
        hg_total = 0
        hg_max_sum = 0
        
    # There's hourglass
    else:
        if num_rows > num_cols:
            # hg_total = num_cols - 2 + ( num_rows - num_cols ) 
            hg_total = num_rows - 2
        #elif num_cols > num_rows:
        else:
            # hg_total = num_rows - 2 + ( num_cols - num_rows ) 
            hg_total = num_cols - 2
        # irrelevant and could be added to any of the others, transforming the elif into else
        # else:
        #    hg_total = num_rows - 2
    
    # only one hourglass        
    if hg_total == 1:
        # calculate hg_current_sum
        row_1 = arr[0][0:3]
        row_2 = arr[1][1]
        row_3 = arr[2][0:3]
        
        #input
        """
        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
        """
        #print(f"row_1: {row_1}")
        #print(f"row_2: {row_2}")
        #print(f"row_3: {row_3}")
        #output
        """
        row_1: [1, 1, 1]
        row_2: 1
        row_3: [1, 1, 1]
        """
            
        # Note that row_2 won't have sum() because it'll be always int and not a list of numbers
        hg_current_sum = sum(row_1) + row_2 + sum(row_3)
        hg_max_sum = hg_current_sum
        return hg_max_sum
            
    # Generalize
    while i < num_rows:
        row_1 = arr[i][0:3]
        row_2 = arr[i+1][1]
        row_3 = arr[i+2][0:3]
                
        hg_current_sum = sum(row_1) + row_2 + sum(row_3)
                
        # 9 is the highest value for a cell
        # 7 is the amount of cells in each hourglass
        # lowest_sum = -9 * 7
        # Hightest_sum = 9 * 7
        if hg_current_sum == 9*7:
            hg_max_sum = hg_current_sum
            break
        elif hg_current_sum > hg_max_sum:
            hg_max_sum = hg_current_sum
                    
        i = i + 2
        
    while j < num_cols:
        row_1 = arr[0][j:j+2]
        row_2 = arr[1][j+1]
        row_3 = arr[2][j:j+2]
                
        hg_current_sum = sum(row_1) + row_2 + sum(row_3)
                
        # 9 is the highest value for a cell
        # 7 is the amount of cells in each hourglass
        # lowest_sum = -9 * 7
        # Hightest_sum = 9 * 7
        if hg_current_sum == 9*7:
            hg_max_sum = hg_current_sum
            break
        elif hg_current_sum > hg_max_sum:
            hg_max_sum = hg_current_sum
                    
        j = j + 2
         
    return hg_max_sum

如果我执行这个，它会给出一个

错误（stderr）回溯（最近一次调用）：文件

“Solution.py”，第 119 行，位于

结果 = hourglassSum(arr) 文件“Solution.py”，第 74 行，在 hourglassSum 中

row_3 = arr[i+2][0:3] IndexError：列表索引超出范围

---

我遇到的问题是行为的概括，从评论

# Generalize

开始。从那一刻起，就开始了不止一个沙漏的场景。

我可以看到沙漏的移动应该如何发生：左上角 -> 右上角（向右移动 1 个单元格，直到沙漏中最右边的单元格到达数组中最后一个现有列）并重复此过程移动 1 个单元格向下直到沙漏中最下方的单元格到达数组的最后一行/底部。

可以看到它可以通过在 for 循环（从顶部 -> 底部）内部使用 for 循环（从左 -> 右）来完成。所以，类似

for i in range(num_rows)
    # do stuff
    for j in range(num_cells)
        # do stuff    

这通常会使循环内的部分几乎没有必要；我把它们放在这里的唯一原因是为了可视化每个单元格向右或向下的移动。

然后呢？

Answer 1

向右移动，我会将沙漏的每个部分更新为“滑动窗口”，减去以前最左边的元素并添加新的最右边的元素。将沙漏向下移动一排时开始一个新的沙漏。

这是 JavaScript 代码，可以轻松转换为 Python：

function f(m){
  if (m.length < 3 || m[0].length < 3)
    return null;
    
  let row1, row2, row3;
  
  let best = -Infinity;
  
  for (let i=0; i<m.length-2; i++){
    // Update the hourglass moving down
    row1 = m[i][0] + m[i][1] + m[i][2];
    row2 = m[i+1][1];
    row3 = m[i+2][0] + m[i+2][1] + m[i+2][2];
    
    best = Math.max(best, row1 + row2 + row3);
    
    for (let j=1; j<m[0].length-2; j++){
      // Update the hourglass moving to the right
      row1 += m[i][j+2] - m[i][j-1];
      row2 = m[i+1][j+1];
      row3 += m[i+2][j+2] - m[i+2][j-1];
      
      best = Math.max(best, row1 + row2 + row3);
    }
  }
  
  return best;
}

var m = [
  [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]
];

console.log(f(m));

Tiago Martins Peres 李大仁更新：

这是 Python 代码：

def hourglassSum(arr):
    #print(f"arr: {arr}")
    #print(f"arr[1]: {arr[1]}")
    #print(f"arr[1][1]: {arr[1][1]}")
    num_rows = len(arr)
    num_cols = len(arr[0])
    hg_max_sum = -float('Inf') #-inf
    hg_current_sum = 0
    i = 0
    j = 1
    
    # There's no hourglass
    if 0 <= num_rows <= 3 or 0 <= num_cols <= 3:
        hg_max_sum = 0
    
    for i in range(0,num_rows - 2):
        # Update the hourglass moving down
        row1 = arr[i][0] + arr[i][1] + arr[i][2];
        row2 = arr[i+1][1];
        row3 = arr[i+2][0] + arr[i+2][1] + arr[i+2][2];
        hg_current_sum = row1 + row2 + row3
        #print(f"1_ hg_current_sum: {hg_current_sum}")
    
        hg_max_sum = max(hg_max_sum, hg_current_sum);
        
        #print(f"1_ hg_max_sum: {hg_max_sum}")
        
        for j in range(1,num_cols - 2):
            # Update the hourglass moving to the right
            row1 += arr[i][j+2] - arr[i][j-1];
            row2 = arr[i+1][j+1];
            row3 += arr[i+2][j+2] - arr[i+2][j-1];
            hg_current_sum = row1 + row2 + row3
            #print(f"2_ hg_current_sum: {hg_current_sum}")
        
            hg_max_sum = max(hg_max_sum, hg_current_sum);
            #print(f"2_ hg_max_sum: {hg_max_sum}")
        
    return hg_max_sum

基本上区别就是现在

• 通过专注于本质，消除了您添加的一些复杂性
• 将 hg_max_sum 设置为 -inf
• 在 for 内部使用 for，其中一个在初始列中向下移动（因此 i = 0），另一个向右和向下移动（因此 j = 1）
• 删除了 ++i 和 ++j，因为循环将根据给定范围必然地增加它
• 立即获得每一 row_1、row_2 和 row_3 的总和（无需存储它们的实际值）并将其关联到变量 hg_current_sum
• 使用 max() 函数将迄今为止的最高值 (hg_max_sum) 与 hg_current_sum 进行比较

这将通过当前所有测试

Answer 2

  public static int hourglassSum(List<List<int>> arr)
    { 
       int[] sum = new int[16];
        int hourglass = 0;
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 4; j++)
            {
                sum[hourglass] = 
                          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++;
            }
        }
          return sum.Max();;
    }