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

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.length
  • 2 <= n <= 2000
  • 对于 i != 0 ,满足 0 <= parent[i] <= n - 1
  • parent[0] == -1
  • 0 <= num <= n - 1
  • 1 <= user <= 104
  • parent 表示一棵合法的树。
  • lockunlockupgrade 的调用 总共 不超过 2000 次。

相关文章:

2023-09-23力扣每日一题

链接&#xff1a; 1993. 树上的操作 题意 **Lock&#xff1a;**指定用户给指定节点 上锁 &#xff0c;上锁后其他用户将无法给同一节点上锁。只有当节点处于未上锁的状态下&#xff0c;才能进行上锁操作。**Unlock&#xff1a;**指定用户给指定节点 解锁 &#xff0c;只有当…...

C#中使用Newtonsoft.Charp实现Json对象序列化与反序列化

场景 C#中使用Newtonsoft.Json实现对Json字符串的解析&#xff1a; C#中使用Newtonsoft.Json实现对Json字符串的解析_霸道流氓气质的博客-CSDN博客 上面讲的对JSON字符串进行解析&#xff0c;实际就是JSON对象的反序列化。 在与第三方进行交互时常需要封装对象&#xff0c;…...

Golang开发--互斥锁和读写锁

互斥锁&#xff08;Mutex&#xff09; 互斥锁&#xff08;Mutex&#xff09;是一种并发控制机制&#xff0c;用于保护共享资源的访问。互斥锁用于确保在任何给定时间只有一个 goroutine&#xff08;Go 语言中的并发执行单元&#xff09;可以访问被保护的共享资源&#xff0c;从…...

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单播消息&#xff1a; nlmsg_unicast -> netlink_unicast -> netlink_sendskb -> __netlink_sendskb -> 把skb链入struct sock 的 sk_receive_queue 链表中&#xff0c;再调用sk->sk_data_ready(sk); -> sock_def_readable -> wak…...

软考高级+系统架构设计师教程+第二版新版+电子版pdf

注意&#xff01;&#xff01;&#xff01; 系统架构设计师出新版教程啦&#xff0c;2022年11月出版。所以今年下半年是新版第一次考试&#xff0c;不要再复习老版教程了&#xff0c;内容改动挺大的。 【内容简介】系统架构设计师教程&#xff08;第2版&#xff09;作为全国计…...

【产品运营】如何提升B端产品竞争力(下)

“好产品不是能力内核&#xff0c;做好产品的流程才是” 一、建立需求池和需求反馈渠道 需求池管理是B端产品进化最重要的环节&#xff0c;它的重要性远超产品设计、开发等其他环节。 维护需求池有主动和被动两种。 主动维护是产品经理在参与售前、迭代、交付、售后、竞品分…...

uniapp 微信小程序使用echarts

本文目的&#xff1a;通过分包的方式&#xff0c;尽可能在微信小程序中使用最新的echarts。 当然你也可以直接使用现成的uchart或者市场里别人封好的echarts. 准备工作 下载echarts-for-weixin源码。 复制ec-canvas文件夹以及下属文件&#xff0c;在uniapp项目中与pages同级的地…...

【漏洞复现】企望制造 ERP命令执行

漏洞描述 由于企望制造 ERP comboxstore.action接口权限设置不当&#xff0c;默认的配置可执行任意SQL语句&#xff0c;利用xp_cmdshell函数可远程执行命令&#xff0c;未经认证的攻击者可通过该漏洞获取服务器权限。 免责声明 技术文章仅供参考&#xff0c;任何个人和组织…...

2023 “华为杯” 中国研究生数学建模竞赛(E题)深度剖析|数学建模完整代码+建模过程全解全析

​ 问题一 血肿扩张风险相关因素探索建模 思路&#xff1a; 根据题目要求,首先需要判断每个患者是否发生了血肿扩张事件。根据定义,如果后续检查的血肿体积比首次检查增加≥6 mL或≥33%,则判断为发生了血肿扩张。 具体判断步骤: (1) 从表1中提取每个患者的入院首次影像检查…...

【腾讯云国际站】CDN内容分发网络特性介绍

为什么使用腾讯云国际站 CDN 内容分发网络&#xff1f; 当用户直接访问源站中的静态内容时&#xff0c;可能面临的体验问题&#xff1a; 客户离服务器越远&#xff0c;访问速度越慢。客户数量越多&#xff0c;网络带宽费用越高。跨境用户访问体验较差。 腾讯云国际站CDN 如何改…...

【工业机器人视觉】

工业机器人视觉 工业机器人的定位、抓取任务是工业生产线上一项重要的应用&#xff0c;一般通过预先示教的方式让机器人执行预定的指令动作。但是&#xff0c;一旦工件的状态发生改变时&#xff0c;机器人便无法完成工作任务。区别&#xff1a;就像人睁眼走直线和闭眼走直线。…...

跨域(浏览器)

跨域问题 是前端开发中常遇到的一个挑战。由于浏览器的同源策略限制&#xff0c;前端在发起异步请求时会受到限制&#xff0c;只能向相同源&#xff08;域名、协议和端口号都相同&#xff09;的服务器发送请求。当请求的目标服务器与当前页面的源不一致时&#xff0c;就会触发…...

Leetcode 2866. Beautiful Towers II

Leetcode 2866. Beautiful Towers II 1. 解题思路2. 代码实现 题目链接&#xff1a;2866. Beautiful Towers II 1. 解题思路 这一题其实思路上还是比较明显的&#xff0c;就是一个单调数组的问题&#xff0c;问题在于说如果具体去设计这个单调数组。 我们从题目出发&#x…...

电脑C盘爆红怎么办?(小白篇)

文章目录 前言&#xff1a;1、清理临时和系统文件2、更改电脑默认软件安装位置3、微信、QQ文件存储路径放在其它盘4、卸载一些不常用的软件彩蛋 前言&#xff1a; C盘作为电脑的系统盘&#xff0c;如果出现爆满或者剩余空间很小整个C盘变红&#xff0c;这样会导致电脑系统运行…...

Office Xml 2003转XLSX

一、使用到的依赖包 1、xelem-3.1.jar 下载地址&#xff1a;管网下载地址 2、poi-3.17.jar 下载地址&#xff1a;https://mvnrepository.com/artifact/org.apache.poi/poi 二、实现方法 1、Xml2003公式转XLSX公式算法 &#xff08;1&#xff09;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 语言标准库中的一个并发原语&#xff0c;用于等待一组并发操作的完成。它提供了一种简单的方式来跟踪一组 goroutine 的执行状态&#xff0c;并在所有 goroutine 完成后恢复执行。 下面是关于 sync.WaitGroup 的实现细节的详细解释&#xff1a; 创建 Wa…...

Linux命令教程:使用cat命令查看和处理文件

文章目录 教程&#xff1a;使用cat命令在Linux中查看和处理文件1. 引言2. cat命令的基本概述3. 查看文件内容4. 创建文件5. 文件重定向和管道6. 格式化和编辑文件7. 实际应用示例7.1 使用cat命令浏览日志文件7.2 利用cat命令合并多个配置文件7.3 使用cat命令将文件内容发送到其…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...