LeetCode 数字经济算法编程大赛 2022

https://leetcode.cn/contest/hhrc2022/

4道题目，我看排行上有人5分钟就搞完了，觉得应该是比较水的比赛。

但是我实际做起来的时候发现还有点难的，可能是之前没有搞过吧。所以很多事情还是不能想当然，按照佛经的说法就是不能住相。

我觉得这4题出了第一题之外其他题目都可以拿来说说，每题都有点启发性。

https://leetcode.cn/contest/hhrc2022/problems/0Wx4Pc/

这题初看上上去像是求最大连续和的问题，但是这里并不是要求最大值，而是求解最大区间，直接套用之前的方法是不行的。

正确的做法是，预先计算好大约等于某个累计值的最大偏移，然后在遍历的时候到某个下标，假设累计值是X那么就寻找之后大于X的最远偏移。 

class Solution:
    def longestESR(self, sales: List[int]) -> int:
        xs = [1 if x > 8 else -1 for x in sales]
        n = len(xs)
        pos = [-1] * (2 * n + 2)

        acc = 0
        for i in range(n):
            acc += xs[i]
            pos[(acc + n)] = i

        for i in reversed(range(2 * n + 1)):
            pos[i] = max(pos[i], pos[i+1])

        ans = 0
        acc = 0
        for i in range(n):
            j = pos[(acc + 1 + n)]
            dist = (j - i + 1)
            ans = max(ans, dist)
            acc += xs[i]
        return ans

https://leetcode.cn/contest/hhrc2022/problems/VAc7h3/

之前没有太碰到过这种模式匹配的问题，所以一直想使用整数hash的方式来搞。但是选好hash这件事情比较难，很容易选错出现冲突，所以还是直接使用字符串比较简单。 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def lightDistribution(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        repo = set()
        ans = {}

        def walk(root):
            if root is None:
                return ''
            a = walk(root.left)
            b = walk(root.right)
            h = '%s,%s,%s' % (root.val, a, b)
            if h not in repo:
                repo.add(h)
            elif h not in ans:
                ans[h] = root
            return h

        walk(root)
        return list(ans.values())

https://leetcode.cn/contest/hhrc2022/problems/wFtovi/

这题我看不少人直接使用DFS, 而且写法都大同小异，似乎是什么套路，我还是使用DP的方式来搞:

这些东西最好使用数据驱动来表示，否则手写if-else很容易出错。 

class Solution:
    def minSupplyStationNumber(self, root: Optional[TreeNode]) -> int:

        import functools
        @functools.cache
        def search(root, me, p):
            if root is None:
                return 0

            ans = 10000
            lr = ((0, 0), (0, 1), (1, 0), (1, 1))

            def bad(l, r):
                if (l, r, me, p) == (0, 0, 0, 0):
                    return True
                if l and root.left is None:
                    return True
                if r and root.right is None:
                    return True
                return False

            for l, r in lr:
                if bad(l, r): continue
                a = search(root.left, l, me) + l
                b = search(root.right, r, me) + r
                ans = min(ans, a + b)
            return ans

        ans = search(root, 1, 0) + 1
        if root.left or root.right:
            a = search(root, 0, 0)
            ans = min(ans, a)
        return ans