【力扣周赛】第 361 场周赛(⭐前缀和+哈希表 树上倍增、LCA⭐)
文章目录
- 竞赛链接
- Q1:7020. 统计对称整数的数目
- 竞赛时代码——枚举预处理
- Q2:8040. 生成特殊数字的最少操作(倒序遍历、贪心)
- 竞赛时代码——检查0、00、25、50、75
- Q3:2845. 统计趣味子数组的数目
- 竞赛时代码——前缀和+哈希表
- 相似题目——1590. 使数组和能被 P 整除(确实很相似的题目)
- Q4:2846. 边权重均等查询⭐⭐⭐⭐⭐
- 读题
- 解法——树上倍增、最近公共祖先LCA
- 相关题目
- 成绩记录
竞赛链接
https://leetcode.cn/contest/weekly-contest-361/
Q1:7020. 统计对称整数的数目
https://leetcode.cn/problems/count-symmetric-integers/
提示:
1 <= low <= high <= 10^4
竞赛时代码——枚举预处理
预处理所有数字是否为对称整数。
cnt[i]表示 <=i 的数字中有几个对称整数。
class Solution {static int[] cnt = new int[10005];// 预处理static {for (int i = 1; i <= 10001; ++i) {cnt[i] = cnt[i - 1];if (op(i)) cnt[i]++;}}public int countSymmetricIntegers(int low, int high) {return cnt[high] - cnt[low - 1];}// 判断x是否为对称整数public static boolean op(int x) {List<Integer> ls = new ArrayList<>();while (x != 0) {ls.add(x % 10);x /= 10;}int n = ls.size();if (n % 2 == 1) return false;int a = 0, b = 0;for (int i = 0; i < n; ++i) {if (i < n / 2) a += ls.get(i);else b += ls.get(i);}return a == b;}
}
Q2:8040. 生成特殊数字的最少操作(倒序遍历、贪心)
https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/
提示
1 <= num.length <= 100
num 仅由数字 '0' 到 '9' 组成
num 不含任何前导零
竞赛时代码——检查0、00、25、50、75
检查位置最靠后的 00、25、50、75 的位置。
如果都不存在但是有 0 的话,答案则为 n - 1。(因为 0 可以不删)
class Solution {public int minimumOperations(String num) {int n = num.length();boolean f0 = false, f5 = false;for (int i = n - 1; i >= 0; --i) {char ch = num.charAt(i);if (ch == '0') {if (f0) return n - i - 2; // 检查00f0 = true;} else if (ch == '5') {if (f0) return n - i - 2;; // 检查50f5 = true;} else if (ch == '2' || ch == '7') {if (f5) return n - i - 2;; // 检查25,75}}if (f0) return n - 1; // 检查是否有0return n;}
}
Q3:2845. 统计趣味子数组的数目
https://leetcode.cn/problems/count-of-interesting-subarrays/
提示:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= modulo <= 10^9
0 <= k < modulo
竞赛时代码——前缀和+哈希表
使用前缀和数组可以快速求出从 l ~ r 之间满足要求的元素个数 cnt。
求出前缀和数组之后,从前往后依次枚举下标。对于当前的前缀和 sum[r],前面有若干个满足 (sum[r] - sum[x]) % modulo == k 的下标,这些下标的共同特征是:它们的值 sum[x] = (sum[r] - k + modulo) % modulo。
在枚举的过程中用哈希表 cnt 记录下各种 sum[i] 数值的数量,即 cnt[[sum[i]]++
。
这样当枚举到 当前的前缀和为 sum[r] 时,与他相匹配的前缀和设为 x,则有 (sum[r] - x) % modulo == k,解得 x = (sum[r] - k + modulo) % modulo。 就可以快速找到 sum[r] 之前有几个可以和当前下标配对的下标 l,组成符合条件的区间 l ~ r,从哈希表中可以快速找出有 cnt[x] 的值个可以匹配。
即——在 r 之前有 cnt[x] 个下标,分别为 l1、l2…、lx 满足区间 li ~ r 之间的 cnt % modulo == k。
class Solution {public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {int n = nums.size();int[] x = new int[n], sum = new int[n + 1]; // x是原始数组,sum是前缀和数组Map<Integer, Integer> cnt = new HashMap<>(); // 存储各个余数为key的位置的数量cnt.put(0, 1);long ans = 0;for (int i = 0; i < n; ++i) {if (nums.get(i) % modulo == k) x[i] = 1;sum[i + 1] = (sum[i] + x[i]) % modulo; // 前缀和int r = sum[i + 1];ans += cnt.getOrDefault((r - k + modulo) % modulo, 0);cnt.merge(r, 1, Integer::sum);}return ans;}
}
相似题目——1590. 使数组和能被 P 整除(确实很相似的题目)
https://leetcode.cn/problems/make-sum-divisible-by-p/description/
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109
class Solution {public int minSubarray(int[] nums, int p) {int n = nums.length;int[] sum = new int[n + 1]; // 前缀和数组for (int i = 0; i < n; ++i) {sum[i + 1] = (sum[i] + nums[i]) % p;}int t = sum[n], ans = n;if (t == 0) return 0;Map<Integer, Integer> idx = new HashMap<>(); // 记录各个前缀和出现的下标idx.put(0, -1);for (int i = 0; i < n; ++i) {// x是当前前缀和,y是和x配对组成t的前缀和int x = sum[i + 1], y = (x - t + p) % p; // 如果之前有y,就尝试更新答案 if (idx.containsKey(y)) ans = Math.min(ans, i - idx.get(y));idx.put(x, i);}return ans == n? -1: ans;}
}
Q4:2846. 边权重均等查询⭐⭐⭐⭐⭐
https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/
提示:
1 <= n <= 10^4
edges.length == n - 1
edges[i].length == 3
0 <= ui, vi < n
1 <= wi <= 26
生成的输入满足 edges 表示一棵有效的树
1 <= queries.length == m <= 2 * 10^4
queries[i].length == 2
0 <= ai, bi < n
读题
给了一个 n 个节点的无向图。
每次查询,给两个点 a ,b。求 a 和 b 路径之间的所有边权,都变成相等需要操作几步——实际上是求 a 和 b 之间有几条边,其中出现次数最多的边权出现了几次。
解法——树上倍增、最近公共祖先LCA
关于这部分的知识点总结可见:【算法】树上倍增 & LCA
https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/solutions/2424060/lca-mo-ban-by-endlesscheng-j54b/
思路总结:
用树上倍增的思想维护:各个节点的深度、各个节点和父节点之间各种边权的数量。
求答案时,先将两个节点放在同一深度,实现方法是 y 先跳 d[y] - d[x] 的深度。
然后,x 和 y 一起往上跳。
class Solution {public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {// 临界表存储无向图List<int[]>[] g = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>());for (int[] e: edges) {int x = e[0], y = e[1], w = e[2] - 1;g[x].add(new int[]{y, w});g[y].add(new int[]{x, w});}int m = 32 - Integer.numberOfLeadingZeros(n); // n的二进制长度int[][] pa = new int[n][m]; // pa[x][i]表示节点x的第2^i个父节点for (int i = 0; i < n; ++i) {Arrays.fill(pa[i], -1); // -1表示没有这个父节点}int[][][] cnt = new int[n][m][26]; // cnt[x][i][w]记录节点x和父节点之间的边权为w的个数int[] depth = new int[n]; // 记录n个节点的深度// 使用 dfs 从0节点开始 初始化pa、cnt 计算depthdfs(0, -1, g, pa, cnt, depth);// 计算 pa 和 cnt// 先枚举i,(也就是先算出所有节点的爷爷、再求所有节点爷爷的爷爷...for (int i = 0; i < m - 1; ++i) { // 先枚举i,范围是0~m-2for (int x = 0; x < n; ++x) { // 再枚举xint p = pa[x][i]; // 取出节点x的第2^i个父节点if (p != -1) { int pp = pa[p][i]; // 取出节点x的第2^i个父节点的第2^i个父节点pa[x][i + 1] = pp; // 赋值——x的第2^(i+1)个父节点// 通过cnt[x][i]和cnt[p][i]计算 cnt[x][i+1]for (int j = 0; j < 26; ++j) {cnt[x][i + 1][j] = cnt[x][i][j] + cnt[p][i][j];}}}}// 计算答案int[] ans = new int[queries.length];for (int qi = 0; qi < queries.length; qi++) { // 枚举每一个查询int x = queries[qi][0], y = queries[qi][1];int pathLen = depth[x] + depth[y]; // x的深度和y的深度int[] cw = new int[26]; // 统计各种边权在x和y之间出现的次数// 让 x 作为深度更小的那个节点if (depth[x] > depth[y]) {int t = x;x = y;y = t;}// 让 y 和 x 在同一深度(先让 y 跳 depth[y]-depth[x])for (int k = depth[y] - depth[x]; k > 0; k &= k - 1) {int i = Integer.numberOfTrailingZeros(k);int p = pa[y][i];for (int j = 0; j < 26; ++j) {cw[j] += cnt[y][i][j];}y = p;}// y和x位于同一深度的时候可能位于同一个节点,那么就不用继续计算了if (y != x) {// 让 x 和 y 同时往上跳for (int i = m - 1; i >= 0; i--) { // 从大到小尝试各种2^i跳法int px = pa[x][i], py = pa[y][i];// 如果px!=py,说明可以跳if (px != py) {for (int j = 0; j < 26; ++j) {cw[j] += cnt[x][i][j] + cnt[y][i][j];} x = px;y = py;}}// 因为跳到最后,x和y都是最近公共祖先的直系节点,所以px一定会=py// 手动计算cnt[j]for (int j = 0; j < 26; ++j) {cw[j] += cnt[x][0][j] + cnt[y][0][j];}x = pa[x][0]; // x此时变成了 x 和 y 的最近公共祖先}int lca = x;pathLen -= depth[lca] * 2;int maxCw = 0;for (int i = 0; i < 26; ++i) maxCw = Math.max(maxCw, cw[i]);ans[qi] = pathLen - maxCw;}return ans;}public void dfs(int x, int fa, List<int[]>[] g, int[][] pa, int[][][] cnt, int[] depth) {pa[x][0] = fa; // 父节点for (int[] e: g[x]) { // 枚举和x相连的每一条边int y = e[0], w = e[1];if (y != fa) {cnt[y][0][w] = 1;depth[y] = depth[x] + 1;dfs(y, x, g, pa, cnt, depth);}}}
}
相关题目
1483. 树节点的第 K 个祖先
2836. 在传球游戏中最大化函数值
成绩记录
喜报!应该要升 guardian 了!
相关文章:
【力扣周赛】第 361 场周赛(⭐前缀和+哈希表 树上倍增、LCA⭐)
文章目录 竞赛链接Q1:7020. 统计对称整数的数目竞赛时代码——枚举预处理 Q2:8040. 生成特殊数字的最少操作(倒序遍历、贪心)竞赛时代码——检查0、00、25、50、75 Q3:2845. 统计趣味子数组的数目竞赛时代码——前缀和…...
解决 Android 依赖冲突
解决办法 问题原因就是,各个模块所有的依赖(递归)的 jar 包最后都会加载到安卓的项目中,你可以选择 project 形式查看 External Libraries,都在这了。所以解决问题关键就是干掉冲突,剩下一个就行了…...
前端设计模式基础笔记
前端设计模式是指在前端开发中经常使用的一些解决问题的模式或思想。它们是经过实践证明的最佳实践,可以帮助我们更好地组织和管理我们的代码。 一、单例模式(Singleton Pattern) 单例模式是一种创建型模式,它保证一个类只有一个…...
Python项目开发:Flask基于Python的天气数据可视化平台
目录 步骤一:数据获取 步骤二:设置Flask应用程序 步骤三:处理用户输入和数据可视化 步骤四:渲染HTML模板 总结 在这个数字化时代,数据可视化已经成为我们理解和解释信息的重要手段。在这个项目中,我们…...
Dell 服务器常见报错信息汇总
Dell 服务器常见报错汇总 如果有别的报错信息欢迎补充...
算法通关村-----贪心面试大热门之区间问题
判断区间是否重叠 问题描述 给定一个会议时间安排数组intervals,每个会议时间都包括开始时间和结束时间,intervals[i] [starti,endi],请你判断一个人是否能够参加这里面的全部会议。详见leetcode252 问题分析 先将会议安排数组按照开始时间排序&…...
OAK相机:自动或手动设置相机参数
OAK相机:自动或手动设置相机参数 硬件软件 硬件 使用硬件如下: 4✖️ov9782相机OAK-FFC-4P驱动板 硬件接线参考博主的一篇博客:OAK相机:多相机硬件同步拍摄 软件 博主使用的是Ubuntu18.04系统,首先配置所需的pytho…...
百家宴焕新上市,持续深耕100-300元价位段
执笔 | 尼 奥 编辑 | 古利特 4月8日,长江酒道曾在《百家宴谋划“晋级”之路,多措并举切分宴席市场“蛋糕”》一文中提到:“百家宴主力新品即将登场,市场政策灵活焕新。” 如今,百家宴新品及市场新政,正…...
Linux Debian12使用git将本地项目上传到码云(gitee)远程仓库
一、注册码云gitee账号 这个可以参考其他教程,本文不做介绍。 gitee官网:https://gitee.com/ 二、Linux Debian12安装git 如果Linux系统没有安装git,可以使用下面命令安装git sudo apt install git 三、gitee新建仓库 我这只做测试&…...
电子烟行业常用的英文表达
1. 电子烟的各种表达 a) 电子烟 i. Electronic-cigarette, ii. Electronic smoke, iii. electronic cigarettes iv. Electric cigarette, v. E-Cigarettes vi. e-cigarette, vii. e-Cig viii. E cigar,e-cigar 电子烟雪茄 2. 电子烟特指词汇及衍生 a) VAPE i. Vapo…...
【SpringMvc 丨跨域】
Spring MVC 支持跨域处理(CORS)。 CORS 简介处理CORS 过滤器CrossOrigin注解java配置xml配置 主页传送门:📀 传送 简介 跨域是指在浏览器的同源策略下,不能执行其他网站的脚本。它是由浏览器的安全限制造成的…...
【C语言】【strlen函数的使用与模拟实现】
1.strlen函数的使用和模拟实现 1.1使用: size_t strlen(const char* str)返回类型为无符号整型,参数是字符指针 计算的是字符串中到“\0"之前的字符个数 1.2模拟实现: 方法一:计数器式遍历 #include<stdio.h> #in…...
类和对象【基础概念】
全文目录 类的定义定义方式 类的访问限定符封装(面向对象的三大特性之一) 类对象模型类对象的存储方式类对象的大小计算 this指针this指针的特性**this指针可以为空吗?** 类的定义 在C中,C语言中的结构体struct中除了定义变量外还…...
如何测试生成式人工智能(AIGC)
简介:在人工智能日趋普及的今天,生成式人工智能(AIGC)已经成为不可忽视的一个分支。从自动化生成新闻、编写代码到图像和音频生成,AIGC几乎无处不在。但如何确保这些生成的内容达到预期标准、安全可靠,同时…...
机器学习算法详解3:逻辑回归
机器学习算法详解3:逻辑回归 前言 本系列主要对机器学习上算法的原理进行解读,给大家分享一下我的观点和总结。 本篇前言 本篇对逻辑回归的算法原理进行解读。 目录结构 文章目录 机器学习算法详解3:逻辑回归1. 引子2. sigmoid函数3. 原…...
linux命令集合
cd:切换文件路径 pwd:显示当前所处的路径 mkdir:创建目录比如mkdir test touch:创建一个空文件touch test.txt in:用于指定文件夹在另一个位置建立同步的链接in -s /lib/test1 /user/lj 在user目录下建立指向/lib/test1 目录的lj文件 cat:cat file(查看文件内…...
实现卓越供应链:RFID技术的革命性应用
在现代制造业中,供应链和物流的高效运作至关重要,它不仅影响着生产效率,还直接关系到企业的竞争力和客户满意度。为了应对这些挑战,越来越多的企业开始关注智能制造RFID智能设备,将其应用于供应链和物流管理࿰…...
从JVM角度看继承
从JVM角度看继承 最近重读了周志明老师的《深入理解JAVA虚拟机》一书,看完大有收获,但仍对继承情况下对象内存布局有所疑惑,所以查阅资料,结合本书进行分析 参考文档: 【深入理解JVM】:Java类继承关系中…...
基于Python和mysql开发的看图猜成语微信小程序(源码+数据库+程序配置说明书+程序使用说明书)
一、项目简介 本项目是一套基于Python和mysql开发的看图猜成语微信小程序,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Python学习者。 包含:项目源码、项目文档、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都…...
Unity入门教程||创建项目(上)
一、介绍 目的:通过尝试制作一款使用玩家角色把小球弹飞的简单小游戏,熟悉使用Unity进行游戏开发的基本流程。 软件环境:Unity 2017.3.0f3,Visual Studio 2013 二、创建新项目 1,启动Unity后将出现一个并列显示Pro…...
Openbmc编译
1.网址的问题解决 原文 Modifying /conf/local.conf was the only solution that worked for me. Simply add one of the two options:#check connectivity using google CONNECTIVITY_CHECK_URIS "https://www.google.com/"#skip connectivity checks CONNECTIVI…...
美国CN2服务器速度怎么样
美国服务器以免备案、大带宽、性价比高的优势,多用于企业、电商、外贸、视频等个中大型网站建设。但是,因中美服 务器接口原因,导致某些服务器的网络并不稳定,这时候就会对美国服务器产品失望,解决这种问题的方法就是选…...
K8S原理架构与实战教程
文章目录 一、背景1.1 物理机时代、虚拟机时代、容器化时代1.2 容器编排的需要 二、K8S架构2.2 Worker节点 三、核心概念3.1 Pod3.2 Deployment3.3 Service3.4 Volume3.5 Namespace 四、K8S安装五、kubectl常用命令六、K8S实战6.1 水平扩容6.2 自动装箱6.2.1 节点污点6.2.2 Pod…...
基于C#的图书管理系统数据库设计报告
第一章 问题描述 1.1 图书管理系统简介 本系统利用.NET处理数据库的功能,实现对图书馆信息的管理。主要功能为管理有关读者、出版社、书籍、借阅和管理者的信息等。 本系统的结构分为读者信息管理模块、出版社信息管理模块、书籍信息管理模块、借阅信息管理模块、…...
【Express.js】pm2进程管理
pm2进程管理 本节我们将介绍如何使用 pm2 运行和监管我们的 express 项目 准备工作 一个 express 项目全局安装 pm2 npm install -g pm2pm2使用介绍 启动应用 你可以用纯命令去运行一个node项目,假设原本运行项目使用 node src/index.js可以跑起来一个项目&am…...
Nginx部署前后端分离项目(Linux)
Nginx代理前端页面、后端接口 一、前端打包二、后端打包三、Linux部署Nginx启动、暂停、重启服务器部署文件地址: 一、前端打包 npm run build二、后端打包 通过Maven 使用package打包 三、Linux部署 安装Nginx 安装环境 yum -y install gcc pcre pcre-devel z…...
Docker网络
1 简介 网络原理 下载iproute工具(linux)ip addr查看地址映射 容器内ip地址会进行映射符号。docker分配的地址。 77: eth0if78: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default link/ether 02:42:ac:11:00:…...
第15章_瑞萨MCU零基础入门系列教程之Common I2C总线模块
本教程基于韦东山百问网出的 DShanMCU-RA6M5开发板 进行编写,需要的同学可以在这里获取: https://item.taobao.com/item.htm?id728461040949 配套资料获取:https://renesas-docs.100ask.net 瑞萨MCU零基础入门系列教程汇总: ht…...
《TCP/IP网络编程》阅读笔记--多播与广播
目录 1--多播 2--多播代码实例 3--广播 4--广播代码实例 1--多播 多播方式的数据传输是基于 UDP 完成的,多播数据包的格式与 UDP 数据包相同; 多播与 UDP 的区别:UDP 数据传输以单一目标进行,多播数据同时传递到加入ÿ…...
聚观早报|华为Mate 60 Pro支持面容支付;特斯拉重回底特律车展
【聚观365】9月8日消息 华为Mate 60 Pro已支持面容支付 特斯拉将重回底特律车展 iPhone在美国有1.67亿用户 韩国半导体8月份出口85.6亿美元 比亚迪元PLUS冠军版将于9月15日上市 华为Mate 60 Pro已支持面容支付 毫无预热的华为Mate 60 Pro突然在华为商城首批开售…...
哪类型网站容易做/百度竞价排名利弊
MRAM速度快且非易失性。实时监控的传感器数据可以实时写入,无需负载均衡或ECC开销。AEC-Q1001级合格MRAM将在发动机罩下应用的扩展温度(-40℃至125℃)内保留数据20年。意外断电不会影响数据完整性。 Everspin的汽车规AEC-Q100MRAM内存可用于…...
wordpress markdown/网站推广如何引流
<identity> <dns value"localhost" /> </identity>...
thinkphp网站优化/搜搜
XXL-JOB 任务调度平台实践一、调度中心(服务端)1、从gitbub 获取项目源码:[https://github.com/xuxueli/xxl-job](https://github.com/xuxueli/xxl-job)2、从源码中得到SQL脚本创建和初始化数据库3、Maven 编译打包 xxl-job-admin 并部署为调度中心4、启动运行 xxl-…...
免费学编程国内网站/360优化大师历史版本
资源调度是Spark中比较重要的内容,对调度的相关原理以及策略的了解对集群的运行以及优化都会有很大的帮助,资源调度的方式有多种,Local,Standlone,Yarn,Mesos等,本文只针对Standlone的方式做简介 几个重要的概念 开始文章之前,再…...
创造与魔法官方网站-做自己喜欢的事/北京网
目录 文档用途 详细信息 文档用途 本文介绍向PostgreSQL中加载数据的几种方法。 详细信息 1.服务器端 1.1 COPY/COPY FROM PROGRAM COPY用于在PostgreSQL表和标准文件系统文件之间移动数据。COPY TO把一个表的内容复制到一个文件,而COPY FROM则从一个文件复…...
响应式网站开发教程/百度快速排名软件
1、什么是内存模型Java平台自动集成了线程以及多处理器技术,这种集成程度比Java以前诞生的计算机语言要厉害很多。Java针对多种异构平台的独立性,使得多线程技术也具有了开拓性的一面。了解线程和进程看这里:线程和进程有什么区别我们有时候在…...