2022-03-20：给定一棵多叉树的头节点head，
每个节点的颜色只会是0、1、2、3中的一种，
任何两个节点之间的都有路径，
如果节点a和节点b的路径上，包含全部的颜色，这条路径算达标路径，
(a -> … -> b)和(b -> … -> a)算两条路径。
求多叉树上达标的路径一共有多少？
点的数量 <= 10^5。
答案2022-03-20：
方法一：自然智慧，所有节点两两对比。
方法二：递归，前缀和+后缀和+位运算。目前是最难的。
当前节点是起点，当前节点是终点。
子节点两两对比。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
root := NewNode(0)
root.nexts = make([]*Node, 2)
root.nexts[0] = NewNode(1)
root.nexts[1] = NewNode(2)
root.nexts[0].nexts = make([]*Node, 1)
root.nexts[0].nexts[0] = NewNode(3)
ret := colors3(root)
fmt.Println(ret)
}
type Node struct {
color int
nexts []*Node
}
func NewNode(c int) *Node {
ans := &Node{}
ans.color = c
ans.nexts = make([]*Node, 0)
return ans
}
type Info struct {
// 我这棵子树，总共合法的路径有多少？
all int
// 课上没有强调！但是请务必注意！
// 一定要从头节点出发的情况下！
// 一定要从头节点出发的情况下！
// 一定要从头节点出发的情况下！
// 走出来每种状态路径的条数
colors []int
}
func NewInfo() *Info {
ans := &Info{}
ans.all = 0
ans.colors = make([]int, 16)
return ans
}
func colors3(head *Node) int {
if head == nil {
return 0
}
return process3(head).all
}
var consider = [][]int{{}, // 0
{14, 15}, // 1 -> 0001
{13, 15}, // 2 -> 0010
{12, 13, 14, 15}, // 3 -> 0011
{11, 15}, // 4 -> 0100
{10, 11, 14, 15}, // 5 -> 0101
{9, 11, 13, 15}, // 6 -> 0110
{8, 9, 10, 11, 12, 13, 14, 15}, // 7 -> 0111
{7, 15}, // 8 -> 1000
{6, 7, 14, 15}, // 9 -> 1001
{5, 7, 13, 15}, // 10 -> 1010
{4, 5, 6, 7, 12, 13, 14, 15}, // 11 -> 1011
{3, 7, 11, 15}, // 12 -> 1100
{2, 3, 6, 7, 10, 11, 14, 15}, // 13 -> 1101
{1, 3, 5, 7, 9, 11, 13, 15}, // 14 -> 1110
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, // 15 -> 1111
}
func process3(h *Node) *Info {
ans := NewInfo()
hs := 1 << h.color
ans.colors[hs] = 1
if len(h.nexts) > 0 {
n := len(h.nexts)
infos := make([]*Info, n+1)
for i := 1; i <= n; i++ {
infos[i] = process3(h.nexts[i-1])
ans.all += infos[i].all
}
lefts := make([][]int, n+2)
for i := 0; i < n+2; i++ {
lefts[i] = make([]int, 16)
}
for i := 1; i <= n; i++ {
for status := 1; status < 16; status++ {
lefts[i][status] = lefts[i-1][status] + infos[i].colors[status]
}
}
rights := make([][]int, n+2)
for i := 0; i < n+2; i++ {
rights[i] = make([]int, 16)
}
for i := n; i >= 1; i-- {
for status := 1; status < 16; status++ {
rights[i][status] = rights[i+1][status] + infos[i].colors[status]
}
}
for status := 1; status < 16; status++ {
ans.colors[status|hs] += rights[1][status]
}
ans.all += ans.colors[15] << 1
for from := 1; from <= n; from++ {
for fromStatus := 1; fromStatus < 16; fromStatus++ {
for _, toStatus := range consider[fromStatus|hs] {
ans.all += infos[from].colors[fromStatus] * (lefts[from-1][toStatus] + rights[from+1][toStatus])
}
}
}
}
return ans
}
执行结果如下：
左神java代码
