携程 算法 9.9笔试
一题没A的菜🐔希望各位A的大佬帮忙看看代码怎么改。。
1.矩阵（45%）
方法1和方法2应该都是超时了。。。
class Solution:
# 方法1
def maxRecArea_1(self, grid, k: int) -> int:
n, m = len(grid), len(grid[0])
res = float("-inf")
for i in range(n - k + 1):
for j in range(m - k + 1):
nums = [grid[i:i + k][a][j:j + k] for a in range(k)]
# print(nums)
res = max(res, sum(sum(nums[i]) for i in range(k)))
return res
# 方法2
def maxRecArea(self, grid: List[List[int]], k: int) -> int:
n, m = len(grid), len(grid[0])
res = float("-inf")
tmp = 0
for i in range(n - k + 1):
for j in range(m - k + 1):
for a in range(k):
for b in range(k):
tmp += grid[i + a][j + b]
# print(tmp)
res = max(res, tmp)
tmp = 0
return res
if __name__ == "__main__":
sl = Solution()
N, M, K = input().split()
N, M, K = int(N), int(M), int(K)
board = []
for _ in range(N):
tmp = list(map(int, input().split()))
board.append(tmp)
# print(board)
print(sl.maxRecArea(board, K)) 2.***甩卖 到期时间不知道怎么更新。。。
import collections
class Solution:
def operationGoods(self, arr):
n = len(arr)
capacity = 0 # 仓库容量
deadline = 0 # 有效期
res = []
cur_nums = 0
for i in range(n):
tmp = arr[i]
if tmp[0] == 1:
cur_nums = tmp[1]
capacity += cur_nums
deadline = tmp[2]
elif tmp[0] == 2:
if tmp[1] > capacity:
res.append("no")
else:
cur_nums = tmp[1]
capacity -= cur_nums
res.append("yes")
elif tmp[0] == 3:
deadline -= 1
if deadline == 0:
capacity -= cur_nums
elif tmp[0] == 4:
res.append(deadline)
return res
if __name__ == "__main__":
sl = Solution()
N = int(input())
nums = []
for _ in range(N):
nums.append(list(map(int, input().split())))
# print(nums)
ans = sl.operationGoods(nums)
for a in ans:
print(a) 3.黑白树 DFS
import collections
class Solution:
def __init__(self):
self.sum = 0
def sumSubTreeUniqueness(self, graph, nums):
n = len(graph) # 节点个数
def dfs(node: int, cur):
if not node:
return
if not graph.get(node, None):
res.append(0)
return
for next_node in graph[node]:
# print(next_node)
cur ^= nums[next_node - 1]
# print(next_node)
if cur:
# print("yes")
self.sum += 1
res.append(self.sum)
break
for next_node in graph[node]:
dfs(next_node, cur)
res = []
for i in range(1, n + 1):
dfs(i, nums[i - 1])
return res
if __name__ == "__main__":
sl = Solution()
N, index = input().split()
N, index = int(N), int(index)
Arrs = list(map(int, input().split()))
connections = []
for _ in range(N - 1):
connections.append(list(map(int, input().split())))
# print(connections)
Graphs = collections.defaultdict(list)
for c in range(N - 1):
Graphs[connections[c][0]].append(connections[c][1])
# Graphs[connections[c][1]].append(connections[c][0])
# print(Graphs)
ans = sl.sumSubTreeUniqueness(Graphs, Arrs)
# print(ans)
for a in ans:
print(a, end=" ") 感觉题目思路都不是很难想，但就是过不了。。。
