首页 > 携程9.9算法岗笔试AK代码
头像
炼丹师0
编辑于 2021-09-09 21:03
+ 关注

携程9.9算法岗笔试AK代码

感谢携程三道medium,在动辄hard,acm题的笔试里面简直一股清流
第一题最大方阵和:
思路:二维前缀和
x = input().split()
x = list(map(int,x))
n,m,k = x[0],x[1],x[2]
matrix = []
for _ in range(n):
    x = input().split()
    x = list(map(int,x))
    matrix.append(x)
res = 0 
prefix = [[0] * (m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]
res = 0
for i in range(k,n+1):
    for j in range(k,m+1):
        res = max(res,prefix[i][j] - prefix[i][j-k] - prefix[i-k][j] + prefix[i-k][j-k])
print(res)


第二题,模拟四种状态
思路:直接模拟即可
import heapq
n = int(input())

stack = []
num = 0
def put(x,y):
    heapq.heappush(stack,[y,x])
    global num
    num += x
def get(x):
    global num
    if x > num:return 'no'
    num -= x
    while stack and stack[0][1] <= x:
        x -= heapq.heappop(stack)[1]
    if x:
        stack[0][1] -= x 
    return 'yes'
def nextday():
    global num 
    while stack and stack[0][0] == 1:
        num -= heapq.heappop(stack)[1]
         
    for i in range(len(stack)):
        stack[i][0] -= 1
def getnearst():
    if not stack:return 0
    return stack[0][0]

for i in range(n):
    x = input().split()
    x = list(map(int,x))
    if x[0] == 1:
        put(x[1],x[2])
    elif x[0] == 2:
        print(get(x[1]))
    elif x[0] == 3:
        nextday()
    elif x[0] == 4:
        print(getnearst())

第三题,黑白树
思路:带备忘录的dfs
class Node:
    def __init__(self,color):
        self.child = []
        self.color = color

x = input().split()
x = list(map(int,x))
n,root = x[0],x[1]
cache = {}
 
color = input().split()
color = list(map(int,color))
for i in range(len(color)):
    cache[i+1] = Node(color[i])
while True:
    try:
        x = input().split()
        x = list(map(int,x))
        cache[x[0]].child.append(x[1])
    except:
        break
memo = [0] * (n+1)
def dfs(i):
    if memo[i]!=0:
        return memo[i]
    res = 0 
    for node in cache[i].child:
        if cache[node].color != cache[i].color:
            res += 1
        res += dfs(node)
    memo[i] = res
    return res
dfs(root)
for i in range(1,n+1):
    print(memo[i])




全部评论

(10) 回帖
加载中...
话题 回帖