携程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]) 