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);}
}

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

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

相关文章

工业三防平板助力MES系统打造工厂移动式生产管理

随着工业4.0时代的到来&#xff0c;智能制造、数字化车间等概念层出不穷&#xff0c;生产过程的可视化管理也成为了企业提升效率、优化生产的关键。而工业三防平板&#xff0c;凭借其坚固耐用、功能强大、便携易用等特性&#xff0c;成为了实现生产过程可视化管理的重要利器&am…

服务器网络磁盘挂载

一、Ping测试 先测试磁盘网络的连通性 例如&#xff1a;这里申请的网络磁盘是&#xff1a; 127.0.0.1:/shareData ping 127.0.0.1二、挂载 确认连通后&#xff0c;确定需要挂载的目录&#xff0c;这里服务器的挂载目录为&#xff1a;/data/share &#xff08;自主选择创建目录…

1985-2023年中国城市统计年鉴(PDF+EXCEL)

1985-2023年中国城市统计年鉴 1、时间&#xff1a;1985-2023年 2、格式&#xff1a;1985-2023年PDF版本&#xff0c;1993-2023年excel格式 3、说明&#xff1a;中国城市统计年鉴收录了全国各级城市社会经济发展等方面的主要统计数据&#xff0c;数据来源于各城市的相关部门。…

算法3:二分查找(下)

文章目录 寻找峰值寻找旋转数组最小值 寻找峰值 class Solution { public:int findPeakElement(vector<int>& nums) {int left 0, right nums.size() - 1;while(left < right){int mid left (right - left) / 2;if(nums[mid] < nums[mid 1])left mid 1;…

漏洞复现-F5 BIG-IP 存在远程代码执行漏洞 (CVE-2023-46747)

1.漏洞描述 F5 Networks是全球范围内应用交付网络&#xff08;ADN&#xff09;领域的知名厂商&#xff0c;致力于帮助全球大型企业和服务提供商实现虚拟化、云计算和灵活的IT业务服务。。 F5 BIG-IP 存在远程代码执行漏洞。未经身份验证的攻击者可能会绕过配置实用程序身份验…

大话设计模式:七大设计原则

目录 一、单一职责原则&#xff08;‌Single Responsibility Principle, SRP&#xff09;‌ 二、开放封闭原则&#xff08;‌Open-Closed Principle, OCP&#xff09; 三、依赖倒置原则&#xff08;‌Dependency Inversion Principle, DIP&#xff09; 四、里氏替换原则&am…

Java事务失效

目录 传送门一、概念1、事务的传播类型2、isolation3、Transactionnal注解属性 二、事务失效场景1、异常捕获2、异步处理3、final修饰事务方法4、非public5、T范围小了6、不加T或者事务传播用了NOT_SUPPORTED这种不支持事务7、数据库MyISAM不支持事务8、事务方法未被Spring管理…

Unity URP 曲面细分学习笔记

学百人时遇到了曲面着色器的内容&#xff0c;有点糊里糊涂&#xff0c;于是上知乎找到了两篇大佬的文章 Unity URP 曲面细分 和 Unity曲面细分笔记&#xff0c;本文只是自己做学习记录使用 1.曲面细分与镶嵌 曲面细分或细分曲面&#xff08;Subdivision surface&#xff09;是…

字节跳动发Seed-TTS语音合成模型,可模仿任意人的声音,效果逼真

前期我们介绍过很多语音合成的模型&#xff0c;比如ChatTTS&#xff0c;微软语音合成大模型等&#xff0c;随着大模型的不断进步&#xff0c;其合成的声音基本跟真人没有多大的区别。本期介绍的是字节跳动自家发布的语音合成模型Seed-TTS。 Seed-TTS 推理包含四个功能模块&…

无人机之热成像篇

一、定义 无人机热成像技术是指将热成像相机安装在无人机云台上&#xff0c;通过无人机的高空飞行能力和云台的稳定性&#xff0c;结合红外热成像技术对目标区域进行非接触式的温度测量和图像采集。该技术利用物体发出的红外辐射来生成图像&#xff0c;通过测量物体表面温度分布…

Leetcode JAVA刷刷站(8)字符串转换整数

一、题目概述 二、思路方向 要实现这个功能&#xff0c;我们可以遵循以下步骤来编写 myAtoi 函数&#xff1a; 去除前导空格&#xff1a;使用循环或字符串的 trim() 方法&#xff08;虽然直接操作字符串更高效的方式是使用循环&#xff09;。检查符号&#xff1a;记录第一个非…

nodejs 生成随机邮箱

首先安装依赖&#xff1a; npm install faker 示例代码&#xff1a; const faker require(faker); const fs require(node:fs) function generateRandomEmail(num){let str for (let i 0; i < num; i) {str faker.internet.email() &:focus:&;}fs.writeFil…

魔众文库系统v7.0.0版本推荐店铺功能,管理菜单逻辑优化

推荐店铺功能&#xff0c;管理菜单逻辑优化 [新功能] RandomImageProvider 逻辑升级重构&#xff0c;支持更丰富的随机图片生成 [新功能] 资源篮订单参数字段 [新功能] 首页推荐店铺功能&#xff0c;需要在后台 文库系统 → 文库店铺 开启推荐 [系统优化] Grid 快捷编辑请求…

告别DockerHub 镜像下载难题:掌握高效下载策略,畅享无缝开发体验

告别DockerHub 镜像下载难题:掌握高效下载策略,畅享无缝开发体验 1. 介绍 1.1 DockerHub简介 Docker Hub 是 Docker 提供的一项服务,用于与您的团队查找和共享容器映像。 它是世界上最大的容器映像存储库,其中包含一系列内容源,包括容器社区开发人员,开源项目和独立软…

【Kubernetes】Service 类型

Service 类型 1.NodePort2.ClusterlP3.LoadBalance4.ExternalName 在《Service 概念与实战》一文中&#xff0c;Service 的发布使用的是 NodePort 类型。除此之外&#xff0c;Service 的发布还支持 ClusterlP、LoadBalancer 和 ExternalName 这 3 种类型。 1.NodePort 在把 Se…

基于微信小程序的小区业主服务系统(源码+论文+部署讲解等)

博主介绍&#xff1a;✌全网粉丝10W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术栈介绍&#xff1a;我是程序员阿龙&#xff…

SOMEIP_ETS_033:echoUINT8ArrayMinSize_too_short

测试目的&#xff1a; 验证DUT是否能够正确处理小于最小尺寸&#xff08;少于3个元素&#xff09;的UINT8数组参数&#xff0c;并返回相应的错误消息。 描述 本测试用例旨在检验DUT在接收到长度不足3个元素的UINT8数组参数时&#xff0c;是否能够返回错误消息MALFORMED_MESS…

【电路笔记】-L 型衰减器

L 型衰减器 文章目录 L 型衰减器1、概述2、等阻抗L型衰减器3、不等阻抗的 L型衰减器4、L型衰减器示例25、总结L型衰减器是一个简单的电阻分压器网络,可用作固定无源衰减器以降低信号幅度。 1、概述 就其基本形式而言,L 型衰减器只不过是一个非常简单的分压器网络,用于许多电…

数据结构实验:排序算法(附c++源码:冒泡、选择、希尔、快速、堆排序)

实验内容&#xff1a; 输入一组关键字序列&#xff0c;分别实现下列排序算法: 1.编写函数&#xff0c;实现简单选择排序、直接插入排序和冒泡排序算法。 2.编写函数&#xff0c;实现希尔排序算法。 3.编写函数&#xff0c;实现快速排序算法。 4.编写函数&#xff0c;实现堆…

入门 PyQt6 看过来(项目)26 在线购物-主页面

功能导航页面很简单&#xff0c;就几个按钮功能。效果如下图&#xff1a; 1 主界面 ​ 包含 “商品选购”、”下单结算“、”销售分析“四个按钮以及“功能导航”标题。 2 工程目录 首先先创建工程目录及子目录&#xff1a; ​ 3 代码 主窗口文件为Main.py&#xff0c;其…