gpt4 book ai didi

algorithm - 将字符串数组的数组转换为层次结构

转载 作者:IT王子 更新时间:2023-10-29 02:07:58 26 4
gpt4 key购买 nike

假设我对数组进行了排序,如下所示:

["A", "B", "C"]
["A", "B", "D"]
["A", "E"]
["F", "G"]

我现在想转换成

type Node struct {
NodeID string
Children []Node
}

我尝试的是编写一种通过递归来完成此操作的方法。

这是我目前用 Go 编写的尝试:

func Test_toNodes(t *testing.T) {
in := [][]string{
{"A", "B", "C"},
{"A", "B", "D"},
{"A", "E"},
{"F", "G"},
}

want := []Node{
{
Name: "A",
Children: []Node{
{
Name: "B",
Children: []Node{
{
Name: "C",
},
{
Name: "D",
},
},
},
{
Name: "E",
},
},
},
{
Name: "F",
},
}

got := toNodes(in)
if !reflect.DeepEqual(got, want) {
t.Fatalf("got %v, want %v", got, want)
}
}

func toNodes(in [][]string) []Node {
var (
tmp [][]string
out []Node
)

for i, hierarchy := range in {
current := nodeAt(in, i)
next := nodeAt(in, i+1)

if current == next {
if len(hierarchy) > 0 {
tmp = append(tmp, hierarchy[1:])
}
} else {
out = append(out, Node{
Name: current,
Children: toNodes(tmp),
})
}
}

return out
}

func nodeAt(h [][]string, i int) string {
if i > len(h)-1 {
return ""
}
v := h[i]
if len(v) == 0 {
return ""
}
return v[0]
}

这显然没有呈现正确的结果,也没有处理所有的边缘情况——那么是否有一个通用的“算法”可以在这里应用?

最佳答案

这是一个传递样本输入的递归解决方案。您没有说太多关于输入和可能存在的边缘情况,所以如果它在某些输入上失败并提供输入,请告诉我。

我还在测试中修复了您的预期结果。您忘记了 F 节点 G 的子节点。希望这会有所帮助。

type Node struct {
Name string
Children []Node
}

func Test_toNodes(t *testing.T) {
in := [][]string{
{"A", "B", "C"},
{"A", "B", "D"},
{"A", "E"},
{"F", "G"},
}

want := []Node{
{
Name: "A",
Children: []Node{
{
Name: "B",
Children: []Node{
{
Name: "C",
},
{
Name: "D",
},
},
},
{
Name: "E",
},
},
},
{
Name: "F",
Children: []Node{
{
Name: "G",
},
},
},
}

got := toNodes(in, 0, 0, len(in))
if !reflect.DeepEqual(got, want) {
t.Fatalf("got %v, want %v", got, want)
}
}

func toNodes(in [][]string, i, j, k int) []Node {
res := []Node{}

for m := j; m < k; m++ {
curr := nodeAt(in, i, m)
next := nodeAt(in, i, m+1)
if next != curr {
children := toNodes(in, i+1, j, m+1)
if len(children) == 0 {
children = nil
}
res = append(res, Node{
Name: curr,
Children: children,
})
j = m + 1
}
}

return res
}

func nodeAt(h [][]string, i, j int) string {
if j >= len(h) || i >= len(h[j]) {
return ""
}
return h[j][i]
}

关于algorithm - 将字符串数组的数组转换为层次结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54280473/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com