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数组,判断一下自己和祖先是否未上锁,其次判断子孙节点是否至少有一个上锁,如果满足以上条件,将子孙解锁并给自己上锁。注意顺序,和解锁时机,以免印象后续操作。

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

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

相关文章

2023-油猴(Tampermonkey)脚本推荐

2023-油猴&#xff08;Tampermonkey&#xff09;脚本推荐 知乎增强 链接 https://github.com/XIU2/UserScript https://greasyfork.org/zh-CN/scripts/419081 介绍 移除登录弹窗、屏蔽首页视频、默认收起回答、快捷收起回答/评论&#xff08;左键两侧&#xff09;、快捷回…

CeresPCL ICP精配准(点到面)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 ICP算法总共分为6个阶段,如下图所示: (1)挑选发生重叠的点云子集,这一步如果原始点云数据量比较巨大,一般会对原始点云进行下采样操作。 (2)匹配特征点。通常是距离最近的两个点,当然这需要视评判的准则而…

基于微信小程序的医院门诊体检预约管理系统设计与实现(源码+lw+部署文档+讲解等)

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

uni-app:实现页面效果1

效果 代码 <template><view><view class"add"><image :src"add_icon" mode""></image></view><view class"container_position"><view class"container_info"><view c…

使用datax将数据从InfluxDB抽取到TDengine过程记录

1. 编写InfluxDB数据查询语句 select time as ts,device as tbname, ip,device as district_code from "L2_CS" limit 1000 2. 创建TDengine表 create database if not exists sensor; create stable if not exists sensor.water(ts timestamp, ip varchar(50), …

怎样快速打开github.com

1访问这个网站很慢是因为有DNS污染&#xff0c;被一些别有用心的人搞了鬼了&#xff0c; 2还有一个重要原因是不同的DNS服务器解析的速度不一样。 1 建议设置dns地址为114.114.114.114.我觉得假设一个县城如果有一个DNS服务器的话&#xff0c;这个服务器很可能不会存储…

【STM32】IAP升级 预备知识

IAP&#xff08;In Application Programming&#xff09;简介 Flash够大的情况下&#xff0c;上电后的程序通过修改 MSP 的方式&#xff0c;可以在一块Flash上存在多个功能差异的程序。 IAP是为了在执行正常功能前&#xff0c;为了升级功能&#xff0c;提前运行的一段程序。这…

【【萌新的SOC学习之绪论】】

萌新的SOC学习之绪论 Vitis 统一软件平台的前身为 Xilinx SDK&#xff0c;从 Vivado 2019.2 版本开始&#xff0c;Xilinx SDK 开发环境已统一整合 到全功能一体化的 Vitis 中。Vitis 开发平台除了启动方式、软件界面、使用方法与 SDK 开发平台略有区别&#xff0c; 其他操作几…

LLM-TAP随笔——语言模型训练数据【深度学习】【PyTorch】【LLM】

文章目录 3、语言模型训练数据3.1、词元切分3.2、词元分析算法 3、语言模型训练数据 数据质量对模型影响非常大。 典型数据处理&#xff1a;质量过滤、冗余去除、隐私消除、词元切分等。 训练数据的构建时间、噪音或有害信息情况、数据重复率等因素都对模型性能有较大影响。训…

代数——第2章——群

第 2 章 群(Groups) II est peu de notions en mathematiques qui soient plus primitives que celle de loi de composition. (数学中很少有比合成律更原始的概念了。) --------------------------------------------------------Nicolas Bourbaki 2.1 合成律(LAWS OF CO…

数据链路层协议

文章目录 数据链路层协议0. 数据链路层解决的问题1. 以太网协议(1) 认识以太网(2) 以太网帧格式<1> 两个核心问题 (3) 认识MAC地址(4) 局域网通信原理(5) MTU<1> 认识MTU<2> MTU对IP协议的影响<3> MTU对UDP协议的影响<4> MTU对TCP协议的影响<…

Vue3 动态组件 component:is= 失效

错误代码 用Vue3&#xff0c;组件无需注册&#xff0c;所以就会提示“注册了不不使用”的报错&#xff0c; 于是用了异步注册&#xff0c;甚至直接为了不报错就在下面使用3个组件&#xff0c;有异步加载&#xff0c;但还是实现不了预期效果 <script setup> import { re…

如何设计一个 JVM 语言下的 LLM 应用开发框架?以 Chocolate Factory 为例

本文将介绍 Chocolate Factory 框架背后的一系列想法和思路。在我们探索和设计框架的过程中&#xff0c;受到了&#xff1a;LangChain4j、LangChain、LlamaIndex、Spring AI、Semantic Kernel、PromptFlow 的大量启发。 欢迎一起来探索&#xff1a;https://github.com/unit-mes…

历史高频行情数据存储最佳实践:DolphinDB Array Vector 使用指南

越来越多的机构使用 L1/L2 的快照行情数据进行量化金融的研究。作为一个高性能时序数据库&#xff0c;DolphinDB 非常适合存储和处理海量的历史高频行情数据。针对快照数据包含多档位信息的特点&#xff0c;DolphinDB 研发了一种方便、灵活且高效的数据结构——Array Vector&am…

[AI Agent学习] MetaGPT源码浅析

前言 工作上&#xff0c;需要使用AI Agent&#xff0c;所以需要深入学习一下AI Agent&#xff0c;光阅读各种文章&#xff0c;总觉无法深入细节&#xff0c;所以开看各类AI Agent相关的开源项目&#xff0c;此为第一篇&#xff0c;学习一下MetaGPT的源码。 基本目标 MetaGPT是一…

博客系统的自动化测试

本次自动化实战内容&#xff1a;本次测试根据博客管理系统这个项目&#xff0c;首先设计UI自动化测试用例&#xff0c;然后使用Selenium4自动化测试工具和JUnit5单元测试框架&#xff0c;实现web端的自动化测试。 本次项目总体实现思路&#xff1a;目录下有一个common包&#…

机器学习(19)---神经网络详解

神经网络 一、神经网络概述1.1 神经元模型1.2 激活函数 二、感知机2.1 概述2.2 实现逻辑运算2.3 多层感知机 三、神经网络3.1 工作原理3.2 前向传播3.3 Tensorflow实战演示3.3.1 导入数据集查看3.3.2 数据预处理3.3.3 建立模型3.3.4 评估模型 四、反向传播五、例题5.1 题15.2 题…

Day1-DeepWalk

论文《DeepWalk: Online Learning of Social Representations》 2014年发表在数据挖掘顶会ACM SIGKDD&#xff08;KDD&#xff09;上的论文 目的&#xff1a;学习节点表示 推动&#xff1a;将自然语言处理里面的无监督学习方法迁移至此 思路&#xff1a;将图结构序列化&#x…

ajax method to retrieve images as a blob

go 服务端&#xff1a; 就是先把这个图片读出来 然后返回二进制的数据 byteFile, err : ioutil.ReadFile("." "/processed/" uuidStr"processed.png")if err ! nil {fmt.Println(err)}c.Header("Content-Disposition", "att…

MYSQL不常用但好用写法

ORDER BY FIELD() 自定义排序逻辑 MySql 中的排序 ORDER BY 除了可以用 ASC 和 DESC&#xff0c;还可以通过 「ORDER BY FIELD(str,str1,…)」 自定义字符串/数字来实现排序。这里用 order_diy 表举例&#xff0c;结构以及表数据展示&#xff1a; ORDER BY FIELD(str,str1,…) …