美团2024届秋招(8.12)【后端&数开&软件方向】
1、输入数组array和目标数n1,n2，判断数组[n1,n2]或[n2,n1]是否在array中
题目是简单题，限制时间复杂度。使用字典存储array中的数和下标，再使用n1查看其下标偏移后是否对应n2的下标
_ = input()
strNums = input().split()
dictNums = {}
for idx in range(len(strNums)):
strCurNum = strNums[idx]
if strCurNum not in dictNums:
dictNums[strCurNum] = [idx]
dictNums[strCurNum].append(idx)
nNum = input().split()
nNum1 = nNum[0]
nNum2 = nNum[1]
bFlag = True
for idx in dictNums[nNum1]:
if idx + 1 in dictNums[nNum2] or idx - 1 in dictNums[nNum2]:
print("Yes")
bFlag = False
break
if bFlag:
print("No")
2、环形道路中，使用array记录从i至i+1的路程（最后一位表示重点到起点距离）。输入n1、n2，求之间的最短路程
数学题，看出来只用求一边就行
_ = input()
arrnDis = input().split()
arrnTarget = input().split()
nStart = int(arrnTarget[0]) - 1
nEnd = int(arrnTarget[1]) - 1
if (nStart > nEnd):
nStart, nEnd = nEnd, nStart
for idx in range(len(arrnDis)):
arrnDis[idx] = int(arrnDis[idx])
nDisSum = sum(arrnDis)
nResDis = sum(arrnDis[nStart:nEnd])
print(min(nResDis, nDisSum - nResDis))
3、输入二维数组Matrix，横向或纵向切成两部分，使两部分数组之和的差最小
统计横向和纵向的一维数组之和，然后求两个一维数组的前缀和数组，方便表示两个子矩阵地数组之和大小
nLineNum = input()
nLineNum = nLineNum.split()
nLineNum = int(nLineNum[0])
matNum = []
for _ in range(nLineNum):
arrstrCurLine = input()
arrstrCurLine = arrstrCurLine.split()
arrnCurLine = [int(x) for x in arrstrCurLine]
matNum.append(arrnCurLine)
arrnRowSum = [sum(x) for x in matNum]
arrnColSum = [sum(x) for x in zip(*matNum)]
for idx in range(1, len(arrnRowSum)):
arrnRowSum[idx] += arrnRowSum[idx - 1]
for idx in range(1, len(arrnColSum)):
arrnColSum[idx] += arrnColSum[idx - 1]
nRes = arrnRowSum[-1]
for idx in range(len(arrnRowSum)):
nRes = min(abs(arrnRowSum[-1] - 2 * arrnRowSum[idx - 1]), nRes)
for idx in range(len(arrnColSum)):
nRes = min(abs(arrnColSum[-1] - 2 * arrnColSum[idx - 1]), nRes)
print(nRes)
4、输入字符串，将字符串重新排列成矩阵。如果字符相同则视为“连通”的，求重新排列后，最小连通块数量
例如aaaaabbbb可以重新排列成三行三列aaa aab bbb，可以看到只有左上角a和右下角b两个连通区域，所以结果是2。同理。caab不用重排，结果是3。
暴力，感觉题目对时间限制不严格。
nNum = int(input())
strStr = input()
def Visit(nRow, nCol, strStr, arrbVisited, nCurRow, nCurCol, cCurChar):
nCurIdx = nCurRow * nCol + nCurCol
if nCurRow < 0 or nCurRow >= nRow or nCurCol < 0 or nCurCol >= nCol or arrbVisited[nCurIdx] == True or strStr[nCurIdx] != cCurChar:
return
arrbVisited[nCurIdx] = True
Visit(nRow, nCol, strStr, arrbVisited, nCurRow + 1, nCurCol, cCurChar)
Visit(nRow, nCol, strStr, arrbVisited, nCurRow - 1, nCurCol, cCurChar)
Visit(nRow, nCol, strStr, arrbVisited, nCurRow, nCurCol + 1, cCurChar)
Visit(nRow, nCol, strStr, arrbVisited, nCurRow, nCurCol - 1, cCurChar)
def CountValue(strStr, arrbVisited, nRow, nCol):
nCount = 0
for nIdx in range(len(arrbVisited)):
if arrbVisited[nIdx] == False:
cCurChar = strStr[nIdx]
Visit(nRow, nCol, strStr, arrbVisited, nIdx // nCol, nIdx % nCol, cCurChar)
nCount += 1
return nCount
nRes = nNum
for nRow in range(1, nNum):
nCol = nNum / nRow
if nCol != int(nCol):
continue
arrbVisited = [False] * nNum
nRes = min(nRes, CountValue(strStr, arrbVisited, nRow, int(nCol)))
print(nRes)
5、给出一棵树，每个节点包含权重和颜色。初始时刻所有节点为白色。若两个节点的颜色均为白色，且权重之和恰为完全平方数，则可以同时染为红色。问至多可使几个节点染色。
输入样例：
8 # 节点数 4 16 16 4 3 4 3 3 # 节点权重 1 2 # 第1个节点和第2个节点相连 1 3 # 第1个节点和第3个节点相连 2 4 2 5 3 6 3 7 7 8
输出样例：6。即染色节点（下标从1开始）为（2、4）（1、3）（7、8）
暴力dfs，需要分别考虑当前节点被染色和当前节点不被染色两种情况。由于两种情况都考虑，所以遍历至某一结点时，当前节点内容和此前节点无关（注意不要回溯循环就行，因为题目说了是树，只要记录从哪一个节点遍历至当前节点从而避免循环就行），所以递归求解就行。
递归公式求以下两种情况最大值：
1、当前节点CurNode不和任何连通节点NextNode染色，对NextNode递归后结果之和
2、当前节点CurNode与某一节点NextColoredNode染色，同时其他节点NextUncoloredNode不染色，对NextColoredNode和NextUncoloredNode递归后结果之和
nNodeNum = int(input())
arrnValue = input().split()
arrnValue = [int(i) for i in arrnValue]
listlistnAdjust = [[] for i in range(len(arrnValue))]
arrbColored = [False] * nNodeNum
for _ in range(nNodeNum - 1):
strCurInput = input().split()
listlistnAdjust[int(strCurInput[0]) - 1].append(int(strCurInput[1]) - 1)
listlistnAdjust[int(strCurInput[1]) - 1].append(int(strCurInput[0]) - 1)
def issut(value1, value2):
res = (value1 * value2) ** 0.5
if res == int(res):
return True
else :
return False
def color(listlistnAdjust, arrnValue, arrbColored, nCurNodeIdx, nPreNodeIdx):
if nCurNodeIdx == nPreNodeIdx:
return 0
nRes = 0
arrnNextNodeIdx = listlistnAdjust[nCurNodeIdx]
arrnSutRes = [0 for _ in range(len(arrnNextNodeIdx))]
arrnRes = [0 for _ in range(len(arrnNextNodeIdx))]
for idx in range(len(arrnNextNodeIdx)):
nNextNodeIdx = arrnNextNodeIdx[idx]
if nPreNodeIdx == nNextNodeIdx:
continue
if arrbColored[nNextNodeIdx] == False and arrbColored[nCurNodeIdx] == False and issut(arrnValue[nNextNodeIdx], arrnValue[nCurNodeIdx]) :
arrbColored[nNextNodeIdx] = True
arrbColored[nCurNodeIdx] = True
arrnSutRes[idx] = 2 + color(listlistnAdjust, arrnValue, arrbColored, nNextNodeIdx, nCurNodeIdx)
arrbColored[nNextNodeIdx] = False
arrbColored[nCurNodeIdx] = False
arrnRes[idx] = color(listlistnAdjust, arrnValue, arrbColored, nNextNodeIdx, nCurNodeIdx)
nSumRes = sum(arrnRes)
for idx in range(len(arrnSutRes)):
nRes = max(nSumRes - arrnRes[idx] + arrnSutRes[idx], nRes)
return nRes
print(color(listlistnAdjust, arrnValue, arrbColored, 0, -1))
#美团2024秋招#
投递华为等公司8个岗位 >