当前位置: 首页 > 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命令将文件内容发送到其…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...