复盘｜天堂硅谷·数字经济算法编程大赛

题目-01 化学反应

【模拟】按题意模拟（可以用大根堆或者平衡树），每次找两个最大的出来，直到没有剩余或只剩一个。

1 2 3 4 5 6 7 8 9	#平衡树 from sortedcontainers import SortedList class Solution: def lastMaterial(self, material: List[int]) -> int: s = SortedList(material) while len(s) > 1: a, b = s.pop(), s.pop() if a != b: s.add(a - b) return s[0] if s else 0

1 2 3 4 5 6 7 8 9	#大根堆 class Solution: def lastMaterial(self, material: List[int]) -> int: h = [-m for m in material] heapify(h) while len(h) > 1: a, b = heappop(h), heappop(h) if a != b: heappush(h, a - b) return -h[0] if h else 0

题目-02 销售出色区间

【前缀和 + 单调栈】把销售产品>8的天数当成增1，<=8的天数当成减1，判断的同时把前缀和算出来，寻找最长presum[i] - presum[j] >0的区间。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution: def longestESR(self, sales: List[int]) -> int: n = len(sales) presum = [0] * (n + 1) for i in range(1, n + 1): presum[i] = presum[i - 1] + 1 if sales[i - 1] > 8 else presum[i - 1] - 1 st = [0] for i in range(1, n + 1): if presum[i] < presum[st[-1]]: st.append(i) j = n ans = 0 while j > ans: while st and presum[j] > presum[st[-1]]: ans = max(ans, j - st[-1]) st.pop() j -= 1 return ans

题目-03 重复的彩灯树

【二叉树的序列化】在先序的位置递归序列化每棵树，每次用哈希表计数并找到重复次数为2的子树。

1 2 3 4 5 6 7 8 9 10 11 12	class Solution: def lightDistribution(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: d, res = defaultdict(int), [] def dfs(node): if not node: return ' ' left, right = dfs(node.left), dfs(node.right) subTree = left + ',' + right + ',' + str(node.val) if d[subTree] == 1: res.append(node) d[subTree] += 1 return subTree dfs(root) return res

题目-04 补给覆盖

【后序遍历递归】对于每个root，一共有三种状态，状态0：没覆盖其他节点也没被覆盖；状态1：被覆盖了；状态2：覆盖其他节点。（空节点不需要覆盖别人也不需要被覆盖，默认状态1即可。）

1 2 3 4 5 6 7 8 9 10 11 12 13 14	class Solution: def minSupplyStationNumber(self, root: Optional[TreeNode]) -> int: ans = 0 def dfs(node): if not node: return 1 left, right = dfs(node.left), dfs(node.right) nonlocal ans if left == 0 or right == 0: ans += 1 return 2 if left == 2 or right == 2: return 1 if left == 1 and right == 1: return 0 if dfs(root) == 0: ans += 1 return ans