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

题目-01 化学反应

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

#平衡树
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

#大根堆
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的区间。

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的子树。

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即可。）

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