阿里巴巴

题目要求：

阿里笔试前的编程测验题，具体的题目要求很长，我已经给忘记了，大概意思就是，给你一个由0和1组成的矩阵，例如下面这个矩阵：

maps = [[1, 1, 0, 1, 1, 0, 0],[1, 0, 1, 1, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1],[0, 1, 0, 1, 0, 1, 1],[1, 0, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 0, 1]]

让你选择一个位置，这个位置必须是1，而且从这个位置出发（上，下，左，右）可以打到飞机数最多，1代表飞机，0代表陨石（不可到达），输出的结果要求是一个坐标信息，如果存在相同的结果，应该都输出出来。

题目分析：

很显然，使用暴力解法时间复杂度为O(n3)， 在这里采用动态规划思想，时间复杂度为O(n2)，从上下左右四个方向出发，分别代表一个单维的数组进行dp操作。

Python3 实现：

# @Time   :2018/5/8
# @Author :LiuYinxingmaps = [[1, 1, 0, 1, 1, 0, 0],[1, 0, 1, 1, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1],[0, 1, 0, 1, 0, 1, 1],[1, 0, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 0, 1]]
n, m = 6, 7  # 行列dp1 = [[0]*m for _ in range(n)]  # 上
dp2 = [[0]*m for _ in range(n)]  # 右
dp3 = [[0]*m for _ in range(n)]  # 下
dp4 = [[0]*m for _ in range(n)]  # 左for i in range(m): dp1[0][i], dp3[n-1][i] = maps[0][i], maps[n-1][i]  # 初始化
for i in range(n): dp2[i][m-1], dp4[i][0] = maps[i][m-1], maps[i][0]for i in range(n):  # 从左--->右计算for j in range(1, m):dp4[i][j] = 0 if maps[i][j] == 0 else dp4[i][j-1] + maps[i][j]for i in range(n):  # 从右--->左计算for j in range(m-2, -1, -1):dp2[i][j] = 0 if maps[i][j] == 0 else dp2[i][j+1] + maps[i][j]for j in range(m):  # 从上--->下计算for i in range(1, n):dp1[i][j] = 0 if maps[i][j] == 0 else dp1[i-1][j] + maps[i][j]for j in range(m):  # 从下--->上计算for i in range(n-2, -1, -1):dp3[i][j] = 0 if maps[i][j] == 0 else dp3[i+1][j] + maps[i][j]idm = 0
pathid = []
for i in range(n):  # 获取结果for j in range(m):dp1[i][j] = dp1[i][j] + dp2[i][j] + dp3[i][j] + dp4[i][j] - (3*maps[i][j])if dp1[i][j] > idm:  # 更新最大值idm, pathid= dp1[i][j], [[i,j]]elif dp1[i][j] == idm:  # 保留最大值pathid.append([i,j])print(pathid)

程序简化一下：

# @Time   :2018/5/8
# @Author :LiuYinxingmaps = [[1, 1, 0, 1, 1, 0, 0],[1, 0, 1, 1, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1],[0, 1, 0, 1, 0, 1, 1],[1, 0, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 0, 1]]
n, m = 6, 7  # 行列dp1 = [[0]*m for _ in range(n)]  # 上
dp2 = [[0]*m for _ in range(n)]  # 右
dp3 = [[0]*m for _ in range(n)]  # 下
dp4 = [[0]*m for _ in range(n)]  # 左for i in range(m): dp1[0][i], dp3[n-1][i] = maps[0][i], maps[n-1][i]  # 初始化
for i in range(n): dp2[i][m-1], dp4[i][0] = maps[i][m-1], maps[i][0]for i in range(n):  # 一行一行的计算for j in range(1, m):  # 从左--->右计算dp4[i][j] = [0, dp4[i][j-1] + maps[i][j]][maps[i][j]]for j in range(m-2, -1, -1):  # 从右--->左计算dp2[i][j] = [0, dp2[i][j+1] + maps[i][j]][maps[i][j]]for j in range(m):  # 一列一列的计算for i in range(1, n):  # 从上--->下计算dp1[i][j] = [0, dp1[i-1][j] + maps[i][j]][maps[i][j]]for i in range(n-2, -1, -1):  # 从下--->上计算dp3[i][j] = [0, dp3[i+1][j] + maps[i][j]][maps[i][j]]idm = 0
pathid = []
for i in range(n):  # 获取结果for j in range(m):dp1[i][j] = dp1[i][j] + dp2[i][j] + dp3[i][j] + dp4[i][j] - (3*maps[i][j])if dp1[i][j] > idm:  # 更新最大值idm, pathid= dp1[i][j], [[i,j]]elif dp1[i][j] == idm:  # 保留最大值pathid.append([i,j])print(pathid)

发现问题，可以留言指教哦。小白一个。

阿里巴巴

题目要求：

阿里笔试前的编程测验题，具体的题目要求很长，我已经给忘记了，大概意思就是，给你一个由0和1组成的矩阵，例如下面这个矩阵：

maps = [[1, 1, 0, 1, 1, 0, 0],[1, 0, 1, 1, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1],[0, 1, 0, 1, 0, 1, 1],[1, 0, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 0, 1]]

让你选择一个位置，这个位置必须是1，而且从这个位置出发（上，下，左，右）可以打到飞机数最多，1代表飞机，0代表陨石（不可到达），输出的结果要求是一个坐标信息，如果存在相同的结果，应该都输出出来。

题目分析：

很显然，使用暴力解法时间复杂度为O(n3)， 在这里采用动态规划思想，时间复杂度为O(n2)，从上下左右四个方向出发，分别代表一个单维的数组进行dp操作。

Python3 实现：

# @Time   :2018/5/8
# @Author :LiuYinxingmaps = [[1, 1, 0, 1, 1, 0, 0],[1, 0, 1, 1, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1],[0, 1, 0, 1, 0, 1, 1],[1, 0, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 0, 1]]
n, m = 6, 7  # 行列dp1 = [[0]*m for _ in range(n)]  # 上
dp2 = [[0]*m for _ in range(n)]  # 右
dp3 = [[0]*m for _ in range(n)]  # 下
dp4 = [[0]*m for _ in range(n)]  # 左for i in range(m): dp1[0][i], dp3[n-1][i] = maps[0][i], maps[n-1][i]  # 初始化
for i in range(n): dp2[i][m-1], dp4[i][0] = maps[i][m-1], maps[i][0]for i in range(n):  # 从左--->右计算for j in range(1, m):dp4[i][j] = 0 if maps[i][j] == 0 else dp4[i][j-1] + maps[i][j]for i in range(n):  # 从右--->左计算for j in range(m-2, -1, -1):dp2[i][j] = 0 if maps[i][j] == 0 else dp2[i][j+1] + maps[i][j]for j in range(m):  # 从上--->下计算for i in range(1, n):dp1[i][j] = 0 if maps[i][j] == 0 else dp1[i-1][j] + maps[i][j]for j in range(m):  # 从下--->上计算for i in range(n-2, -1, -1):dp3[i][j] = 0 if maps[i][j] == 0 else dp3[i+1][j] + maps[i][j]idm = 0
pathid = []
for i in range(n):  # 获取结果for j in range(m):dp1[i][j] = dp1[i][j] + dp2[i][j] + dp3[i][j] + dp4[i][j] - (3*maps[i][j])if dp1[i][j] > idm:  # 更新最大值idm, pathid= dp1[i][j], [[i,j]]elif dp1[i][j] == idm:  # 保留最大值pathid.append([i,j])print(pathid)

程序简化一下：

# @Time   :2018/5/8
# @Author :LiuYinxingmaps = [[1, 1, 0, 1, 1, 0, 0],[1, 0, 1, 1, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1],[0, 1, 0, 1, 0, 1, 1],[1, 0, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 0, 1]]
n, m = 6, 7  # 行列dp1 = [[0]*m for _ in range(n)]  # 上
dp2 = [[0]*m for _ in range(n)]  # 右
dp3 = [[0]*m for _ in range(n)]  # 下
dp4 = [[0]*m for _ in range(n)]  # 左for i in range(m): dp1[0][i], dp3[n-1][i] = maps[0][i], maps[n-1][i]  # 初始化
for i in range(n): dp2[i][m-1], dp4[i][0] = maps[i][m-1], maps[i][0]for i in range(n):  # 一行一行的计算for j in range(1, m):  # 从左--->右计算dp4[i][j] = [0, dp4[i][j-1] + maps[i][j]][maps[i][j]]for j in range(m-2, -1, -1):  # 从右--->左计算dp2[i][j] = [0, dp2[i][j+1] + maps[i][j]][maps[i][j]]for j in range(m):  # 一列一列的计算for i in range(1, n):  # 从上--->下计算dp1[i][j] = [0, dp1[i-1][j] + maps[i][j]][maps[i][j]]for i in range(n-2, -1, -1):  # 从下--->上计算dp3[i][j] = [0, dp3[i+1][j] + maps[i][j]][maps[i][j]]idm = 0
pathid = []
for i in range(n):  # 获取结果for j in range(m):dp1[i][j] = dp1[i][j] + dp2[i][j] + dp3[i][j] + dp4[i][j] - (3*maps[i][j])if dp1[i][j] > idm:  # 更新最大值idm, pathid= dp1[i][j], [[i,j]]elif dp1[i][j] == idm:  # 保留最大值pathid.append([i,j])print(pathid)

发现问题，可以留言指教哦。小白一个。