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

LeetCode每日一题:1993. 树上的操作(2023.9.23 C++)

目录

1993. 树上的操作

题目描述:

实现代码与解析:

模拟 + dfs

原理思路:


1993. 树上的操作

题目描述:

        给你一棵 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) 如果 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 会被 升级 

示例 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 次。

实现代码与解析:

模拟 + dfs

class LockingTree {
public:vector<int> h = vector<int>(2010, -1), e = vector<int>(2010, 0), ne = vector<int>(2010, 0);vector<int> parent; // 方便后面向上遍历int idx = 0; // 邻接表vector<int> flag = vector<int>(2010, 0); // 记录是否上锁void add(int a, int b){e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}LockingTree(vector<int>& parent) {for (int i = 1; i < parent.size(); i++) {add(parent[i], i); // 连接}this->parent = parent;}bool lock(int num, int user) {if (flag[num]) return false; // 已经有人上锁,不能再上flag[num] = user;return true;}bool unlock(int num, int user) {if (flag[num] != user) return false; // 非你上,不能解flag[num] = 0;return true;}bool upgrade(int num, int user) {// 当前节点和其祖先不能有锁for (int i = num; ~i; i = parent[i]) {if (flag[i]) return false;}// 子孙必须有至少一个上锁if (!hasLockedDescendant(num)) return false;// 解锁所有子孙节点unlockDescendants(num);// 上锁当前节点flag[num] = user;return true;}bool hasLockedDescendant(int num) {for (int i = h[num]; i != -1; i = ne[i]) {int child = e[i];if (flag[child] || hasLockedDescendant(child)) {return true;}}return false;}void unlockDescendants(int num) {for (int i = h[num]; i != -1; i = ne[i]) {int child = e[i];if (flag[child]) {flag[child] = 0;}unlockDescendants(child);}}
};

原理思路:

        其实只有upgrade麻烦一点,先利用parent数组,判断一下自己和祖先是否未上锁,其次判断子孙节点是否至少有一个上锁,如果满足以上条件,将子孙解锁并给自己上锁。注意顺序,和解锁时机,以免印象后续操作。

相关文章:

LeetCode每日一题:1993. 树上的操作(2023.9.23 C++)

目录 1993. 树上的操作 题目描述&#xff1a; 实现代码与解析&#xff1a; 模拟 dfs 原理思路&#xff1a; 1993. 树上的操作 题目描述&#xff1a; 给你一棵 n 个节点的树&#xff0c;编号从 0 到 n - 1 &#xff0c;以父节点数组 parent 的形式给出&#xff0c;其中 p…...

绿色计算产业发展白皮书:2022年OceanBase助力蚂蚁集团减排4392tCO2e

9 月 15 日&#xff0c;绿色计算产业联盟在 2023 世界计算大会期间重磅发布了《绿色计算产业发展白皮书&#xff08;2023 版&#xff09;》。蚂蚁集团作为指导单位之一&#xff0c;联合参与了该白皮书的撰写。 白皮书中指出&#xff0c;落实“双碳”战略&#xff0c;绿色计算已…...

阿里云通义千问14B模型开源!性能超越Llama2等同等尺寸模型

9月25日&#xff0c;阿里云开源通义千问140亿参数模型Qwen-14B及其对话模型Qwen-14B-Chat,免费可商用。Qwen-14B在多个权威评测中超越同等规模模型&#xff0c;部分指标甚至接近Llama2-70B。阿里云此前开源了70亿参数模型Qwen-7B等&#xff0c;一个多月下载量破100万&#xff0…...

两横一纵 | 寅家科技发布10年新征程战略

2023年9月22日&#xff0c;寅家科技“寅路向前”10年新征程战略发布会在上海举办&#xff0c;来自投资领域的东方富海、深创投、高新投等知名投资机构&#xff0c;一汽大众、一汽红旗、奇瑞汽车等主机厂&#xff0c;国家新能源汽车技术创新中心、梅克朗、芯驰科技、思特威等合作…...

二值贝叶斯滤波计算4d毫米波聚类目标动静属性

机器人学中有些问题是二值问题&#xff0c;对于这种二值问题的概率评估问题可以用二值贝叶斯滤波器binary Bayes filter来解决的。比如机器人前方有一个门&#xff0c;机器人想判断这个门是开是关。这个二值状态是固定的&#xff0c;并不会随着测量数据变量的改变而改变。就像门…...

【刷题笔记9.25】LeetCode:相交链表

LeetCode&#xff1a;相交链表 一、题目描述 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 二、分析及代码 方法一&#xff1a;使用哈希Set集合 &#xff08;注意…...

打造本地紧密链接的开源社区——KCC@长沙开源读书会openKylin爱好者沙龙圆满举办...

2023年9月9日&#xff0c;由开源社联合 openKylin 社区举办的 KCC长沙开源读书会&openKylin 爱好者沙龙&#xff0c;在长沙圆满举办。这是 KCC长沙首次正式进入公众视野&#xff0c;开展开源交流活动&#xff0c;也是 openKylin 社区长沙首场线下沙龙。长沙地区及其周边的众…...

Python 笔记03(多线程)

一 打开命令行&#xff0c;查看本机IP windows r 命令行输入&#xff1a;cmd ipconfig 然后查看IPv4的地址&#xff1a;192.168.1*6.1 ipconfig 二 函数式多进程 from multiprocessing import Process import os, timedef func(name):print(进程的ID&#xff1a;, os.g…...

mysql-4:SQL的解析顺序

SQL语句的解析顺序 文章目录 SQL语句的解析顺序编写顺序与解析顺序解析顺序关键字FROMONOUTER JOINWHEREGROUP BYHAVINGSELECTDISTINCTORDER BYLIMIT 解析流程流程分析流程说明WHERE条件解析顺序 编写顺序与解析顺序 编写顺序 SELECT DISTINCT < select_list > FROM &l…...

如何通过优化Read-Retry机制降低SSD读延迟?

近日,小编发现发表于2021论文中,有关于优化Read-Retry机制降低SSD读延迟的研究,小编这里给大家分享一下这篇论文的核心的思路,感兴趣的同学可以,可以在【存储随笔】VX公号后台回复“Optimizing Read-Retry”获取下载链接。 本文中主要基于Charge Trap NAND架构分析。NAND基…...

matlab自动生成FPGA rom源码

1 matlab 源码 close all clear all clci=0:1:(300000-100-1); x=300000./(100+i); x=x./2; x=round(...

消息队列(RabbitMQ+RocketMQ+Kafka)

消息队列是一种应用程序之间通过异步通信进行数据交换的通信模式 消息队列的类型&#xff1a; 点对点&#xff0c;一对一的消息传递模型&#xff0c;其中每个消息只能被一个接收者消费。发送者将消息发送到队列中&#xff0c;而接收者从队列中获取消息并进行处理&#xff0c;…...

python判断语句

1.布尔类型 进行判断&#xff0c;只有是(True&#xff1a;本质上是一个数字&#xff0c;记作1)和否(False&#xff1a;本质上是一个数字&#xff0c;记作0)。 定义变量存储布尔类型数据: 变量名称 布尔类型字面量 a True代码演示&#xff1a; a True print(type(a))输出结…...

C# 虚方法

在C#中&#xff0c;虚方法&#xff08;virtual methods&#xff09;是一种允许派生类&#xff08;子类&#xff09;覆盖&#xff08;重写&#xff09;基类&#xff08;父类&#xff09;中的方法的技术。虚方法的定义和使用如下&#xff1a; 基类中定义虚方法&#xff1a; pub…...

微信小程序,动态设置三级联动, 省市区街道

1.第一步 传parentId0 查询省份 2.第二步 选择省份,传pathId选择省份的pathId, 不传parentId,会查询出 市/县数据 3.第三步 根据选择县的parentId 查询街道数据,传parentId选择的县id 4.选择结果回显 显示所选择的 path 以/分割 取最后一级<van-dropdown-menu…...

Learn Prompt- Midjourney 图片生成:Image Prompts

Prompt 自动生成 前不久&#xff0c;Midjourney 宣布支持图片转 prompt 功能。 原始图片​ blueprint holographic design of futuristic Midlibrary --v 5Prompt 生成​ 直接输入 /describe 指令通过弹出窗口上传图像并发送&#xff0c;Midjourney 会根据该图像生成四种可…...

基于微信小程序的健身房私教预约平台设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…...

安卓Compose(二)

在上一篇博客中&#xff0c;我们已经了解了安卓Compose的一些基本概念以及使用方法&#xff0c;接下来我们将继续深入学习。 一、Compose的基础组件 文本组件(Text) 文本组件是Compose中最基本的组件之一&#xff0c;用于在界面上显示文本。使用方式如下&#xff1a; // 定…...

TCP 和 UDP哪个更好

传输控制协议 &#xff08;TCP&#xff09; 和用户数据报协议 &#xff08;UDP&#xff09; 是互联网的基础支柱&#xff0c;支持从网络源到目的地的不同类型的数据传输。TCP更可靠&#xff0c;而UDP优先考虑速度和效率。本文解释了两种协议的工作原理&#xff0c;并详细讨论了…...

Spring Boot 如何实现单点登录(SSO)

当今的应用程序越来越多地采用了微服务架构&#xff0c;这就引出了一个重要的问题&#xff1a;如何实现单点登录&#xff08;Single Sign-On&#xff0c;简称SSO&#xff09;来确保用户在多个微服务之间无需重复登录。Spring Boot是一个流行的Java框架&#xff0c;它提供了一些…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...