考虑以下 N × N 矩阵 A 和仅包含正整数的 B:
- B 是从 A 通过对奇数求和创建的 在 A 中的
[i,j]位置相邻每个元素。 - 然后将每个计算的总和存储在 B 中相应的位置
[i,j]。
例如:
- 在位置
[3, 2]有4个奇数[3, 1, 5, 3]邻居A[3,2]。 - 这些相邻的奇数之和是
12， 存储在B[3,2]
此代码通过暴力破解，分别获取 9 个区域(即:顶部、底部、左侧、右侧、4 个角和内部)。
有没有更好的方法来解决这个问题？
from numpy import array,zeros,shape
def sum_neighbours(A):
A = array(A,int)
r,c = shape(A)
B = zeros(shape(A),int)
for i in range(r):
for j in range(c):
N_list_i = [0,-1,-1,-1,0,1,1,1,0] #[l,tl,t,tr,r,br,b,bl]
N_list_j = [-1,-1,0,1,1,1,0,-1,-1]
# innerSquares
if 1 <= i <= (r-2) and 1 <= j <= (r-2):
for k in range(len(N_list_j)-1):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#TopLeft
elif i==0 and j==0:
N_list_i = N_list_i[4:(4+3)]
N_list_j = N_list_j[4:(4+3)]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#BottomLeft
elif j==0 and i==(r-1):
N_list_i = N_list_i[2:(2+3)]
N_list_j = N_list_j[2:(2+3)]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#TopRight
elif i==0 and j == (r-1):
N_list_i = N_list_i[6:(6+3)]
N_list_j = N_list_j[6:(6+3)]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#BottomRight
elif i == (r-1) and j == (r-1):
N_list_i = N_list_i[0:(0+3)]
N_list_j = N_list_j[0:(0+3)]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#TopBorder
elif i==0 and j < (r-1):
N_list_i = N_list_i[4:(4+5)]
N_list_j = N_list_j[4:(4+5)]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#LeftBorder
elif j==0 and i < (r-1):
N_list_i = N_list_i[2:(2+5)]
N_list_j = N_list_j[2:(2+5)]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#BottomBorder
elif i==(r-1) and j < (r-1):
N_list_i = N_list_i[0:(0+5)]
N_list_j = N_list_j[0:(0+5)]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
#RightBorder
elif j==(r-1) and i < (r-1):
N_list_i = [1,1,0,-1,-1]
N_list_j = [0,-1,-1,-1,0]
for k in range(len(N_list_j)):
if A[i+N_list_i[k]][j+N_list_j[k]] %2 != 0:
B[i][j] += A[i+N_list_i[k]][j+N_list_j[k]]
return B
A = array([[3,2,8,1,1],
[1,2,4,1,1],
[7,3,4,1,8],
[1,8,0,6,4],
[5,6,5,3,8]])
请您参考如下方法:
就重构而言，您几乎肯定希望避免必须显式输入所有案例的“蛮力”:) @alexmcf 在上面解决了这个问题。
在概念上，您的方法直接遵循问题陈述:检查矩阵中每个数字的所有邻居并对所有奇数求和。这意味着您总是在进行检查和求和，即使矩阵中没有奇数也是如此。
作为替代方案:我们可以先遍历矩阵并识别奇数。然后，从一个空矩阵开始，我们只需将奇数添加到所有有效邻居。这节省了与矩阵中奇数的稀疏性成比例的工作。
import numpy as np
def find_offsets(row, col, size):
"""Return all valid pairs of offsets as [(row_offset, col_offset)...]."""
offsets = ((-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1))
return [(r_off, c_off) for r_off, c_off in offsets
if row + r_off >= 0 and row + r_off < size
if col + c_off >= 0 and col + c_off < size]
def find_odds(matrix, size):
"""Return all odd values in matrix as [(row_ind, col_ind, value)...]."""
return [(row, col, matrix[row][col])
for row in xrange(size)
for col in xrange(size)
if matrix[row][col] % 2 != 0]
def gen_matrix(source, size):
"""Filter source 2x2 matrix for odds and add each to valid neighbors."""
out = np.zeros((size, size), dtype=int)
# filter for location and value of all odd numbers
odds = find_odds(source, size)
for row, col, value in odds:
# add odd number to all valid neighbors (by finding valid offsets)
offsets = find_offsets(row, col, size)
for r_off, c_off in offsets:
out[row + r_off][col + c_off] += value
return out
def sum_neighbors():
"""Sum neighbors as described in problem."""
N = 5
A = [[3,2,8,1,1],
[1,2,4,1,1],
[7,3,4,1,8],
[1,8,0,6,4],
[5,6,5,3,8]]
return gen_matrix(A, N)
上面的代码运行速度大约是你的代码的两倍(为了进行同类比较，我在 iPython 中执行时调整了上面的代码，以便在两种情况下都提供相同的矩阵 A 作为参数):
In [19]: %timeit original.sum_neighbours(A)
1000 loops, best of 3: 195 µs per loop
In [20]: %timeit new.sum_neighbors(A)
10000 loops, best of 3: 84 µs per loop
