京东算法笔试编程题

迷宫问题：把传入的矩阵matrix，扩成每行每列各三个matrix（共9个）的大矩阵，从最左上角的小matrix中的‘S’出发，沿可走的路径寻找，如果能找找到其它的‘S’，则是通的，s出发就能到无穷多位置 import numpy as np def s_location(matrix):#定位S在矩阵中位置     for i in range(len(matrix)):         if 'S' in matrix[i]:             j = matrix[i].index('S')             return [i, j] def findanother_S(matrix, i, j):#在大矩阵中沿可通过路径寻找其它S，若找到则说明是连通的     if i<0 or i>=len(matrix) or j<0 or j>= len(matrix) or matrix[i][j] == '#':         return False     if matrix[i][j] == 'S':         return True     if findanother_S(matrix, i + 1, j):         print(i+1, j)         return True     if findanother_S(matrix, i - 1, j):         print(i-1, j)         return True     if findanother_S(matrix, i, j + 1):         print(i, j+1)         return True     if findanother_S(matrix, i, j - 1):         print(i, j-1)         return True     return False def isok(matrix):#判断matrix矩阵中S是否可以到达无穷多位置     i, j = s_location(matrix)  # i,j     matrix = np.array(matrix)#把matrix变成每行、每列各3个（共九个）matrix的大矩阵     matrix = np.concatenate([matrix] * 3, axis=1)     matrix = np.concatenate([matrix] * 3, axis=0)     matrix[i][j] = '#'     print(matrix)     if findanother_S(matrix, i + 1, j):         print(i+1,j)         return True     if findanother_S(matrix, i - 1, j):         print(i-1,j)         return True     if findanother_S(matrix, i, j + 1):         print(i,j+1)         return True     if findanother_S(matrix, i, j - 1):         print(i,j-1)         return True     print(i,j)     return False if __name__== '__main__':     matrix1 = [['S', '#'], ['#', '.']]     matrix2 = [['.', '.', '.'], ['#', '#', '#'], ['#', 'S', '#']]     result = isok(matrix2)     print(result)

大佬得到面试通知了吗

消消乐问题： 用一个感染函数，一个标志矩阵（初始值为1），把与初始点相同且连成一片的位置，对应在标志矩阵的位置改为0，然后与初始矩阵进行对应位置相乘的操作，则初始矩阵被消除的位置变为0，其他位置数字保持不变，然后执行下沉操作，对下沉完成的矩阵继续执行开始的消除操作 开始写的版本是贪心的，就是每次消除最大数量的点，但后来感觉不合适，不是最优解。后来改成每次从上到下，从左到右顺序‘感染’，只要凑够三个就删除 从上到下，从左到右顺序消除： import numpy as np class returndata():#每个点给上一个点返回的信息（与本点相邻且相同的点有多少个？）     subnum = 0     def __init__(self,subnum):         self.subnum = subnum #感染函数（给定flaglist矩阵，把能连城一片的点的位置，对应在flaglist中表为0） def infect(i, j, number, checkerboard, flagList):     if i<0 or i >= len(checkerboard) or j<0 or j>= len(checkerboard[0]) or checkerboard[i][j] != number or \     flagList[i][j]==0 or number == 0:         return returndata(0)     flagList[i][j] = 0     sumsubnum = returndata(1)     #从上下左右四个方向继续“感染”     a = infect(i + 1, j, checkerboard[i][j], checkerboard, flagList)     b = infect(i - 1, j, number, checkerboard, flagList)     c = infect(i, j + 1, checkerboard[i][j], checkerboard, flagList)     d = infect(i, j - 1, number, checkerboard, flagList)     sumsubnum.subnum += a.subnum+b.subnum+c.subnum+d.subnum     return sumsubnum#返回值为 从此点出发，最多能删除的点的个数 #下沉函数，把不是0的数都下沉下去 def down(matrix):     for i in range(len(matrix)-1,0,-1):         for j in range(len(matrix[0])):             if matrix[i][j]==0:                 for h in range(i-1,-1,-1):                     if matrix[h][j]!=0:                         matrix[i][j] = matrix[h][j]                         matrix[h][j] = 0     return matrix checkerboard = np.array([[3, 1, 2, 1, 1, ], \                          [1, 1, 1, 1, 3], \                          [1, 1, 1, 1, 1], \                          [1, 1, 1, 1, 1], \                          [3, 1, 2, 2, 2]]) row = checkerboard.shape[0]  # 获取行数 col = checkerboard.shape[1]  # 获取列数 flagList = [[1] * col for i in range(row)]  # 创建标志矩阵，初始值为1，能删除的位置变为0 flagList = np.array(flagList) #print(checkerboard) for i in range(row):     for j in range(col):         flagList = [[1] * col for k in range(row)]#消除矩阵         flagList = np.array(flagList)         result = infect(i, j, checkerboard[i][j], checkerboard, flagList)         if result.subnum>=3:#如果相同点连通个数大于等于3，则进行消除操作             checkerboard = checkerboard*flagList             checkerboard = down(checkerboard)             print(checkerboard) count = 0#最后剩下的不能删除的点的个数 for lst in checkerboard:     for x in lst:         if x!=0:             count+=1 print(count) 贪心版本： import numpy as np class returndata():#返回的信息（与本点相邻的点有多少个？）     subnum = 0     def __init__(self,subnum):         self.subnum = subnum def infect(i, j, number, checkerboard, flagList):#感染函数     if i<0 or i >= len(checkerboard) or j<0 or j>= len(checkerboard[0]) or checkerboard[i][j] != number or \     flagList[i][j]==0 or number == 0:         return returndata(0)     flagList[i][j] = 0     sumsubnum = returndata(1)     a = infect(i + 1, j, checkerboard[i][j], checkerboard, flagList)     b = infect(i - 1, j, number, checkerboard, flagList)     c = infect(i, j + 1, checkerboard[i][j], checkerboard, flagList)     d = infect(i, j - 1, number, checkerboard, flagList)     sumsubnum.subnum += a.subnum+b.subnum+c.subnum+d.subnum     return sumsubnum def down(matrix):#把不是0的都沉下去     for i in range(len(matrix)-1,0,-1):         for j in range(len(matrix[0])):             if matrix[i][j]==0:                 for h in range(i-1,-1,-1):                     if matrix[h][j]!=0:                         matrix[i][j] = matrix[h][j]                         matrix[h][j] = 0     return matrix checkerboard = np.array([[3, 1, 2, 1, 1, ], \                          [1, 1, 1, 1, 3], \                          [1, 1, 1, 1, 1], \                          [1, 1, 1, 1, 1], \                          [3, 1, 2, 2, 2]]) row = checkerboard.shape[0]  # 获取行数 col = checkerboard.shape[1]  # 获取列数 flagList = [[1] * col for i in range(row)] flagList = np.array(flagList) print(checkerboard) dic = {}#key:可删除点的个数 value：对应个数的标志矩阵（0 1矩阵） while True:     dic.clear()     for i in range(row):         for j in range(col):             flagList = [[1] * col for k in range(row)]#消除矩阵             flagList = np.array(flagList)             result = infect(i, j, checkerboard[i][j], checkerboard, flagList)             if result.subnum>=3:                 dic[result.subnum] = flagList     if dic=={}:#结束条件（不能再消除的时候结束）         break     #if max(dic.keys())<3:     #    break     maxdeletematrix = dic.get(max(dic.keys()))     checkerboard = checkerboard*maxdeletematrix     checkerboard = down(checkerboard)     print(checkerboard) count = 0#最后剩下的不能删除的点的个数 for lst in checkerboard:     for x in lst:         if x!=0:             count+=1 print(count)

我也参加了，表示没做出来

大佬还记得输入输出是什么吗？

感谢大佬分享解题思路

大佬面试过了没？