2023-09-23力扣每日一题
链接:
1993. 树上的操作
题意
- **Lock:**指定用户给指定节点 上锁 ,上锁后其他用户将无法给同一节点上锁。只有当节点处于未上锁的状态下,才能进行上锁操作。
- **Unlock:**指定用户给指定节点 解锁 ,只有当指定节点当前正被指定用户锁住时,才能执行该解锁操作。
- Upgrade:指定用户给指定节点 上锁 ,并且将该节点的所有子孙节点 解锁 。只有如下 3 个条件全部满足时才能执行升级操作:
- 指定节点当前状态为未上锁。
- 指定节点至少有一个上锁状态的子孙节点(可以是 任意 用户上锁的)。
- 指定节点没有任何上锁的祖先节点。
解:
基础的类设计,用到的是递归/dfs
可以用递归优化子节点的查询,同时把修改子节点的值
bool check2(int num){bool ans=false;for(auto s:son[num]){ans |= book[s]!=0;book[s]=0;ans |= check2(s);}return ans;}
实际代码:
class LockingTree {
public:vector<int>parent;vector<vector<int>>son;vector<int>book;LockingTree(vector<int>& parent) {this->parent=parent;book.resize(parent.size());son.resize(parent.size());for(int i=0;i<parent.size();i++){if(parent[i]>=0){son[parent[i]].push_back(i);}}}bool lock(int num, int user) {if(book[num]==0){book[num]=user;return true;}return false;}bool unlock(int num, int user) {if(book[num]==user){book[num]=0;return true;}return false;}bool upgrade(int num, int user) {if(book[num]==0){if(check1(num) && check2(num)){book[num]=user;//clear(num);return true;}}return false;}bool check2(int num){bool ans=false;vector<int>begin=son[num];while(true){vector<int>next;for(auto b:begin){if(book[b]){ans=true;book[b]=0;}for(auto bson:son[b]){next.push_back(bson);}}if(next.empty()) break;begin=next;}return ans;}bool check1(int num){while(parent[num]!=-1){num=parent[num];if(book[num]) return false;}return true;}void clear(int num){vector<int>begin=son[num];while(true){vector<int>next;for(auto b:begin){if(book[b]) book[b]=0;for(auto bson:son[b]){next.push_back(bson);}}if(next.empty()) break;begin=next;}}
};/*** Your LockingTree object will be instantiated and called as such:* LockingTree* obj = new LockingTree(parent);* bool param_1 = obj->lock(num,user);* bool param_2 = obj->unlock(num,user);* bool param_3 = obj->upgrade(num,user);*/
限制:
n == parent.length2 <= n <= 2000- 对于
i != 0,满足0 <= parent[i] <= n - 1 parent[0] == -10 <= num <= n - 11 <= user <= 104parent表示一棵合法的树。lock,unlock和upgrade的调用 总共 不超过2000次。
相关文章:
2023-09-23力扣每日一题
链接: 1993. 树上的操作 题意 **Lock:**指定用户给指定节点 上锁 ,上锁后其他用户将无法给同一节点上锁。只有当节点处于未上锁的状态下,才能进行上锁操作。**Unlock:**指定用户给指定节点 解锁 ,只有当…...
C#中使用Newtonsoft.Charp实现Json对象序列化与反序列化
场景 C#中使用Newtonsoft.Json实现对Json字符串的解析: C#中使用Newtonsoft.Json实现对Json字符串的解析_霸道流氓气质的博客-CSDN博客 上面讲的对JSON字符串进行解析,实际就是JSON对象的反序列化。 在与第三方进行交互时常需要封装对象,…...
Golang开发--互斥锁和读写锁
互斥锁(Mutex) 互斥锁(Mutex)是一种并发控制机制,用于保护共享资源的访问。互斥锁用于确保在任何给定时间只有一个 goroutine(Go 语言中的并发执行单元)可以访问被保护的共享资源,从…...
Springboot 集成WebSocket作为客户端,含重连接功能,开箱即用
使用演示 public static void main(String[] args) throws Exception{//初始化socket客户端BaseWebSocketClient socketClient BaseWebSocketClient.init("传入链接");//发送消息socketClient.sendMessage("填写需要发送的消息", (receive) -> {//这里…...
java调整字符串
package 字符串练习;public class 调整字符串 {/* 如果调整成功则给提示,返回不成功也给提示调整 例如:abcde -> bcdea -> cdeab 就是把第一个值放到最后的位置上现在是给定两个字符串, 选定其中一个进行调整, (我们想一下,如果调整字符串的长度次,那不就是返回到原来的字…...
2023-9
内核向应用层发送netlink单播消息: nlmsg_unicast -> netlink_unicast -> netlink_sendskb -> __netlink_sendskb -> 把skb链入struct sock 的 sk_receive_queue 链表中,再调用sk->sk_data_ready(sk); -> sock_def_readable -> wak…...
软考高级+系统架构设计师教程+第二版新版+电子版pdf
注意!!! 系统架构设计师出新版教程啦,2022年11月出版。所以今年下半年是新版第一次考试,不要再复习老版教程了,内容改动挺大的。 【内容简介】系统架构设计师教程(第2版)作为全国计…...
【产品运营】如何提升B端产品竞争力(下)
“好产品不是能力内核,做好产品的流程才是” 一、建立需求池和需求反馈渠道 需求池管理是B端产品进化最重要的环节,它的重要性远超产品设计、开发等其他环节。 维护需求池有主动和被动两种。 主动维护是产品经理在参与售前、迭代、交付、售后、竞品分…...
uniapp 微信小程序使用echarts
本文目的:通过分包的方式,尽可能在微信小程序中使用最新的echarts。 当然你也可以直接使用现成的uchart或者市场里别人封好的echarts. 准备工作 下载echarts-for-weixin源码。 复制ec-canvas文件夹以及下属文件,在uniapp项目中与pages同级的地…...
【漏洞复现】企望制造 ERP命令执行
漏洞描述 由于企望制造 ERP comboxstore.action接口权限设置不当,默认的配置可执行任意SQL语句,利用xp_cmdshell函数可远程执行命令,未经认证的攻击者可通过该漏洞获取服务器权限。 免责声明 技术文章仅供参考,任何个人和组织…...
2023 “华为杯” 中国研究生数学建模竞赛(E题)深度剖析|数学建模完整代码+建模过程全解全析
问题一 血肿扩张风险相关因素探索建模 思路: 根据题目要求,首先需要判断每个患者是否发生了血肿扩张事件。根据定义,如果后续检查的血肿体积比首次检查增加≥6 mL或≥33%,则判断为发生了血肿扩张。 具体判断步骤: (1) 从表1中提取每个患者的入院首次影像检查…...
【腾讯云国际站】CDN内容分发网络特性介绍
为什么使用腾讯云国际站 CDN 内容分发网络? 当用户直接访问源站中的静态内容时,可能面临的体验问题: 客户离服务器越远,访问速度越慢。客户数量越多,网络带宽费用越高。跨境用户访问体验较差。 腾讯云国际站CDN 如何改…...
【工业机器人视觉】
工业机器人视觉 工业机器人的定位、抓取任务是工业生产线上一项重要的应用,一般通过预先示教的方式让机器人执行预定的指令动作。但是,一旦工件的状态发生改变时,机器人便无法完成工作任务。区别:就像人睁眼走直线和闭眼走直线。…...
跨域(浏览器)
跨域问题 是前端开发中常遇到的一个挑战。由于浏览器的同源策略限制,前端在发起异步请求时会受到限制,只能向相同源(域名、协议和端口号都相同)的服务器发送请求。当请求的目标服务器与当前页面的源不一致时,就会触发…...
Leetcode 2866. Beautiful Towers II
Leetcode 2866. Beautiful Towers II 1. 解题思路2. 代码实现 题目链接:2866. Beautiful Towers II 1. 解题思路 这一题其实思路上还是比较明显的,就是一个单调数组的问题,问题在于说如果具体去设计这个单调数组。 我们从题目出发&#x…...
电脑C盘爆红怎么办?(小白篇)
文章目录 前言:1、清理临时和系统文件2、更改电脑默认软件安装位置3、微信、QQ文件存储路径放在其它盘4、卸载一些不常用的软件彩蛋 前言: C盘作为电脑的系统盘,如果出现爆满或者剩余空间很小整个C盘变红,这样会导致电脑系统运行…...
Office Xml 2003转XLSX
一、使用到的依赖包 1、xelem-3.1.jar 下载地址:管网下载地址 2、poi-3.17.jar 下载地址:https://mvnrepository.com/artifact/org.apache.poi/poi 二、实现方法 1、Xml2003公式转XLSX公式算法 (1)Xml2003函数格式 SUM(R[-1…...
skyWalking搭建(一)
title: “SkyWalking搭建(一)” createTime: 2021-07-27T14:34:2108:00 updateTime: 2021-07-27T14:34:2108:00 draft: false author: “name” tags: [“skywalking”] categories: [“java”] description: “测试的” 基于 docker 部署 skywalking 并实现 SpringBoot 全链路…...
Golang开发--sync.WaitGroup
sync.WaitGroup 是 Go 语言标准库中的一个并发原语,用于等待一组并发操作的完成。它提供了一种简单的方式来跟踪一组 goroutine 的执行状态,并在所有 goroutine 完成后恢复执行。 下面是关于 sync.WaitGroup 的实现细节的详细解释: 创建 Wa…...
Linux命令教程:使用cat命令查看和处理文件
文章目录 教程:使用cat命令在Linux中查看和处理文件1. 引言2. cat命令的基本概述3. 查看文件内容4. 创建文件5. 文件重定向和管道6. 格式化和编辑文件7. 实际应用示例7.1 使用cat命令浏览日志文件7.2 利用cat命令合并多个配置文件7.3 使用cat命令将文件内容发送到其…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
