「力扣挑战赛」有 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。
请你根据现有的信息求出初始每个场馆的志愿者人数,并按场馆编号顺序返回志愿者人数列表。
注意:测试数据保证当某场馆进行第一种调配时,该场馆的志愿者人数一定为偶数;
测试数据保证当某场馆进行第三种调配时,该场馆的相邻场馆志愿者人数不为负数;
测试数据保证比赛开始时每个场馆的志愿者人数都不超过 10^9;
测试数据保证给定的场馆间的道路分布情况中不会出现自环、重边的情况。
示例 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
1、模拟-解方程;时间复杂度O(n),空间复杂度O(n)
type Node struct {
a float64 // 未知final[0] x的系数
b int // 已知的系数
}
func volunteerDeployment(finalCnt []int, totalNum int64, edges [][]int, plans [][]int) []int {
n := len(finalCnt) + 1
arr := make([][]int, n) // 邻接表
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
arr[a] = append(arr[a], b)
arr[b] = append(arr[b], a)
}
final := make([]Node, 0)
final = append(final, Node{a: 1, b: 0}) // final为最终的结果,a为final[0]未知x的系数
for i := 0; i < len(finalCnt); i++ {
final = append(final, Node{a: 0, b: finalCnt[i]})
}
for i := len(plans) - 1; i >= 0; i-- { // 倒推
a, b := plans[i][0], plans[i][1]
if a == 1 {
final[b] = Node{
a: final[b].a * 2,
b: final[b].b * 2,
}
} else if a == 2 {
for j := 0; j < len(arr[b]); j++ {
next := arr[b][j]
final[next] = Node{
a: final[next].a - final[b].a,
b: final[next].b - final[b].b,
}
}
} else if a == 3 {
for j := 0; j < len(arr[b]); j++ {
next := arr[b][j]
final[next] = Node{
a: final[next].a + final[b].a,
b: final[next].b + final[b].b,
}
}
}
}
a, b := float64(0), int64(0)
for i := 0; i < len(final); i++ {
a = a + final[i].a
b = b + int64(final[i].b)
}
per := float64(totalNum-b) / a // 求x的值
res := make([]int, n)
for i := 0; i < n; i++ {
res[i] = int(final[i].a*per) + final[i].b
}
return res
}
Medium题目,本质上是求解方程问题
页面更新:2024-04-16
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号