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的方式来搞:
- (root, me, p) 分别表示节点,自己是否被打开,父亲节点是否打开
- 然后枚举所有子节点的情况 ((0, 1), (1, 0), (1,1), (0, 0))
- 对于某些情况是不行的,比如自己父亲都没有打开,并且下面节点也没有打开。
- 还有就是如果子节点是null的话,那么是没有办法打开的。
这些东西最好使用数据驱动来表示,否则手写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