|
请你设计一个文件目录权限管理系统，实现以下功能： · DirPermSystem(int[] path, int[] statuses) —— 初始化文件目录树及其初始状态 o path[i] 下标表示目录编号，值表示其上一级目录的编号（根目录编号为 0，path[0]固定为 -1）。 o statuses[i] 表示目录 i 的初始状态。仅两种： § 1 表示「公开」状态，所有用户均可访问（无论是否授权）； § 2 表示「加密」状态，仅拥有权限的用户可访问； · changeStatus(int dirId, int status) —— 修改目录 dirId 的状态为 status。（不涉及子目录） · grantRight(int userId, int dirId) —— 授予用户 userId 对目录 dirId 持有「目录树权限」。 o 持有对 dirId 的「目录树权限」后，代表该用户可以访问 dirId 及其所有子目录（包含直接子目录、子目录的子目录等），即使加密的目录也可以访问。 o 注意：重复授予同一用户对目录 dirId 的「目录树权限」授权，只保留最后一次。 · removeRight(int userId, int dirId) —— 移除用户 userId 对目录 dirId 所持有的「目录树权限」。若授予过，则移除对这个目录的授权，并返回 true；否则不做处理，返回 false。 · queryRight(int userId, int dirId) —— 查询用户 userId 是否可以访问目录 dirId，是返回 true；否则返回 false。 · queryNum(int userId) —— 查询用户 userId 所有可访问的目录数量。 注： 输入用例保证函数中的 dirId 已存在。 示例 1： 输入： 输出：[null,null,null,true,4,true] 解释： 0 (公开) └ 4 (公开) ├ 1 (公开) │ └ 3 (公开) └ 2 (加密) sys.grantRight(101,1); // 授予用户 101 对目录 1 的「目录树权限」，即可访问目录1、3 示例 2： 输入： 输出： 解释： 0 (加密) ├ 6 (公开) │ ├ 3 (加密) │ │ └ 8（公开） │ └ 4 (加密) ├ 2 (加密) │ ├ 1 (公开) │ └ 7 (加密) └ 5 (公开) sys.grantRight(105,6); // 授予用户 105 对目录 6 的「目录树权限」，即可访问目录 6 及其子目录 3、8、4 提示： · 2 <= changeStatus,grantRight,removeRight,queryRight,queryNum 累计操作数 <= 10^3 · 0 <= path.length == statuses.length <= 1000 · -1 <= path[i] <= path.length - 1 · 0 <= dirId <= path.length - 1 · 1 <= statuses[i], status <= 2 · 0 <= userId <= 1000 · 用例保证目录的深度不超过 30
2. 题目分析题目理解： 需要设计一个文件目录权限管理系统，支持以下功能：修改目录加密状态，授予用户目录树权限，移除用户目录树权限，查询用户是否有访问目录权限，查询用户可访问目录数量。 Ø 目录的访问权限和linux的目录权限管理不一样 对某个用户授予持有某目录的「目录树权限」，可以视作对这个目录配了一把“钥匙”，对同一个用户一个目录最多配一把“钥匙”。 有了这把“钥匙”后，此用户就有访问此目录及其子目录的能力，把这把“钥匙”拿走，能力则随之消失。 假设有如下三个目录，目录均为加密状态，层次如下： 7 ├ 8 │ └ 9 假定某用户持有目录 7、8 的「目录树权限」，移除目录 7 的权限后，由于仍持有目录 8 的权限，所以可以访问目录 8 和 9。如下图所示：
Ø 重复授予同一用户对目录 dirId 的「目录树权限」授权，只保留最后一次 对同一用户授予对目录7、目录8的「目录树权限」，这两个授权目录是独立且不同的。 只保留最后一次指的是同一个用户对同一个目录授权多次，只保留一次，举个例子： 假设对目录7授权了两次，然后删除授权一次，那么对于目录7也不存在授权了。 思路解析： 我们用节点表示目录，边表示目录之间的层级关系，如下图所示：
将对用户对目录的“授权”和判断用户“对某目录有访问权限”两个动作分开管理： Ø 授权只管对目录增加授权、删除授权； Ø 查询用户是否有访问目录权限时，如果目录状态是公开，可直接访问；如果是加密，有两个遍历方向： l 从下往上，即从 dirId 开始往祖先目录迭代查找，如果某祖先目录授予过目录树权限，则说明此用户可以访问dirId 例如上图中从节点9向上查找，找到节点8的时候发现8被授权过，所以可以访问9。 这种做法，不需要记录每个节点的children节点，只需要记录每个节点的父节点。 l 从上往下，即从授予过目录树权限的目录开始，通过DFS/BFS往子目录遍历。如果子目录编号等于 dirId，说明此用户可以访问dirId 这种做法，就必须要记录每个节点的children节点。
因为目录编号是输入参数path的数组下标，必然是唯一的，并且目录编号不超过1000，所以可以使用整型数组statuses来记录每个目录的授权：下标为目录编号、值为授权状态。 可以定义一个TreeNode结构表示一个目录，也可以用数组记录目录的编号、父目录编号。 下面来看看大家具体的实现代码： ##########bfs + 递归树 待验证######## 
package main import "fmt" type dirNode struct { id int // 树id status int // 1代表 公开 2代表 私有 userId int children []*dirNode } type DirPermSystem struct { tree map[int]*dirNode } func buildTree(parent, child int, statuses []int, nodes map[int]*dirNode) { if nodes[child] == nil { nodes[child] = &dirNode{id: child, status: statuses[child]} } if nodes[parent] == nil && parent != -1 { nodes[parent] = &dirNode{id: parent, status: statuses[parent]} } if parent != -1 { nodes[parent].children = append(nodes[parent].children, nodes[child]) } } func Constructor(path []int, statuses []int) DirPermSystem { // 初始化一个map存储多叉树 nodes := make(map[int]*dirNode) for child, parent := range path { buildTree(parent, child, statuses, nodes) } return DirPermSystem{tree: nodes} } func (d *DirPermSystem) ChangeStatus(dirId int, status int) { if d, exist := d.tree[dirId]; exist { d.status = status } } func (d *DirPermSystem) GrantRight(userId int, dirId int) { grantTree := d.tree[dirId] grantTree.userId = userId d.SetChildRight(grantTree, userId) } func (d *DirPermSystem) SetChildRight(childTree *dirNode, userId int) { if childTree == nil { return } for _, child := range childTree.children { child.userId = userId d.SetChildRight(child, userId) } return } func (d *DirPermSystem) RemoveRight(userId int, dirId int) bool { //判断是否移除的权限属于当前用户 if grantTree, exist := d.tree[dirId]; exist { if grantTree.userId != userId { return false } grantTree.userId = 0 // 递归移除userId授权 d.SetChildRight(grantTree, 0) } return true } func (d *DirPermSystem) QueryRight(userId int, dirId int) bool { // 任一给一个目录id,查看userid是否是授权的userId if grantTree, exist := d.tree[dirId]; exist { if grantTree.userId == userId { return true } return false } return false } func (d *DirPermSystem) QueryNum(userId int) int { // bfs查看所有公开的节点数量+userId授权了的数量 count := 0 rootNode := d.tree[0] queue := []*dirNode{rootNode} for len(queue) != 0 { queueLen := len(queue) for i := 0; i < queueLen; i++ { cur := queue[0] queue = queue[1:] if cur.userId == userId || cur.status == 1 { count++ } queue = append(queue, cur.children...) } } return count } func main() { obj := Constructor([]int{-1, 4, 4, 1, 0}, []int{1, 1, 2, 1, 1}) obj.GrantRight(101, 1) obj.ChangeStatus(1, 2) fmt.Println(obj.QueryRight(101, 3)) // true fmt.Println(obj.QueryNum(101)) // 4 fmt.Println(obj.RemoveRight(101, 1)) fmt.Println(obj.QueryRight(101, 1)) // true } #############官方给的代码 newbing 翻译的
package main import ( "container/list" "fmt" ) type TreeNode struct { dirId int children []*TreeNode } type DirPermSystem struct { path []int statuses []int nodes []*TreeNode userRightMap map[int]map[int]bool } func NewDirPermSystem(path []int, statuses []int) *DirPermSystem { d := &DirPermSystem{ path: path, statuses: statuses, userRightMap: make(map[int]map[int]bool), nodes: make([]*TreeNode, len(path)), } for i := 0; i < len(path); i++ { node := &TreeNode{ dirId: i, children: make([]*TreeNode, 0), } d.nodes[i] = node } for i := 1; i < len(path); i++ { d.nodes[path[i]].children = append(d.nodes[path[i]].children, d.nodes[i]) } return d } func (d *DirPermSystem) ChangeStatus(dirId int, status int) { d.statuses[dirId] = status } func (d *DirPermSystem) GrantRight(userId int, dirId int) { if _, ok := d.userRightMap[userId]; !ok { d.userRightMap[userId] = make(map[int]bool) } d.userRightMap[userId][dirId] = true } func (d *DirPermSystem) RemoveRight(userId int, dirId int) bool { if _, ok := d.userRightMap[userId]; !ok { return false } delete(d.userRightMap[userId], dirId) return true } func (d *DirPermSystem) QueryRight(userId int, dirId int) bool { if d.statuses[dirId] == 1 { return true } if _, ok := d.userRightMap[userId]; !ok { return false } queue := list.New() for dirId := range d.userRightMap[userId] { queue.PushBack(d.nodes[dirId]) } for queue.Len() > 0 { node := queue.Remove(queue.Front()).(*TreeNode) if node.dirId == dirId { return true } for _, child := range node.children { queue.PushBack(child) } } return false } func (d *DirPermSystem) QueryNum(userId int) int { set := make(map[int]bool) for i := 0; i < len(d.statuses); i++ { if d.statuses[i] == 1 || d.QueryRight(userId, i) { set[i] = true } } return len(set) } func main() { //path := []int{0, 1, 2, 3} //statuses := []int{0, 0, 0, 0} //system := NewDirPermSystem(path, statuses) //system.GrantRight(1, 1) //system.GrantRight(1, 2) //system.GrantRight(2, 3) //fmt.Println(system.QueryRight(1, 1)) // true //fmt.Println(system.QueryRight(1, 2)) // true //fmt.Println(system.QueryRight(1, 3)) // false //fmt.Println(system.QueryRight(2, 1)) // false //fmt.Println(system.QueryRight(2, 2)) // true //fmt.Println(system.QueryRight(2, 3)) // true obj := NewDirPermSystem([]int{-1, 4, 4, 1, 0}, []int{1, 1, 2, 1, 1}) obj.GrantRight(101, 1) obj.ChangeStatus(1, 2) fmt.Println(obj.QueryRight(101, 3)) // true fmt.Println(obj.QueryNum(101)) // 4 fmt.Println(obj.RemoveRight(101, 1)) // true fmt.Println(obj.QueryRight(101, 1)) // true }
####感受#### 8. 总结1) 解法总结
判断能否访问加密目录的方法有下面几种： l 记录每个节点的父节点，然后从目标目录dirId对应的节点向上查找，如果任意一个父节点被授权过，那么说明可以访问dirId l 从授权过的节点出发，DFS遍历其子节点，如果找到dirId，说明可以访问dirId l 从授权过的节点出发，BFS遍历其子节点，如果找到dirId，说明可以访问dirId |
上机编程[文件目录权限管理系统]学习交流
发布时间 2023-12-12 21:51:27作者: 易先讯
