携程 算法 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=" ")
感觉题目思路都不是很难想,但就是过不了。。。