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

Leetcode - 周赛409

目录

一,3242. 设计相邻元素求和服务

二,3243. 新增道路查询后的最短距离 I

三,3244. 新增道路查询后的最短距离 II

四,3245. 交替组 III


一,3242. 设计相邻元素求和服务

本题纯模拟,代码如下:

class neighborSum {int[][] t;int n, m;public neighborSum(int[][] grid) {n = grid.length;m = grid[0].length;t = grid;}public int adjacentSum(int value) {int x=-1, y=-1;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(t[i][j] == value){x = i;y = j;break;}}if(x!=-1 && y!=-1) break;}int ans = 0;if(x>0) ans += t[x-1][y];if(y>0) ans += t[x][y-1];if(x+1<n) ans += t[x+1][y];if(y+1<m) ans += t[x][y+1];return ans;}public int diagonalSum(int value) {int x=-1, y=-1;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(t[i][j] == value){x = i;y = j;break;}}if(x!=-1 && y!=-1) break;}int ans = 0;if(x>0 && y>0) ans += t[x-1][y-1];if(x>0 && y+1<m) ans += t[x-1][y+1];if(x+1<n && y>0) ans += t[x+1][y-1];if(x+1<n && y+1<m) ans+=t[x+1][y+1];return ans;}
}

二,3243. 新增道路查询后的最短距离 I

本题每次查询可以使用 bfs 计算出从 0 到 n-1 的最短路径长度,代码如下:

class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {int t = queries.length;int[] ans = new int[t];List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e->new ArrayList<>());for(int i=0; i<n-1; i++){g[i].add(i+1);}int k = 0;for(int[] q : queries){g[q[0]].add(q[1]);Queue<Integer> que = new LinkedList<>();boolean[] vis = new boolean[n];vis[0] = true;que.add(0);int cnt = 0;while(!que.isEmpty() && ans[k] == 0){int size = que.size();while(size-- > 0){int poll = que.poll();for(int x : g[poll]){if(!vis[x]){vis[x] = true;que.add(x);if(x == n-1){ans[k] = cnt+1;}}}}cnt++;}k++;}return ans;}
}

三,3244. 新增道路查询后的最短距离 II

本题和上一题不同,它多给了一个条件不存在两个查询满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1],也就是说它不会出现两个集合相交的情况。

方法一:

  • 可以使用一个有序集合存储每个点,对于每一个查询,我们直接删除在(queries[i][0],queries[i][1])范围内的点,这时的答案就是集合的大小 - 1,代码如下:
class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {TreeSet<Integer> set = new TreeSet<>();for(int i=0; i<n; i++) set.add(i);int[] ans = new int[queries.length];for(int i=0; i<queries.length; i++){int l = queries[i][0], r = queries[i][1];找到>=l+1的最小的值,使用红黑树实现,时间复杂度O(logn)Integer ceiling = set.ceiling(l+1);//删除(l,r)之间的点while(ceiling != null && ceiling < r){set.remove(ceiling);ceiling = set.ceiling(l+1);}ans[i] = set.size()-1;}return ans;}
}

方法二:并查集

  • 可以把 i -> i + 1 的这段路当成一个点,这时就可以把它当成一个互不相连的图,画个图理解一下:

class Solution {int[] f;int find(int x){if(f[x] != x){f[x] = find(f[x]);}return f[x];}public int[] shortestDistanceAfterQueries(int n, int[][] queries) {f = new int[n];for(int i=1; i<n; i++){f[i] = i;}int[] ans = new int[queries.length];int cnt = n-1;for(int i=0; i<queries.length; i++){int l = queries[i][0] + 1;int r = queries[i][1];int j = find(l), fr = find(r);while(j < fr){//将节点 [l+1, R] 联通 cnt--;f[j] = fr;j = find(j+1);}ans[i] = cnt;}return ans;}
}

四,3245. 交替组 III

代码如下: 

class Fenwick{int[][] t;public Fenwick(int n){t = new int[n][2];}void update(int size, int op){int i=t.length-size;while(i < t.length){t[i][0] += op;t[i][1] += op*size;i += i & -i;}}int[] query(int size){int cnt = 0, sum = 0;int i = t.length - size;while(i > 0){cnt += t[i][0];sum += t[i][1];i -= i & -i;}return new int[]{cnt, sum};}
}
class Solution {public List<Integer> numberOfAlternatingGroups(int[] colors, int[][] queries) {List<Integer> ans = new ArrayList<>();TreeSet<Integer> set = new TreeSet<>();int n = colors.length;Fenwick f = new Fenwick(n+1);for(int i=0; i<n; i++){if(colors[i] == colors[(i+1)%n]){add(set, f, n, i);}}for(int[] q : queries){if(q[0] == 1){if(set.isEmpty()){ans.add(n);}else{int[] res = f.query(q[1]);ans.add(res[1]-res[0]*(q[1]-1));}}else{int i = q[1];if(colors[i] == q[2]) continue;int pre = (i - 1 + n) % n;int nxt = (i + 1) % n;if(colors[pre] == colors[i]){del(set, f, n, pre);}if(colors[nxt] == colors[i]){del(set, f, n, i);}colors[i] ^= 1;if(colors[pre] == colors[i]){add(set, f, n, pre);}if(colors[nxt] == colors[i]){add(set, f, n, i);}}}return ans;}private void add(TreeSet<Integer> set, Fenwick f, int n, int i){if(set.isEmpty()){f.update(n, 1);}else{update(set, f, n, i, 1);}set.add(i);}private void del(TreeSet<Integer> set, Fenwick f, int n, int i){set.remove(i);if(set.isEmpty()){f.update(n, -1);}else{update(set, f, n, i, -1);}}private void update(TreeSet<Integer> set, Fenwick f, int n, int i, int op){Integer pre = set.floor(i);if(pre == null){pre = set.last();}Integer nxt = set.ceiling(i);if(nxt == null){nxt = set.first();}f.update((nxt-pre+n-1)%n+1, -op);f.update((i-pre+n)%n, op);f.update((nxt-i+n)%n, op);}
}

相关文章:

Leetcode - 周赛409

目录 一&#xff0c;3242. 设计相邻元素求和服务 二&#xff0c;3243. 新增道路查询后的最短距离 I 三&#xff0c;3244. 新增道路查询后的最短距离 II 四&#xff0c;3245. 交替组 III 一&#xff0c;3242. 设计相邻元素求和服务 本题纯模拟&#xff0c;代码如下&#xff…...

突破百度网盘的下载限速,两种方法教会你【超详细】

一、前言 Hello&#xff0c;大家后&#xff0c;我是博主英杰&#xff0c;前几天&#xff0c;我在使用百度网盘过程中&#xff0c;下载速度极慢&#xff0c;自己作为一个白嫖党&#xff0c;开会员也是心疼那点钱&#xff0c;所以在网上找了几个有效解决百度网盘限速问题的教程&a…...

整理 酷炫 Flutter 优质 布局、交互 开源App

xtimer-flutter-app Flutter 计时器应用 项目地址&#xff1a;https://github.com/pedromassango/xtimer-flutter-app 项目Demo&#xff1a;https://download.csdn.net/download/qq_36040764/89631382...

【PyCharm怎么同时打开多个项目】

问题描述&#xff1a; 之前点击了“dont ask again”&#xff0c;再也不能同时打开两个或多个项目了。 解决&#xff1a; file->settings->appearance->system settings->project->选择ask...

使用 ProcDump 调试 Linux

Debug Linux using ProcDump By Gaurav Kamathe July 17, 2020 译者&#xff1a;wxy 校对&#xff1a;wxy 微软越来越心仪 Linux 和开源&#xff0c;这并不是什么秘密。在过去几年中&#xff0c;该公司稳步地增加了对开源的贡献&#xff0c;包括将其部分软件和工具移植到 L…...

2023年中国城市统计年鉴(PDF+excel)

2023年中国城市统计年鉴 1、时间&#xff1a;1985-2023年 2、格式&#xff1a;PDFexcel 3、说明&#xff1a;中国城市统计年鉴收录了全国各级城市社会经济发展等方面的主要统计数据&#xff0c;数据来源于各城市的相关部门。本年鉴内容共分四个部分&#xff1a;第一部分是全…...

自用 K8S 资源对象清单 YAML 配置模板手册-1

Linux 常用资源对象清单配置速查手册-1 文章目录 1、Pod 容器集合2、Pod 的存储卷3、Pod 的容器探针4、ResourceQuota 全局资源配额管理5、PriorityClass 优先级类 管理多个资源对象清单文件常用方法&#xff1a; 使用 sed 流式编辑器批量修改脚本键值进行资源清单的创建&am…...

【数据库】事务 | 视图 | 自定义函数创建

1、事物及其特征 事物机制的应用&#xff1a;淘宝订单交易&#xff0c;微信转账等。 视图--------筛子---------过滤-------筛选想要的信息 数据库只存放了视图对应的SQL语句。 视图是一个虚拟的表&#xff0c;本质是一个虚拟的SQL命令集合。 &#xff08;1&#xff09;创建…...

Linux---进程(5)---进程地址空间

目录 预备知识 进程地址空间 什么是进程地址空间 为什么要存在进程地址空间和页表 缺页中断 预备知识 我们在学习语言的时候&#xff0c;一般都会了解到内存区域划分&#xff0c;下面了解一下Linux的内存区域划分。 通过上图&#xff0c;我们了解到 1、堆区向上增长&…...

C语言实现数据结构之队列

目录 队列一. 队列的概念及结构二. 队列的实现1. 要实现的功能2 具体的实现2.1 结构体2.2 初始化2.3 入队列2.4 出队列2.5 返回队首元素2.6 返回队尾元素2.7 队列元素个数2.8 队列判空2.9 队列销毁 三. 队列相关OJ题设计循环队列用队列实现栈用栈实现队列 四. 概念选择题五. 参…...

写一个Vue2和vue3的自定义指令(以复制指定作为示例)

文章目录 一、自定义指令是什么&#xff1f;二、自定义指令有啥用&#xff1f;三、自定义指令怎么用&#xff1f;1.自定义指令的参数2.自定义指令的钩子函数&#xff08;1&#xff09;五个钩子函数的说明&#xff08;2&#xff09;钩子函数的参数(主要参数&#xff1a;el和valu…...

MySQL —— 聚合查询,分组查询 与 联合查询

聚合函数 常见的统计总数、计算平局值等操作&#xff0c;可以使用聚合函数来实现&#xff0c;常见的聚合函数有&#xff1a; 函数说明count()统计数据总数sum()求和avg()求平均值max()求最大值min()求最小值 注意凡是涉及运算的&#xff0c;数据库会自动掉 NULL 值 注意NULL …...

Spring声明式事务失效场景

Spring声明式事务失效场景 背景搭建测试环境测试事务失效场景Transactional 注解标注在 private 方法上异常被 catch 了&#xff0c;事务失效方法抛出的是受检异常&#xff0c;事务也会失效事务传播行为配置不合理导致事务失效 背景 Spring 针对 Java Transaction API (JTA)、…...

基于SpringBoot+UniAPP宠物食品外卖点单小程序的设计与实现》

✅博主简介&#xff1a;Java 全栈开发工程师&#xff0c;抖音优质技术创作者&#xff0c;日常分享实用的前端、后端、运维开发技术。 ✅技术栈&#xff1a;Java、SpringBoot、Vue、React、Node.js、Nest.js、Nuxt.js、uni-app ✅技术擅长&#xff1a;计算机毕设选题、开题报告、…...

ssrf 内网访问 伪协议 读取文件 端口扫描

SSRF&#xff08;Server-Side Request Forgery&#xff0c;服务器侧请求伪造&#xff09;是一种利用服务器发起网络请求的能力来攻击内网资源或执行其他恶意活动的技术。SSRF可以用于访问通常不可由外部直接访问的内网资源&#xff0c;读取文件&#xff0c;甚至进行端口扫描。以…...

发布包到npm

目录 注册npm账号 创建包 登录npm 上架包 更新包 删除包 注册npm账号 首先注册npm账号&#xff1a;npm | Sign Up (npmjs.com) 创建包 可以在桌面上新建一个文件夹&#xff1a;文件夹名随便起&#xff0c;但是别跟npm已经上架的包名重复了 可以通过下面的指令查看&…...

Python | Leetcode Python题解之第324题摆动排序II

题目&#xff1a; 题解&#xff1a; def quickSelect(a: List[int], k: int) -> int:seed(datetime.datetime.now())shuffle(a)l, r 0, len(a) - 1while l < r:pivot a[l]i, j l, r 1while True:i 1while i < r and a[i] < pivot:i 1j - 1while j > l an…...

IGModel——提高基于 GNN与Attention 机制的方法在药物发现中的实用性

导言 深度学习在药物发现&#xff08;发现治疗药物&#xff09;领域的应用以及传统方法面临的挑战。 药物&#xff08;尤其是我们将在本文中讨论的被称为抑制剂的药物&#xff09;通过与在人体中发挥不良功能的蛋白质结合并改变这些蛋白质的功能来发挥治疗效果。因此&#xf…...

AArch64中的寄存器

目录 通用寄存器 其他寄存器 系统寄存器 通用寄存器 大多数A64指令在寄存器上操作。该架构提供了31个通用寄存器。 每个寄存器可以作为64位的X寄存器&#xff08;X0..X30&#xff09;使用&#xff0c;或者作为32位的W寄存器&#xff08;W0..W30&#xff09;使用。这两种是查…...

树莓派Pico 2来了

这两天开源圈的大事之一&#xff0c;就是树莓派基金会发布了树莓派Pico 2。 帖子原文&#xff1a;Raspberry Pi Pico 2, our new $5 microcontroller board, on sale now 总结一些关键信息&#xff1a; 产品发布&#xff1a;Raspberry Pi Pico 2 是 Raspberry Pi 基金会推出的…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

【工具教程】多个条形码识别用条码内容对图片重命名,批量PDF条形码识别后用条码内容批量改名,使用教程及注意事项

一、条形码识别改名使用教程 打开软件并选择处理模式&#xff1a;打开软件后&#xff0c;根据要处理的文件类型&#xff0c;选择 “图片识别模式” 或 “PDF 识别模式”。如果是处理包含条形码的 PDF 文件&#xff0c;就选择 “PDF 识别模式”&#xff1b;若是处理图片文件&…...

Async-profiler 内存采样机制解析:从原理到实现

引言 在 Java 性能调优的工具箱中&#xff0c;async-profiler 是一款备受青睐的低开销采样分析器。它不仅能分析 CPU 热点&#xff0c;还能精确追踪内存分配情况。本文将深入探讨 async-profiler 实现内存采样的多种机制&#xff0c;结合代码示例解析其工作原理。 为什么需要内…...

20250607在荣品的PRO-RK3566开发板的Android13系统下实现长按开机之后出现插入适配器不会自动启动的问题的解决

20250607在荣品的PRO-RK3566开发板的Android13系统下实现长按开机之后出现插入适配器不会自动启动的问题的解决 2025/6/7 17:20 缘起&#xff1a; 1、根据RK809的DATASHEET&#xff0c;短按开机【100ms/500ms】/长按关机&#xff0c;长按关机。6s/8s/10s 我在网上找到的DATASHE…...