python - 概括二维数组中的沙漏运动 - Python 中的 DS

Question

在工作时 this HackerRank challenge准备面试，偶然发现了一个拦路虎。
基本上想创建一个函数 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

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

Error (stderr) Traceback (most recent call last): File

"Solution.py", line 119, in

result = hourglassSum(arr) File "Solution.py", line 74, in hourglassSum

row_3 = arr[i+2][0:3] IndexError: list index out of range

我遇到的问题是行为的概括，来自评论 # 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 的内部，其中一个在初始列中向下移动(因此 i = 0)，另一个向右和向下移动(因此 j = 1)

删除了++i 和++j 因为循环会根据给定的范围

增加它

立即得到每个 row_1、row_2 和 row_3 的总和(无需存储它们的实际值)并将其关联到变量 hg_current_sum

使用 max() 函数将迄今为止的最高值 (hg_max_sum) 与 hg_current_sum

进行比较

这将通过所有当前的测试