2020-03-25 阿里笔试题
题目来源与大神题解地址：https://blog.csdn.net/m0_38065572/article/details/105101287
https://www.nowcoder.com/discuss/391530?type=all&order=time&pos=&page=1
第一题：
给定一个数组n，然后给三个长度为n的数组，可以从这三个数组中选出一个长度为n的数组，第i个位置需要是从给出的三个数组第i个位置选择的，然后要求使这个数组后一项减前一项的绝对值之和最小。
输入示例：：
5
5 9 5 4 4
4 7 4 10 3
2 10 9 2 3
这里可以选择5 7 5 4 4，所以输出等于|7-5|+|5-7|+|4-5|+|4-4|=5。所以输出就是5。
————————————————
版权声明：本文为CSDN博主「August-us」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_38065572/article/details/105101287
大神题解：image.png
image.png
啰嗦预警：
- 看了几位大神都是先把输入的矩阵转置然后再利用dp，为什么转置暂时不懂，可能这样遍历起来方便？如果不转置就得先遍历列，再遍历行。
- 自己写的时候，把dp定义成二维数组了。但是可以注意到dp只与i-1的状态有关，所以优化成一维就可以
def fun1(nums,n):
pre = [0] * 3
nums = list(zip(nums[0],nums[1],nums[2])) #把输入矩阵做转置
for i in range(1,n):
cur = [0,0,0]
for j in range(3):
cur[j] = min (abs(nums[i][j] - nums[i-1][k]) +pre[k] for k in range(3))
pre = cur
return min(pre)
if __name__ == "__main__":
n = int(input())
nums = []
for i in range(3):
nums.append(list(map(int,input().split())))
print(fun1(nums,n))
第二题：
给出一个二维矩阵，这个矩阵的每一行和每一列都是一个独立的等差数列，其中一些数据缺失了，现在需要推理隐藏但是可以被唯一确定的数字，然后对输入的查询进行回答。
输入描述：
第一行，n,m,q分别表示矩阵的行数，列数和查询的条数。
接下来的n行，每行m个数表示这个矩阵，0表示缺失数据。
接下来q行，每行两个数字i,j表示对矩阵中第i行第j列的数字进行查询。
输出描述：
如果可以确定该位置的数字，则输出数字，如果不能确定则输出UNKNOWN。
输入示例：
2 3 6
1 0 3
0 0 0
1 1
1 2
1 3
2 1
2 2
2 3
输出示例：
1
2
3
Unknown
Unknown
Unknown
————————————————
版权声明：本文为CSDN博主「August-us」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_38065572/article/details/105101287
复习了一下等差数列：
大概思路是先对每行求公差，补每行；然后再对每列求公差，补每列。
大神代码（扫描行列思想）https://www.nowcoder.com/discuss/391530?type=all&order=time&pos=&page=1
解方程思想：https://www.nowcoder.com/discuss/392070?type=post&order=time&pos=&page=1
扫描行列思想，给大神代码加了注释：
def trans(A, n, m): # n行，m列 的矩阵A
# 把矩阵中为0的地方换成None #样例输入A= [[1,0,3], [0,0,0]] 变成[[1, None, 3], [None, None, None]]
for i in range(n):
for j in range(m):
if A[i][j] == 0: A[i][j] = None
# 求行的公差
for i in range(n):
has_num = set() # 集合
for j in range(m):
if A[i][j] is not None: # 元素不为None
has_num.add((i, j)) # 把不为空元素的坐标添加进集合
if len(has_num) == 2:
# 某一行只要有了2个不为None的元素，该行所有元素都可以确定
# list(has_num)：[(0, 0), (0, 2)]
pos1, pos2 = list(has_num) # pos1为(0, 0)
val1 = A[pos1[0]][pos1[1]] # 读取该行第一个不为0的元素的值
val2 = A[pos2[0]][pos2[1]] # 读取该行第一个不为0的元素的值
delta = (val2 - val1) // (pos2[1] - pos1[1]) # 求该行公差d
for k in range(m):#补上能补的值
if A[i][k] is None:
A[i][k] = val1 + delta * (k - pos1[1])
# 求列的公差
for j in range(m):
has_num = set() # 集合
for i in range(n):
if A[i][j] is not None: # 元素不为None
has_num.add((i, j)) # 把不为空元素的坐标添加进集合
if len(has_num) == 2:
pos1, pos2 = list(has_num) # pos1为(0, 0)
val1 = A[pos1[0]][pos1[1]] # 读取该列第一个不为0的元素的值
val2 = A[pos2[0]][pos2[1]] # 读取该列第2个不为0的元素的值
delta = (val2 - val1) // (pos2[0] - pos1[0]) # 求该列的公差d
for k in range(n):
if A[k][j] is None: #补上能补的值
A[k][j] = val1 + delta * (k - pos1[0])
if __name__ == "__main__":
n,m,q = map(int,input().split())
A = []
for i in range(n):
A.append(list(map(int,input().split())))
trans(A, n, m)
for j in range(q): # 查询的条数
x, y = map(int, input().split())
x -=1
y -=1
if A[x][y] :
print(A[x][y])
else:
print('Unknown')
但是！扫描行列可能不能解决这种矩阵：
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
所以又有大神给出了四元方程可解的思想：https://www.nowcoder.com/discuss/392070?type=post&order=time&pos=&page=1
（先让我看懂，py代码后续更）
