2021-11-28:有一棵树,给定头节点h,和结构数组m,下标
2023-03-20 14:52:40 时间
2021-11-28:有一棵树,给定头节点h,和结构数组m,下标0弃而不用。
比如h = 1, m = [ [] , 2,3, 4, 5,6, [], [], []],
表示1的孩子是2、3; 2的孩子是4; 3的孩子是5、6; 4、5和6是叶节点,都不再有孩子,
每一个节点都有颜色,记录在c数组里,比如ci = 4, 表示节点i的颜色为4,
一开始只有叶节点是有权值的,记录在w数组里,
比如,如果一开始就有wi = 3, 表示节点i是叶节点、且权值是3。
现在规定非叶节点i的权值计算方式:
根据i的所有直接孩子来计算,假设i的所有直接孩子,颜色只有a,b,k。
wi = Max {
(颜色为a的所有孩子个数 + 颜色为a的孩子权值之和),
(颜色为b的所有孩子个数 + 颜色为b的孩子权值之和),
(颜色为k的所有孩子个数 + 颜色k的孩子权值之和)
}
请计算所有孩子的权值并返回。
来自美团。
答案2021-11-28:
这道题考的是语文。后序遍历。
当前来到h节点,
h的直接孩子,在哪呢?mh = {a,b,c,d,e},
每个节点的颜色在哪?比如i号节点,ci就是i号节点的颜色,
每个节点的权值在哪?比如i号节点,wi就是i号节点的权值,
void : 把w数组填满就是这个函数的目标。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
h := 1
m := [][]int{{}, {2, 3}, {4}, {5, 6}, {}, {}, {}}
w := []int{0, 0, 0, 4, 5, 6, 0}
c := []int{0, 0, 0, 4, 3, 2, 0}
w0(h, m, w, c)
fmt.Println(w)
fmt.Println(c)
}
func w0(h int, m [][]int, w []int, c []int) {
if len(m[h]) == 0 { // 叶节点
return
}
// 有若干个直接孩子
// 1 7个
// 3 10个
colors := make(map[int]int)
// 1 20
// 3 45
weihts := make(map[int]int)
for _, child := range m[h] {
w0(child, m, w, c)
colors[c[child]]++
weihts[c[child]] += +w[c[child]]
}
for color, _ := range colors {
w[h] = getMax(w[h], colors[color]+weihts[color])
}
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下:
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十