当前位置: 首页 > news >正文

【每日一题Day335】LC1993树上的操作 | dfs

树上的操作【LC1993】

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

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

  • **Lock:**指定用户给指定节点 上锁 ,上锁后其他用户将无法给同一节点上锁。只有当节点处于未上锁的状态下,才能进行上锁操作。

  • **Unlock:**指定用户给指定节点 解锁 ,只有当指定节点当前正被指定用户锁住时,才能执行该解锁操作。

  • Upgrade:

    指定用户给指定节点

    上锁

    ,并且将该节点的所有子孙节点

    解锁

    。只有如下 3 个条件

    全部

    满足时才能执行升级操作:

    • 指定节点当前状态为未上锁。
    • 指定节点至少有一个上锁状态的子孙节点(可以是 任意 用户上锁的)。
    • 指定节点没有任何上锁的祖先节点。

请你实现 LockingTree 类:

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

    使用数组记录每个节点的父节点以及上锁状态,并使用list记录每个节点的孩子节点,方便dfs操作

    • lock和unlock函数进行简单判断即可
    • upgrade函数需要判断祖先节点是否上锁,再通过dfs判断是否有上锁的孩子节点,并将其解锁
  • 实现

    class LockingTree {// 记录每个节点的根节点以及加锁状态int[] locked;int[] parent;int n;List<Integer>[] children;public LockingTree(int[] parent) {this.n = parent.length;this.parent = parent;this.locked = new int[n];this.children = new List[n];Arrays.fill(locked, -1);Arrays.setAll(children, e -> new ArrayList<>());for (int i = 0; i < n; i++){if (parent[i] != -1){children[parent[i]].add(i);}}}public boolean lock(int num, int user) {if (locked[num] != -1) return false;locked[num] = user;return true;}public boolean unlock(int num, int user) {if (locked[num] == user){locked[num] = -1;return true;}return false;}public boolean upgrade(int num, int user) {if (locked[num] != -1) return false;// 判断祖先节点是否上锁int p = parent[num];while (p != -1){if (locked[p] != -1) return false;p = parent[p];}// 判断是否有子孙节点加锁了,并给子孙节点解锁boolean[] res = {false};dfs(num, res);if (res[0] == false) return false;locked[num] = user;return true;}public void dfs(int p, boolean[] lock){for (int u : children[p]){if (locked[u] != -1){lock[0] = true;locked[u] = -1;               }dfs(u, lock);}}
    }/*** Your LockingTree object will be instantiated and called as such:* LockingTree obj = new LockingTree(parent);* boolean param_1 = obj.lock(num,user);* boolean param_2 = obj.unlock(num,user);* boolean param_3 = obj.upgrade(num,user);*/
    
    • 复杂度
      • 时间复杂度: n n n为二叉树的节点数目,lock和unlock为 O ( n ) \mathcal{O}(n) O(n),upgrade为 O ( 1 ) \mathcal{O}(1) O(1)
      • 空间复杂度: O ( n ) \mathcal{O}(n) O(n)

相关文章:

【每日一题Day335】LC1993树上的操作 | dfs

树上的操作【LC1993】 给你一棵 n 个节点的树&#xff0c;编号从 0 到 n - 1 &#xff0c;以父节点数组 parent 的形式给出&#xff0c;其中 parent[i] 是第 i 个节点的父节点。树的根节点为 0 号节点&#xff0c;所以 parent[0] -1 &#xff0c;因为它没有父节点。你想要设计…...

FPGA:卷积编码及维特比译码仿真

FPGA&#xff1a;卷积编码及维特比译码仿真 本篇记录一下在FPGA中完成卷积编码和维特比译码的过程&#xff0c;通过代码解释编码的过程和译码的过程&#xff0c;便于理解&#xff0c;同时也方便移植到其他工程中。 1. 准备工作 卷积编译码IP核—convolutionIP核和viterbiIP核…...

MySQL学习笔记4

客户端工具的使用&#xff1a; MySQL&#xff1a; mysql命令行工具&#xff0c;一般用来连接访问mysql的数据。 案例&#xff1a;使用mysql客户端工具连接服务器端&#xff08;用户名&#xff1a;root&#xff1b;密码&#xff1a;123456&#xff09;. [rootmysql-server ~]#…...

JavaFX:窗体显示状态,模态非模态

程序窗体显示一般有3中模式。非模态和模态&#xff0c;其中模态又分为程序模态和窗体模态。 非模态可以理解为窗体之间没有任何限制&#xff0c;可以用鼠标、键盘等工具在窗体间切换。 程序模态是窗体打开后&#xff0c;该程序的所有窗体都被冻结&#xff0c;无法切换&#x…...

C++17中std::filesystem::path的使用

C17引入了std::filesystem库(文件系统库, filesystem library)。这里整理下std::filesystem::path的使用。 std::filesystem::path&#xff0c;文件系统路径&#xff0c;提供了对文件系统及其组件(例如路径、常规文件和目录)执行操作的工具。此path类主要用法包括&#x…...

命令模式简介

概念&#xff1a; 命令模式是一种行为设计模式&#xff0c;它将请求封装成一个对象&#xff0c;从而允许您将不同的请求参数化、队列化&#xff0c;并且能够在不同的时间点执行。通过引入命令对象&#xff08;Command&#xff09;来解耦发送者&#xff08;Invoker&#xff09;…...

Boost序列化指针

Boost.Serialization 还能序列化指针和引用。 由于指针存储对象的地址&#xff0c;序列化对象的地址没有什么意义&#xff0c;而是在序列化指针和引用时&#xff0c;对象的引用被自动地序列化。 代码 #include <boost/archive/text_oarchive.hpp> #include <boost/…...

NIO简单介绍

一、什么是NIO 1、Java NIO全称java non-blocking IO&#xff0c; 是指JDK提供的新API。从JDK1.4开始&#xff0c;Java提供了一系列改进的输入/输出的新特性&#xff0c;被统称为NIO(即New IO)&#xff0c;是同步非阻塞的 2、NIO有三大核心部分: Channel(通道)&#xff0c; Buf…...

linux进程杀不死

项目场景&#xff1a; 虚拟机 问题描述 linux进程杀不死 无反应 原因分析&#xff1a; 进程僵死zombie 解决方案&#xff1a; 进proc或者find命令找到进程所在地址 cat status查看进程杀死子进程...

5分钟带你搞懂RPA到底是什么?RPA能做什么?

一、RPA的定义 RPA&#xff0c;全称Robotic Process Automation&#xff0c;即机器人流程自动化&#xff0c;是一种软件解决方案&#xff0c;能够模拟人类在计算机上执行的操作&#xff0c;以实现重复性、繁琐任务的自动化。它与传统的计算机自动化有所不同&#xff0c;因为它…...

毫米波雷达 TI IWR1443 在 ROS 中进行 octomap 建图

个人实验记录 /mmwave_ti_ros/ros_driver/src/ti_mmwave_rospkg/launch/1443_multi_3d_0.launch <launch><!-- Input arguments --><arg name"device" value"1443" doc"TI mmWave sensor device type [1443, 1642]"/><arg…...

113双周赛

题目列表 2855. 使数组成为递增数组的最少右移次数 2856. 删除数对后的最小数组长度 2857. 统计距离为 k 的点对 2858. 可以到达每一个节点的最少边反转次数 一、使数组成为递增数组的最少右移次数 这题可以直接暴力求解&#xff0c;枚举出每种右移后的数组&#xff0c;将…...

React 全栈体系(九)

第五章 React 路由 一、相关理解 1. SPA 的理解 单页 Web 应用&#xff08;single page web application&#xff0c;SPA&#xff09;。整个应用只有一个完整的页面。点击页面中的链接不会刷新页面&#xff0c;只会做页面的局部更新。数据都需要通过 ajax 请求获取, 并在前端…...

阈值化分割,对灰度级图像进行二值化处理(数字图像处理大题复习 P8)

文章目录 画出表格求出灰度直方图 & 山谷画出结果图 画出表格 有几个0就写几&#xff0c;有几个1就写几&#xff0c;如图 求出灰度直方图 & 山谷 跟前面求灰度直方图的方法一样&#xff0c;找出谷底&#xff0c;发现结果为 4 画出结果图 最终的结果就是&#xf…...

vue3中withDefaults是什么

问: const props withDefaults(defineProps<{// 数据列表lotteryList: { pic: string; name?: string }[];// 中奖idwinId: number;// 抽奖初始转动速度initSpeed: number;// 抽奖最快转动速度fastSpeed: number;// 抽奖最慢转动速度slowSpeed: number;// 基本圈数baseCi…...

Android进阶之路 - 盈利、亏损金额格式化

在金融类型的app中&#xff0c;关于金额、数字都相对敏感和常见一些&#xff0c;在此仅记录我在金融行业期间学到的皮毛&#xff0c;如后续遇到新的场景也会加入该篇 该篇大多采用 Kotlin 扩展函数的方式进行记录&#xff0c;尽可能熟悉 Kotlin 基础知识 兄弟 Blog StringUti…...

工业蒸汽量预测(速通一)

工业蒸汽量预测&#xff08;一&#xff09; 赛题理解1、评估指标2、赛题模型3、解题思路 理论知识1、变量识别2、变量分析3、缺失值处理4、异常值处理5、变量转换6、新变量生成 数据探索1、导包2、读取数据3、查看数据4、可视化数据分布4.1箱型图4.2获取异常数据并画图4.3直方图…...

机器学习的主要内容

分类任务 回归任务 有一些算法只能解决回归问题有一些算法只能解决分类问题有一些算法的思路既能解决回归问题&#xff0c;又能解决分类问题 一些情况下&#xff0c; 回归任务可以转化为分类任务&#xff0c; 比如我们预测学生的成绩&#xff0c;然后根据学生的成绩划分为A类、…...

华为OD机试真题-分积木-2023年OD统一考试(B卷)

题目描述: Solo和koko是两兄弟,妈妈给了他们一大堆积木,每块积木上都有自己的重量。现在他们想要将这些积木分成两堆。哥哥Solo负责分配,弟弟koko要求两个人获得的积木总重量“相等”(根据Koko的逻辑),个数可以不同,不然就会哭,但koko只会先将两个数转成二进制再进行加…...

SpringBoot自动装配原理及分析

一、什么是自动装配 在使用SpringBoot的时候&#xff0c;会自动将Bean装配到IoC容器中。例如我们在使用Redis数据库的时候&#xff0c;会引入依赖spring-boot-starter-data-redis。在引入这个依赖后&#xff0c;服务初始化的时候&#xff0c;会将操作Redis需要的组件注入到IoC…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...