1. 开幕式焰火
「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。
给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色
示例 1：
输入：root = [1,3,2,1,null,2]
输出：3
解释：焰火中有 3 个不同的颜色，值分别为 1、2、3
示例 2：
输入：root = [3,3,3]
输出：1
解释：焰火中仅出现 1 个颜色，值为 3
提示：
1 <= 节点个数 <= 1000
1 <= Node.val <= 1000
class Solution:
def numColor(self, root: TreeNode) -> int:
res = set()
def dfs(node):
if node:
res.add(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return len(res)
2. 自行车炫技赛场
「力扣挑战赛」中 N*M 大小的自行车炫技赛场的场地由一片连绵起伏的上下坡组成，场地的高度值记录于二维数组 terrain 中，场地的减速值记录于二维数组 obstacle 中。
- 若选手骑着自行车从高度为
h1且减速值为o1的位置到高度为h2且减速值为o2的相邻位置，速度变化值为h1-h2-o2（负值减速，正值增速）。
选手初始位于坐标 position 处且初始速度为 1`，请问选手可以刚好到其他哪些位置时速度依旧为 1。请以二维数组形式返回这些位置。若有多个位置则按行坐标升序排列，若有多个位置行坐标相同则按列坐标升序排列。
注意： 骑行过程中速度不能为零或负值.
示例 1：
输入：position = [0,0], terrain = [[0,0],[0,0]], obstacle = [[0,0],[0,0]]
输出：[[0,1],[1,0],[1,1]]
解释：
由于当前场地属于平地，根据上面的规则，选手从[0,0]的位置出发都能刚好在其他处的位置速度为 1。
示例 2：
输入：position = [1,1], terrain = [[5,0],[0,6]], obstacle = [[0,6],[7,0]]
输出：[[0,1]]
解释：
选手从 [1,1] 处的位置出发，到 [0,1] 处的位置时恰好速度为 1。
提示：
1 <= n <= 100
1 <= m <= 100
0 <= terrain[i][j], obstacle[i][j] <= 100
class Solution:
def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:
rows, cols = len(terrain), len(terrain[0])
vis = set()
res = set()
def dfs(i, j, v):
if (i,j,v) not in vis: #出口1, vis
vis.add((i,j,v))
else:
return
if v <= 0: return # 出口2, v
if v == 1: # 出口3, v == 1
if [i,j] != position:
res.add((i, j))
for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
if 0<=x<rows and 0<=y<cols:
dfs(x, y, v + terrain[i][j] - terrain[x][y] - obstacle[x][y])
dfs(position[0], position[1], 1)
res = sorted(list(res))
return res
3. 志愿者调配
「力扣挑战赛」有 n 个比赛场馆（场馆编号从 0 开始），场馆之间的通道分布情况记录于二维数组 edges 中，edges[i]= [x, y] 表示第 i 条通道连接场馆 x 和场馆 y(即两个场馆相邻)。初始每个场馆中都有一定人数的志愿者（不同场馆人数可能不同），后续 m 天每天均会根据赛事热度进行志愿者人数调配。调配方案分为如下三种：
- 将编号为
idx的场馆内的志愿者人数减半； - 将编号为
idx的场馆相邻的场馆的志愿者人数都加上编号为idx的场馆的志愿者人数； - 将编号为
idx的场馆相邻的场馆的志愿者人数都减去编号为idx的场馆的志愿者人数。
所有的调配信息记录于数组 plans 中，plans[i] = [num,idx] 表示第 i 天对编号 idx 的场馆执行了第 num 种调配方案。
在比赛结束后对调配方案进行复盘时，不慎将第 0 个场馆的最终志愿者人数丢失，只保留了初始所有场馆的志愿者总人数 totalNum ，以及记录了第 1 ~ n-1 个场馆的最终志愿者人数的一维数组 finalCnt。请你根据现有的信息求出初始每个场馆的志愿者人数，并按场馆编号顺序返回志愿者人数列表。
示例 1：
输入：
finalCnt = [1,16], totalNum = 21, edges = [[0,1],[1,2]], plans = [[2,1],[1,0],[3,0]]
输出：[5,7,9]
示例 2 ：
输入：
finalCnt = [4,13,4,3,8], totalNum = 54, edges = [[0,3],[1,3],[4,3],[2,3],[2,5]], plans = [[1,1],[3,3],[2,5],[1,0]]
输出：[10,16,9,4,7,8]
提示：
2 <= n <= 5*10^4
1 <= edges.length <= min((n * (n - 1)) / 2, 5*10^4)
0 <= edges[i][0], edges[i][1] < n
1 <= plans.length <= 10
1 <= plans[i][0] <=3
0 <= plans[i][1] < n
finalCnt.length = n-1
0 <= finalCnt[i] < 10^9
0 <= totalNum < 5*10^13
测试用例对的，提交错了。。。
# ln(10^9) = 20.7
class Solution:
def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:
d = defaultdict(list) #建立关系图
for x, y in edges:
d[x].append(y)
d[y].append(x)
def check(num):
res = [num] + finalCnt[:]
for kind, gym in plans[::-1]: #开始反推
if kind == 3:
for neighbor in d[gym]:
res[neighbor] += res[gym]
elif kind == 2:
for neighbor in d[gym]:
res[neighbor] -= res[gym]
else:
res[gym] *= 2
return res
flag = True if check(100) < check(200) else False # 单调递增？
l, r = 0, 10**9
while l <= r:
mid = (l+r)//2
if sum(check(mid)) < totalNum:
if flag:
l = mid + 1
else:
r = mid - 1
elif sum(check(mid)) == totalNum:
return check(mid)
else:
if flag:
r = mid - 1
else:
l = mid + 1
啊。。。flag 那里应该是 sum(check(100)), 改之后就对了
问题不大，至少我学会了对结果二分查找，或是对可能值的枚举
# 做法二：再维持一个变量的数组
class Solution:
def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:
d = defaultdict(list) #建立关系图
for x, y in edges:
d[x].append(y)
d[y].append(x)
n = len(finalCnt) + 1
a = [1] + [0]*(n-1) # 记录各项的 x 系数
b = [0] + finalCnt[:]
for kind, gym in plans[::-1]:
if kind == 1:
a[gym] *= 2
b[gym] *= 2
elif kind == 2:
for neighbor in d[gym]:
a[neighbor] -= a[gym]
b[neighbor] -= b[gym]
else:
for neighbor in d[gym]:
a[neighbor] += a[gym]
b[neighbor] += b[gym]
x = (totalNum-sum(b))//sum(a)
return [a[i]*x + b[i] for i in range(n)]
牛啊，一直绕进了解方程的胡同，原来如此
4. 入场安检
0-1 背包
# 如何满足题意？
# ：将编号 k 以前的都压入栈底
# 栈为 1， 队列为 0
class Solution:
def securityCheck(self, capacities: List[int], k: int) -> int:
mod = 1000000007
dp = [1]+[0]*k
for cap in [c-1 for c in capacities]: # cap 为背包大小
for j in range(k, cap-1, -1):
dp[j] += dp[j-cap]
dp[j] %= mod
return dp[k]
