|
请你设计一个文件目录权限管理系统，实现以下功能： · 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
}
View Code
#############官方给的代码 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
}
View Code
####感受#### 8. 总结1) 解法总结
判断能否访问加密目录的方法有下面几种： l 记录每个节点的父节点，然后从目标目录dirId对应的节点向上查找，如果任意一个父节点被授权过，那么说明可以访问dirId l 从授权过的节点出发，DFS遍历其子节点，如果找到dirId，说明可以访问dirId l 从授权过的节点出发，BFS遍历其子节点，如果找到dirId，说明可以访问dirId |
