时间戳

首页 > 解决方案 > 从矩阵计算菱形的面积

python - 从矩阵计算菱形的面积

问题描述

我最近进行了一次在线评估，遇到了这个我无法完成的问题。我想要一些关于如何去做的帮助。

问题

让我们将大小为 k 的菱形区域定义为距离矩阵中给定中心单元小于 k 步（上、下、左或右）的所有单元的集合。

在下图中，黑色单元格是菱形区域的中心，每个单元格都包含一个数字——到中心的距离，称为半径。具有相同半径的单元格以相同的颜色着色。

给定一个整数矩阵的矩形矩阵和一个整数半径，您的任务如下：

对于矩阵的每个可能的中心单元，找到周围大小为半径的菱形区域边界上的所有元素的总和。注意：只考虑其元素都在矩阵范围内的菱形区域。从这些总和中，找到 3 个最高的不同值。按值递减的顺序返回一个包含 3 个最高不同和的数组。如果不同的和少于 3 个，则返回一个较短的数组，其中包含所有不同的和以降序排列。

例子

为了

          [4, 1, 4, 5, 3],
          [6, 2, 7, 2, 1],
          [10, 0, 4, 2, 7]]
and radius = 2, the output should be bestRhombicAreaFrame(matrix, radius) = [15, 14, 12].

例子

从上面的动画可以看出，在这 6 个菱形区域中，有四个不同的和：10、12、14、15。所以答案是 [15、14、12]。

输入输出


[input] array.array.integer matrix

A rectangular matrix of integers.

Guaranteed constraints:
1 ≤ matrix.length ≤ 100,
1 ≤ matrix[i].length ≤ 100,
0 ≤ matrix[i][j] ≤ 100.

[input] integer radius

An integer representing the radius of the rhombic areas.

Guaranteed constraints:
1 ≤ 2·radius - 1 ≤ min(matrix.length, matrix[i].length).

[output] array.integer

返回一个数组，其中包含按降序排列的 3 个最高不同总和。

这是我到目前为止所做的。它通过了大约 4/20 个测试用例。

def bestRhombicAreaFrame(matrix, radius):
    s = []
    ci = 0
    
    s1 = 0
    
    n = len(matrix)
    m = len(matrix[0])
    
    
    if radius == 1:
        return [matrix[n//2][m//2]]
    
    for x in range(radius - 1, n):
        if x < n - radius + 1:
            for y in range(radius - 1, m):
                if y < m - radius + 1:
                    center = matrix[x][y]
                    left = matrix[x][y - (radius - 1)]
                    right = matrix[x][y+(radius - 1)]
                    up = matrix[x - (radius - 1)][y]
                    down = matrix[x + (radius - 1)][y]
                    s1 = up + down + left + right
                    if s1 not in s:
                        s.append(s1)
        
    
    s.sort()
    s.reverse()
    return s[0:3]

以下是一些测试用例。

matrix:
[[1,1,2,3,1], 
 [2,5,2,1,7], 
 [1,4,3,1,5], 
 [6,1,4,2,0]]
radius: 2
Expected Output:
[14, 13, 12]


Input:
matrix: [[100]]
radius: 1
Expected Output:
[100]


Input:
matrix:
[[0,0,2,2,0,2], 
 [0,0,2,2,1,1], 
 [1,2,2,1,1,1], 
 [0,2,1,2,0,1], 
 [2,0,0,2,0,0]]
radius: 2
Expected Output:
[8, 7, 6]


Input:
matrix:
[[1,1,2,2,0,2,1], 
 [2,0,2,3,3,2,2], 
 [1,2,1,3,0,2,2], 
 [0,1,0,0,1,1,3], 
 [1,1,1,2,3,2,1], 
 [2,2,1,0,1,0,0], 
 [0,3,3,3,3,2,1], 
 [0,1,1,1,1,0,3]]
radius: 3
Expected Output:
[21, 20, 19]


Input:
matrix:
[[3,2,4,2,0,0,3,0,3,3], 
 [0,1,5,3,2,2,1,1,0,5], 
 [2,0,4,0,4,3,5,2,4,4], 
 [5,4,4,5,5,0,2,5,0,2], 
 [0,1,4,4,2,2,4,3,2,2], 
 [3,5,2,0,5,0,4,2,2,5], 
 [2,3,2,0,5,1,0,2,5,4], 
 [0,1,0,1,4,2,5,3,2,2], 
 [5,1,4,3,0,0,5,0,1,0], 
 [5,3,1,1,4,0,4,4,3,2]]
radius: 4
Expected Output:
[74, 71, 68]



Input:
matrix:
[[7,2,0,3,0,2,3,0,3,3], 
 [2,0,6,10,9,2,7,1,1,10], 
 [0,4,4,6,2,6,6,7,9,8], 
 [5,7,10,6,1,8,7,10,8,3], 
 [10,1,0,9,10,0,9,1,3,5], 
 [0,3,0,5,8,4,1,1,6,7], 
 [5,3,7,1,9,6,10,2,8,4], 
 [0,2,8,5,4,9,4,5,4,5], 
 [4,9,9,10,0,1,0,1,6,5], 
 [4,9,8,4,1,0,0,0,2,1]]
radius: 2
Expected Output:
[44, 40, 38]


Input:
matrix:
[[22,28,17,23,5,9,17,20,4,29,19,3,21,29,10], 
 [28,18,26,4,14,5,3,1,26,0,7,3,13,28,3], 
 [14,28,23,4,11,25,10,20,3,26,1,12,10,28,19], 
 [5,23,24,27,16,8,2,0,16,28,10,16,14,22,16], 
 [14,12,21,20,29,18,5,4,26,30,24,15,18,4,18], 
 [26,24,8,13,25,6,1,25,27,1,19,14,9,0,7], 
 [1,30,25,25,13,28,20,17,19,20]]
radius: 7
Expected Output:
[1298, 1278, 1274]



Input:
matrix:
[[54,20,47,57,48,29,51,35,59,3,31,24,67,3,0,51,31,42,53,39,36,54,40,70,23], 
[17,59,57,8,41,46,18,26,38,40,38,54,29,70,7,10,29,70,4,4,21,0,42,18,63], 
[37,42,44,53,60,25,54,52,59,46,35,38,41,31,33,62,19,44,13,5,57,41,22,46,57], 
[18,30,35,26,48,57,30,4,66,58,31,37,52,56,55,30,7,62,26,47,60,24,5,19,30]]
radius: 3
Expected Output:
[654, 643, 642]

标签： pythonalgorithmmatrix

解决方案

对于半径大于 2 的情况，您忘记添加一些数字。

看这个例子：

[0 0 1 0 0]
[0 1 1 1 0]
[1 1 1 1 1]
[0 1 1 1 0]
[0 0 1 0 0]

在这种情况下，必须计算所有 1 个数字。在您的代码中，您失去了位置 [1,1]、[1,3]、[3,1] 和 [3,3]。

[我认为] 我在这里用 GoLang 解决了这个问题：https ://github.com/gesiel/challenges/blob/main/best_rhombic_area.go

但是，如果我理解正确，我认为您的最后 2 次测试中缺少信息，因为半径不符合此要求：

1 ≤ 2·radius - 1 ≤ min(matrix.length, matrix[i].length).

推荐阅读