【1993. 树上的操作】

来源:力扣(LeetCode)

描述:

给你一棵 n 个节点的树,编号从 0 到 n - 1 ,以父节点数组 parent 的形式给出,其中 parent[i] 是第 i 个节点的父节点。树的根节点为 0 号节点,所以 parent[0] = -1 ,因为它没有父节点。你想要设计一个数据结构实现树里面对节点的加锁,解锁和升级操作。

数据结构需要支持如下函数:

  • Lock: 指定用户给指定节点 上锁 ,上锁后其他用户将无法给同一节点上锁。只有当节点处于未上锁的状态下,才能进行上锁操作。
  • Unlock: 指定用户给指定节点 解锁 ,只有当指定节点当前正被指定用户锁住时,才能执行该解锁操作。
  • Upgrade: 指定用户给指定节点 上锁 ,并且将该节点的所有子孙节点 解锁 。只有如下 3 个条件 全部 满足时才能执行升级操作:
    • 指定节点当前状态为未上锁。
    • 指定节点至少有一个上锁状态的子孙节点(可以是 任意 用户上锁的)。
    • 指定节点没有任何上锁的祖先节点。

请你实现 LockingTree 类:

  • LockingTree(int[] parent) 用父节点数组初始化数据结构。
  • lock(int num, int user) 如果 iduser 的用户可以给节点 num 上锁,那么返回 true ,否则返回 false 。如果可以执行此操作,节点 num 会被 iduser 的用户 上锁
  • unlock(int num, int user) 如果 iduser 的用户可以给节点 num 解锁,那么返回 true ,否则返回 false 。如果可以执行此操作,节点 num 变为 未上锁 状态。
  • upgrade(int num, int user) 如果 iduser 的用户可以给节点 num 升级,那么返回 true ,否则返回 false 。如果可以执行此操作,节点 num 会被 升级

示例 1:

1

输入:
["LockingTree", "lock", "unlock", "unlock", "lock", "upgrade", "lock"]
[[[-1, 0, 0, 1, 1, 2, 2]], [2, 2], [2, 3], [2, 2], [4, 5], [0, 1], [0, 1]]
输出:
[null, true, false, true, true, true, false]解释:
LockingTree lockingTree = new LockingTree([-1, 0, 0, 1, 1, 2, 2]);
lockingTree.lock(2, 2);    // 返回 true ,因为节点 2 未上锁。// 节点 2 被用户 2 上锁。
lockingTree.unlock(2, 3);  // 返回 false ,因为用户 3 无法解锁被用户 2 上锁的节点。
lockingTree.unlock(2, 2);  // 返回 true ,因为节点 2 之前被用户 2 上锁。// 节点 2 现在变为未上锁状态。
lockingTree.lock(4, 5);    // 返回 true ,因为节点 4 未上锁。// 节点 4 被用户 5 上锁。
lockingTree.upgrade(0, 1); // 返回 true ,因为节点 0 未上锁且至少有一个被上锁的子孙节点(节点 4)。// 节点 0 被用户 1 上锁,节点 4 变为未上锁。
lockingTree.lock(0, 1);    // 返回 false ,因为节点 0 已经被上锁了。

提示:

  • n == parent.length
  • 2 <= n <= 2000
  • 对于 i != 0 ,满足 0 <= parent[i] <= n - 1
  • parent[0] == -1
  • 0 <= num <= n - 1
  • 1 <= user <= 104
  • parent 表示一棵合法的树。
  • lock ,unlock 和 upgrade 的调用 总共 不超过 2000 次。

方法:深度优先搜索

思路

按照题目要求,依次实现各个函数即可:

  • Lock:可以用一个数组变量 lockNodeUser 记录给各个节点上锁的用户,lockNodeUser[num] 即表示给节点 num 上锁的用户。当lockNodeUser[num] = −1 时,即表示 节点 num 未被上锁,通过给 lockNodeUser[num] 赋值实现上锁。
  • Unlock:通过比较变量 lockNodeUser[num] 和 user 是否先等来判断当前节点是否可以解锁,通过赋值来解锁。
  • Upgrade:实现较为复杂,首先需要判断三个条件是否同时成立,如果是,还需要给指定节点上锁并且给它的所有子孙节点解锁。三个条件中:
    • 指定节点当前状态为未上锁:通过变量 lockNodeUser 来判断。
    • 指定节点没有任何上锁的祖先节点:需要依次遍历当前节点的父亲节点,通过变量 lockNodeUser 和 parent 来判断。具体代码中,我们利用一个函数 hasLockedAncestor 来实现这一判断。
    • 指定节点至少有一个上锁状态的子孙节点:我们将这一判断放到第三步来进行,使得它可以和「给它的所有子孙节点解锁」同时实现。三个状态的判断,我们用「短路与」来连接,当只有前两步都为真,才会进行第三步。当第三步也为真,那么我们就需要进行「给它的所有子孙节点解锁」这一步;当第三步为假,就说明指定节点没有上锁的子孙节点,那么我们仍可以进行「给它的所有子孙节点解锁」这一步,并不影响树的状态。我们定义一个递归函数 checkAndUnlockDescendant 来实现这一步,返回一个布尔值表示当前节点是否有上锁的子孙节点(也包括自己),同时将所有的子孙节点(也包括自己)解锁。遍历子孙节点时,我们提前构建一个变量 children,表示当前节点的孩子节点,这一步可以在初始化时完成。

最后,如果这三个条件与的结果为真,将当前节点上锁。

代码:

class LockingTree {
public:LockingTree(vector<int>& parent) {int n = parent.size();this->parent = parent;this->lockNodeUser = vector<int>(n, -1);this->children = vector<vector<int>>(n);for (int i = 0; i < n; i++) {int p = parent[i];if (p != -1) {children[p].emplace_back(i);}}}bool lock(int num, int user) {if (lockNodeUser[num] == -1) {lockNodeUser[num] = user;return true;} return false;}bool unlock(int num, int user) {if (lockNodeUser[num] == user) {lockNodeUser[num] = -1;return true;}return false;}bool upgrade(int num, int user) {bool res = lockNodeUser[num] == -1 \&& !hasLockedAncestor(num) \&& checkAndUnlockDescendant(num);if (res) {lockNodeUser[num] = user;}return res;}bool hasLockedAncestor(int num) {num = parent[num];while (num != -1) {if (lockNodeUser[num] != -1) {return true;}num = parent[num];}return false;}bool checkAndUnlockDescendant(int num) {bool res = lockNodeUser[num] != -1;lockNodeUser[num] = -1;for (int child : children[num]) {res |= checkAndUnlockDescendant(child);}            return res;}private:vector<int> parent;vector<int> lockNodeUser;vector<vector<int>> children;
};

时间 328ms 击败 62.96%使用 C++ 的用户
内存 117.67MB 击败 94.44%使用 C++ 的用户
复杂度分析

  • 时间复杂度:初始化:构建 children 消耗 O(n),Lock 和 Unlock 都消耗 O(1),Upgrade 消耗 O(n)。
  • 空间复杂度:初始化消耗 O(n),Lock 和 Unlock 都消耗 O(1),Upgrade 消耗 O(n)。
    author:力扣官方题解

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/139702.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【完全二叉树魔法:顺序结构实现堆的奇象】

本章重点 二叉树的顺序结构堆的概念及结构堆的实现堆的调整算法堆的创建堆排序TOP-K问题 1.二叉树的顺序结构 普通的二叉树是不适合用数组来存储的&#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构…

kafka消费者多线程开发

目录 前言 kafka consumer 设计原理 多线程的方案 参考资料 前言 目前&#xff0c;计算机的硬件条件已经大大改善&#xff0c;即使是在普通的笔记本电脑上&#xff0c;多核都已经是标配了&#xff0c;更不用说专业的服务器了。如果跑在强劲服务器机器上的应用程序依然是单…

pom.xml中解决“vulnerable dependency maven:org.yaml:snakeyaml:1.33“警告问题

问题 当我们引入依赖的时候&#xff0c;pom文件会有这样的提示&#xff0c;其大概的意思就是 maven:org.yaml:snakeyaml:1.30"表示通过Maven引入了一个潜在的安全漏洞依赖项"org.yaml:snakeyaml:1.30" 解决办法 其实我们就是要更改这个依赖的版本&#xff0c…

【李沐深度学习笔记】按特定轴求和

课程地址和说明 线性代数实现p4 本系列文章是我学习李沐老师深度学习系列课程的学习笔记&#xff0c;可能会对李沐老师上课没讲到的进行补充。 这节就算之前内容的复习&#xff0c;后面以截图形式呈现 这节课就简单说明以下&#xff0c;axis为0是行&#xff0c;1是列&#xf…

解决方案:TSINGSEE青犀+智能分析网关助力智慧仓储智能化监管

为全面保障物流仓储的安全性与完整性&#xff0c;解决仓库管理难题&#xff0c;优化物流仓储方式&#xff0c;提升仓储效率&#xff0c;降低人工成本&#xff0c;旭帆科技推出智慧仓储AI视频智能分析方案&#xff0c;利用物联网、大数据、云计算等技术&#xff0c;对仓储管理进…

Date类的学习笔记-超级详细

Date 的定义, 在开始研究这个之前我们首先要能够明白一点&#xff0c;这个 Date 其实本质上是一个对象&#xff0c;我们通过这个对象可以去构建变量&#xff0c;知道这个之后就可以开展后续的研究了 JDK 通用 Date 类的构造方法 测试 获取当前的时间 // 构造这个日期对象Date…

【@PostConstruct、 @Autowired与构造函数的执行顺序】

PostConstruct、 Autowired与构造函数的执行顺序 一、PostConstruct介绍二、Spring框架中在bean初始化和销毁时候执行实现方式三、项目验证1.MyServiceImpl2.测试结果3. 项目源码 最近对同事代码进行codeReview时候发现用PostConstruct注解&#xff0c;特地对此注解执行顺序进行…

IDEA2023新UI回退老UI

idea2023年发布了新UI&#xff0c;如下所示 但是用起来真心不好用&#xff0c;各种位置也是错乱&#xff0c;用下面方法可以回退老UI

【C刷题】day3

一、选择题 1、已知函数的原型是&#xff1a; int fun(char b[10], int *a); &#xff0c;设定义&#xff1a; char c[10];int d; &#xff0c;正确的调用语句是&#xff08; &#xff09; A: fun(c,&d); B: fun(c,d); C: fun(&c,&d); D: fun(&c,d); 【答案…

07_ElasticSearch:倒排序索引与分词Analysis

07_ElasticSearch&#xff1a;倒排序索引与分词Analysis 一、 倒排索引是什么&#xff1f;1.1 通过示例&#xff0c;简单理解下1.2 核心组成 二、倒排索引是怎么工作的&#xff1f;2.1 创建倒排索引2.2 倒排索引搜索 三、Analysis 进行分词3.1 Analyzer 由三部分组成3.2 Analyz…

【JS】—垃圾回收机制

一、指令材料 1.定义 JavaScript&#xff08;JS&#xff09;的垃圾回收机制是一种自动管理内存的过程&#xff0c;它有助于释放不再使用的内存&#xff0c;以避免内存泄漏和提高程序的性能。 JavaScript的垃圾回收机制是一种自动管理内存的方式&#xff0c;以确保不再被引用的…

Linux Shell 实现一键部署podman

podman 介绍 使用 Podman 管理容器、Pod 和映像。从本地环境中无缝使用容器和 Kubernetes&#xff0c;Podman 提供与 Docker 非常相似的功能&#xff0c;它不需要在你的系统上运行任何守护进程&#xff0c;并且它也可以在没有 root 权限的情况下运行。 Podman 可以管理和运行…

Hive 的函数介绍

目录 ​编辑 一、内置运算符 1.1 关系运算符 1.2算术运算符 1.3逻辑运算符 1.4复杂类型函数 1.5对复杂类型函数操作 二、内置函数 2.1数学函数 2.2收集函数 2.3类型转换函数 2.4日期函数 2.5条件函数 2.6字符函数 三、内置的聚合函数 四、内置表生成函数 五、…

Android Jetpack组件架构:Lifecycle的使用 和 原理

Android Jetpack组件架构&#xff1a;Lifecycle的使用和原理 导言 作为Jetpack中关于生命周期管理的核心组件&#xff0c;Lifecycle组件是其他比如LiveDate和ViewModel等组件的基础&#xff0c;本篇文章主要就将介绍关于Lifecycle的使用和它的运作原理。 Lifecycle的使用 我…

MyBatis 中的插件可以拦截哪些操作

MyBatis 中的插件可以拦截哪些操作 MyBatis 是一个优秀的持久化框架&#xff0c;在实际项目开发中广泛应用。MyBatis 的插件机制可以方便地对 MyBatis 的各个环节进行扩展和定制。在本文中&#xff0c;我们将详细介绍 MyBatis 中的插件机制&#xff0c;并探讨插件可以拦截哪些…

C语言大佬的必杀技---宏的高级用法

C语言大佬的必杀技—宏的高级用法 目录: 字符串化标记的拼接宏的嵌套替换多条语句防止一个文件被重复包含宏和函数的区别 可能大家在学习的时候用得比较少&#xff0c;但是在一些代码量比较大的时候&#xff0c;这样使用&#xff0c;可以大大的提高代码的可读性&#xff0c;…

Dependency ‘org.redisson:redisson:‘ not found解决方法 三种刷新Maven项目的方法

报错情况 在pom中导入redisson包 <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId> </dependency> 爆红&#xff0c;还显示Dependency org.redisson:redisson: not found。 由于报错已经解决&#xff0c;…

002-第一代硬件系统架构确立及产品选型

第一代硬件系统架构确立及产品选型 文章目录 第一代硬件系统架构确立及产品选型项目介绍摘要硬件架构硬件结构选型及设计单片机选型上位机选型扯点别的 关键字&#xff1a; Qt、 Qml、 信号采集机、 数据处理、 上位机 项目介绍 欢迎来到我们的 QML & C 项目&#xff…

【视觉SLAM入门】8. 回环检测,词袋模型,字典,感知,召回,机器学习

"见人细过 掩匿盖覆” 1. 意义2. 做法2.1 词袋模型和字典2.1.2 感知偏差和感知变异2.1.2 词袋2.1.3 字典 2.2 匹配(相似度)计算 3. 提升 前言&#xff1a; 前端提取数据&#xff0c;后端优化数据&#xff0c;但误差会累计&#xff0c;需要回环检测构建全局一致的地图&…

【AI视野·今日Sound 声学论文速览 第十期】Fri, 22 Sep 2023

AI视野今日CS.Sound 声学论文速览 Fri, 22 Sep 2023 Totally 1 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Sound Papers Performance Conditioning for Diffusion-Based Multi-Instrument Music Synthesis Authors Ben Maman, Johannes Zeitler, Meinard M lle…