1. 题目
今天学习2022-11-25专业级第二题。
|
在一个目录树中（假设都是目录），过深的目录路径不容易展示，为了提升用户体验，需要对目录进行收缩展示，求收缩后某一深度的目录个数。 1. root root 2. ├ B ├ B/C/E 3. │ └ C │ ├ N 4. │ └ E │ └ M 5. │ ├ N └ F 6. │ └ M ├ H 7. └ F └ X/i 8. ├ H 9. └ X 10. └ i 收缩规则： · 若某目录仅有一个子目录，则把这个子目录收缩到其父目录，展示为一个新目录。如图所示，i 收缩到 X 变成新的目录 X/i。 · 所有符合上述条件的均需收缩，收缩后符合上述条件的继续收缩，直到无法收缩。如图所示，目录B、C、E收缩为新的目录 B/C/E 现给定一个原目录树 orgTree，请按照收缩规则展示为一个新目录树，求新目录树中深度值为 depth（根节点深度为 1）的节点个数。 如图所示，收缩后深度为 2 的节点有 2 个（B/C/E、F），深度为 3 的节点有 4 个（N、M、H、X/i）。 输入 一个整数 num，表示父子节点对的数量，1 <= num <= 300 树只有一个根，首个节点对的父节点为根。 输出 一个整数，表示收缩后深度为 depth 的节点个数 样例 输入样例 1 9 root B root F C E B C E N F H F X E M X i 3 输出样例 1 4 提示样例 1 输入数据表示的原目录树，及收缩示意如题面图示，深度为 3 的节点有 4 个（N、M、H、X/i） 输入样例 2 3 1 B123456789 B123456789 c 1 b123456789 3 输出样例 2 0 提示样例 2 原目录树收缩后，不存在深度为 3 的节点，因此返回 0 输入样例 3 4 A B B C C D D E 1 输出样例 3 1 提示样例 3 收缩显示为一个节点 A/B/C/D/E，深度 1 的节点数为 1
2. 题目分析题目理解： 现给出一棵原始的目录树（只给了“父节点-子节点”对），按规则收缩（也可以称作为合并或者折叠）后，求深度为depth的节点个数： l 规则1: 如果当前目录的子目录数为1，则向上收缩，直到无法收缩。 l 规则2: 根节点为orgTree[0][0]，唯一且深度为1。 注意，树上各节点名称是全局唯一的。 思路解析： 如果没有收缩的需求，那么只需要以深度优先或者广度优先的方式遍历整棵树，就可以得到结果。 要实现收缩的需求，有两个思路： l 可以先收缩树节点，再遍历统计 例如，如果已经构建出树了，可以这样递归实现收缩： func dfsMerge(node *treeNode) { parent := node for ; len(parent.children) == 1; { // B-C 合并为 B/C child := parent.children[0] parent.name = parent.name + "/" + child.name parent.children = child.children } for i, child := range node.children { dfsMerge(child) } } l 也可以直接遍历统计，遇到需要收缩的节点不计算这一层的深度即可 下面看看大家的具体代码实现。
总结1) 本题解法总结
同样是BFS，员工5的GO语言解法遍历到深度为depth后就停止搜索，效率比较高；C++的解法需要遍历所有节点，效率要差一些。 员工3的JAVA代码和员工4的PYTHON代码都是建立树之后进行DFS遍历，但存在差异： l 员工3的JAVA解法定义了一个单独的类TreeNode表示节点，而PYTHON解法用字典的key作父节点、字典的value是一个数组用来存储子节点。 l 员工3的JAVA解法传入的node参数是父节点，而PYTHON解法的nodes是子节点。 当树节点需要存储的属性比较少时，可以直接用数组等数据结构；而当需要存储的属性比较多时，建议定义一个单独的结构体TreeNode，这样代码的可维护性也比较好。 2) 树的深度计算和遍历
######### dfs
#################
dfs 算法一步到位
#################
package main
import "fmt"
type dirNode struct {
name string
children []*dirNode
}
func buildTree(parent, child string, nodes map[string]*dirNode) {
if nodes[parent] == nil {
nodes[parent] = &dirNode{name: parent}
}
if nodes[child] == nil {
nodes[child] = &dirNode{name: child}
}
nodes[parent].children = append(nodes[parent].children, nodes[child])
}
func getTargetNum(node *dirNode, depth, target int) int {
for len(node.children) == 1 {
node = node.children[0]
}
if depth == target {
return 1
}
result := 0
for i := 0; i < len(node.children); i++ {
result += getTargetNum(node.children[i], depth+1, target)
}
return result
}
func getNodesNum(orgTree [][]string, depth int) int {
nodes := make(map[string]*dirNode)
for _, tree := range orgTree {
buildTree(tree[0], tree[1], nodes)
}
res := getTargetNum(nodes["root"], 1, depth)
return res
}
func main() {
res := getNodesNum([][]string{
{"root", "B"},
{"root", "F"},
{"C", "E"},
{"B", "C"},
{"E", "N"},
{"F", "N"},
{"F", "X"},
{"E", "M"},
{"X", "i"},
}, 3)
fmt.Println(res)
}
View Code
######### bfs
package main
import "fmt"
type dirNode struct {
name string
children []*dirNode
}
func buildTree(parent, child string, nodes map[string]*dirNode) {
if nodes[parent] == nil {
nodes[parent] = &dirNode{name: parent}
}
if nodes[child] == nil {
nodes[child] = &dirNode{name: child}
}
nodes[parent].children = append(nodes[parent].children, nodes[child])
}
func getTargetNum(node *dirNode, depth, target int) int {
for len(node.children) == 1 {
node = node.children[0]
}
if depth == target {
return 1
}
result := 0
for i := 0; i < len(node.children); i++ {
result += getTargetNum(node.children[i], depth+1, target)
}
return result
}
func flodDir(nodes *dirNode) *dirNode {
for _, child := range nodes.children {
flodDir(child)
}
if len(nodes.children) == 1 {
nodes.name = nodes.name + "/" + nodes.children[0].name
nodes.children = nodes.children[0].children
}
if nodes.children == nil {
return nodes
}
return nil
}
func getTargetNum2(nodes *dirNode, depth int) int {
count := 0
queue := []*dirNode{nodes}
level := 1
for len(queue) != 0 {
queueLen := len(queue)
if level == depth {
count = queueLen
}
for i := 0; i < queueLen; i++ {
cur := queue[0]
queue = queue[1:]
// 已经遍历到最后一层了
if cur.children == nil {
return count
}
queue = append(queue, cur.children...)
}
level++
}
return count
}
func getNodesNum(orgTree [][]string, depth int) int {
nodes := make(map[string]*dirNode)
for _, tree := range orgTree {
buildTree(tree[0], tree[1], nodes)
}
//res := getTargetNum(nodes["root"], 1, depth)
flodDir(nodes["root"])
res := getTargetNum2(nodes["root"], depth)
return res
}
func main() {
res := getNodesNum([][]string{
{"root", "B"},
{"root", "F"},
{"C", "E"},
{"B", "C"},
{"E", "N"},
{"F", "N"},
{"F", "X"},
{"E", "M"},
{"X", "i"},
}, 3)
fmt.Println(res)
}
View Code
|
