6-周赛332总结
6-周赛332总结
过了Q1和Q2,Q2知道用二分但是边界处理的不是很好,迷迷糊糊过的(手动再移动了下返回值…)
Q3知道将子字符串的值取出来,将最短位置放在哈希表中,然后异或在哈希表中找值。但是我这个猪头脑袋直接将值用Integer.parseInt(s)取值,然后右移取余,移了大半天,很蠢就是了…然后就没有时间做第四题了
继续努力继续努力
下文为自己的题解总结,参考其他题解写成,取其精华,做以笔记,如有描述不清楚或者错误麻烦指正,不胜感激,不喜勿喷!
找出数组的串联值【LC2562】
给你一个下标从 0 开始的整数数组
nums。现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。
- 例如,
15和49的串联是1549。
nums的 串联值 最初等于0。执行下述操作直到nums变为空:
- 如果
nums中存在不止一个数字,分别选中nums中的第一个元素和最后一个元素,将二者串联得到的值加到nums的 串联值 上,然后从nums中删除第一个和最后一个元素。- 如果仅存在一个元素,则将该元素的值加到
nums的串联值上,然后删除这个元素。返回执行完所有操作后
nums的串联值。
-
思路:使用双指针匹配数组中的元素,并将元素进行串联,累加至结果中,直至数组中没有元素剩余
- 如果前后指针指向同个元素,直接将值累加至结果
- 如果前后指针指向两个元素nums1,nums2nums1,nums2nums1,nums2,那么串联值为num1∗nums2的位数+nums2num1*nums2的位数+nums2num1∗nums2的位数+nums2
-
实现
class Solution {public long findTheArrayConcVal(int[] nums) {int l = 0, r = nums.length - 1;long res = 0L;while (l <= r){if (l == r){res += nums[l];break;}else{int n = getN(nums[r]);res += Math.pow(10, n) * nums[l] + nums[r];l++;r--;}}return res;}public int getN(int num){int n = 0;while (num != 0){num /= 10;n++;}return n;} }- 复杂度
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(1)O(1)O(1)
- 复杂度
统计公平数对的数目【LC2563】
给你一个下标从 0 开始、长度为
n的整数数组nums,和两个整数lower和upper,返回 公平数对的数目 。如果
(i, j)数对满足以下情况,则认为它是一个 公平数对 :
0 <= i < j < n,且lower <= nums[i] + nums[j] <= upper
-
思路:二分查找
将数组按顺序排序后,枚举每一个
nums[i],那么在nums[0,i)nums[0,i)nums[0,i)范围内,使用二分查找另一个数小于lower−nums[i]lower-nums[i]lower−nums[i]或者小于等于upper−nums[i]upper-nums[i]upper−nums[i]的个数,记为left和right,那么符合条件的公平数对为right−leftright-leftright−left- 可以转换为使用二分查找另一个数大于等于lower−nums[i]lower-nums[i]lower−nums[i]或者大于upper−nums[i]upper-nums[i]upper−nums[i]的第一个数的下标
- 可以转换为使用二分查找另一个数大于等于lower−nums[i]lower-nums[i]lower−nums[i]或者大于等于upper−nums[i]+1upper-nums[i]+1upper−nums[i]+1的第一个数的下标
-
实现
注意:二分查找指定范围内第一个大于等于target的数的下标,左闭右闭
class Solution {public long countFairPairs(int[] nums, int lower, int upper) {long res = 0L;Arrays.sort(nums);int n = nums.length;for (int i = 1; i < n; i++){int left = binarySearch(nums, lower - nums[i], i - 1);// 第一个大于等于 lower - nums[i] 的下标int right = binarySearch(nums, upper - nums[i] + 1, i - 1);// 第一个大于等于high nums[i]的下标[0, i - 1] res += right - left;}return res; }// 返回第一个大于等于target的下标public int binarySearch(int[] nums, int target, int r){int l = 0;// 左闭右闭while (l <= r){int mid = (l + r) >>> 1;if (nums[mid] < target){l = mid + 1;}else{r = mid - 1;}}return l;} }- 复杂度
- 时间复杂度:O(nlogn)O(nlogn)O(nlogn)
- 空间复杂度:O(1)O(1)O(1)
- 复杂度
子字符串异或查询【LC2564】
给你一个 二进制字符串
s和一个整数数组queries,其中queries[i] = [firsti, secondi]。对于第
i个查询,找到s的 最短子字符串 ,它对应的 十进制值val与firsti按位异或 得到secondi,换言之,val ^ firsti == secondi。第
i个查询的答案是子字符串[lefti, righti]的两个端点(下标从 0 开始),如果不存在这样的子字符串,则答案为[-1, -1]。如果有多个答案,请你选择lefti最小的一个。请你返回一个数组
ans,其中ans[i] = [lefti, righti]是第i个查询的答案。子字符串 是一个字符串中一段连续非空的字符序列。
-
思路:
- 首先进行预处理,将二进制字符串所有子字符串对应的十进制整数值存储在哈希表中,哈希表记录该值对应的最短子字符串的起始位置和终止位置
- 然后遍历循环数组查找结果:根据异或性质,当哈希表中存在值为
val = firsti ^ secondi时,对于第iii个查询可以找到答案,答案即为哈希表的key值
-
实现
注意:由于 数值大小109<23010^9<2^{30}109<230,因此,我们可以只需要计算 s 中所有长度不超过 30的子字符串即可
class Solution {public int[][] substringXorQueries(String s, int[][] queries) {char[] chars = s.toCharArray();int n = s.length();int m = queries.length;int[][] res = new int[m][2];Map<Integer, int[]> map = new HashMap<>();for (int i = 0; i < m; i++){Arrays.fill(res[i], -1);} for (int l = 0; l < n; l++){int num = 0;for (int r = l; r < Math.min(l + 30, n); r++){num = (num << 1) + chars[r] - '0';if (!map.containsKey(num) || map.get(num)[1] - map.get(num)[0] > r - l){map.put(num, new int[]{l, r});}}}for (int i = 0; i < m; i++){int target = (queries[i][0] ^ queries[i][1]);if (map.containsKey(target)){res[i] = map.get(target);}}return res;} }- 复杂度
- 时间复杂度:O(nlogU+q)O(nlogU + q)O(nlogU+q),其中 nnn 为
s的长度,U=max(queries)U=max(queries)U=max(queries),qqq 为queries的长度。 - 空间复杂度:O(nlogU)O(nlogU)O(nlogU)
- 时间复杂度:O(nlogU+q)O(nlogU + q)O(nlogU+q),其中 nnn 为
- 复杂度
最少得分子序列【LC2565】
给你两个字符串
s和t。你可以从字符串
t中删除任意数目的字符。如果没有从字符串
t中删除字符,那么得分为0,否则:
- 令
left为删除字符中的最小下标。- 令
right为删除字符中的最大下标。字符串的得分为
right - left + 1。请你返回使
t成为s子序列的最小得分。一个字符串的 子序列 是从原字符串中删除一些字符后(也可以一个也不删除),剩余字符不改变顺序得到的字符串。(比方说
"ace"是"***a\***b***c\***d***e\***"的子序列,但是"aec"不是)。
-
思路:
- 删除[left,right][left,right][left,right]之间的字符,不会影响最终结果,因为删除不影响得分,并且更能让剩余字符成为
s的子串,因此可以视为删除子串【没想到】 - 删除后,
t中剩余的字符为t[:,left),(right,:][:,left),(right,:][:,left),(right,:]。假设s的一个前缀字符串s[0,i]s[0,i]s[0,i]可以匹配该前缀字符串,s的一个后缀字符串s[i+1,:]s[i+1,:]s[i+1,:]可以匹配该后缀字符串,那么表明t中剩余的字符是s的子序列,得分为right−left+1right-left+1right−left+1 - 反而言之,我们可以枚举iii,求得s[0,i]s[0,i]s[0,i]能够匹配
t的最长前缀字符串的结束位置下标l,以及s[i+1,:]s[i+1,:]s[i+1,:]能够匹配t的最长后缀字符串的开始位置r,那么此时需要删除的位置即为[l+1,r−1][l+1,r-1][l+1,r−1],得分为r−l−1r-l-1r−l−1,取最小值返回节课
- 删除[left,right][left,right][left,right]之间的字符,不会影响最终结果,因为删除不影响得分,并且更能让剩余字符成为
-
实现
- 预处理后缀数组
suff[i]:s的一个后缀字符串s[i,:]s[i,:]s[i,:]可以匹配t的最长后缀字符串的开始位置 - 预处理前缀数组
pre[i+1]:s的一个前缀字符串s[0,i]s[0,i]s[0,i]可以匹配t的最长前缀字符串的结束位置
class Solution {public int minimumScore(String s, String t) {int n = s.length(), m = t.length();int[] pre = new int[n + 1];int[] suf = new int[n + 1];suf[n] = m;for (int i = n - 1, j = m - 1; i >= 0; i--){if (j >= 0 && s.charAt(i) == t.charAt(j)) j--;suf[i] = j + 1;}int res = suf[0];if (suf[0] == 0) return res;// t是s的子序列pre[0] = -1;for (int i = 1; i <= n; i++){if (s.charAt(i - 1) == t.charAt(pre[i - 1] + 1)){pre[i] = pre[i - 1] + 1;}else{pre[i] = pre[i - 1];}res = Math.min(res, suf[i] - pre[i] - 1);}return res;} }- 复杂度
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(n)O(n)O(n)
- 预处理后缀数组
-
优化:前缀数组可以用变量代替
class Solution {public int minimumScore(String s, String t) {int n = s.length(), m = t.length();int[] suf = new int[n + 1];suf[n] = m;for (int i = n - 1, j = m - 1; i >= 0; i--){if (j >= 0 && s.charAt(i) == t.charAt(j)) j--;suf[i] = j + 1;}int res = suf[0];if (suf[0] == 0) return res;// t是s的子序列int pre = -1;for (int i = 1; i <= n; i++){if (s.charAt(i - 1) == t.charAt(pre + 1)){pre += + 1;}res = Math.min(res, suf[i] - pre - 1);}return res;} }
相关文章:
6-周赛332总结
6-周赛332总结 过了Q1和Q2,Q2知道用二分但是边界处理的不是很好,迷迷糊糊过的(手动再移动了下返回值…) Q3知道将子字符串的值取出来,将最短位置放在哈希表中,然后异或在哈希表中找值。但是我这个猪头脑袋…...
嵌入式Qt 开发一个音乐播放器
上篇文章:RK3568源码编译与交叉编译环境搭建,进行了OK3568开发板软件开发环境搭建,通过编译RK3568的源码,可以得到Qt开发的交叉编译相关工具。 本篇,就来在搭建好的软件开发中,进行Qt软件的开发测试。由于…...
2023秋招万得集团AI算法岗面经分享
本专栏分享 计算机小伙伴秋招春招找工作的面试经验和面试的详情知识点 专栏首页:秋招算法类面经分享 主要分享计算机算法类在面试互联网公司时候一些真实的经验 2022年 11.22下午AI算法岗面试 (1)一面35min 1、自我介绍 2、科研:长文本MRC...
RoI Transformer论文翻译详解
Learning RoI Transformer for Oriented Object Detection in Aerial Images 0.摘要 航空图像中的目标检测是计算机视觉中一个活跃而又具有挑战性的任务,因为它具有鸟瞰视角、高度复杂的背景和变化的物体外观。特别是在航空图像中检测密集的目标时,基于…...
Prometheus 自动发现监控AWS EC2实例
本文章简述对接自动发现AWS云EC2实例 前提环境: PromethuesGrafanaAWS IAM权限 涉及参考文档: AWS EC2Grafana 通用监控模板 一、IAM 用户创建 1、创建Prometheus 策略 策略规则: {"Version": "2012-10-17",&quo…...
从recat源码角度看setState流程
setState setState() 将对组件 state 的更改排入队列批量推迟更新,并通知 React 需要使用更新后的 state 重新渲染此组件及其子组件。其实setState实际上不是异步,只是代码执行顺序不同,有了异步的感觉。 使用方法 setState(stateChange | u…...
【Java|golang】1234. 替换子串得到平衡字符串---双指针
有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符,且长度为 n 的字符串。 假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。 给你一个这样的字符串 s,请通过「替换一个子串」的方式,…...
自监督表征学习方法——BYOL(Bootstrap Your Own Latent)
自监督表征学习方法——BYOL(Bootstrap Your Own Latent) 参考文献:《Bootstrap Your Own Latent A New Approach to Self-Supervised Learning》 1.前言背景 学习良好的图像表示是计算机视觉中的一个关键挑战,因为它允许对下游任务进行有效的训练。许…...
均衡负载集群(LBC)-1
均衡负载集群(LBC) 客户–>通过Internet—>负载调度器—>n台真实服务器 负载调度器: 软件:LVS;Nginx;Haproxy硬件:F5; LVS架构: 使用到C/S(B/S…...
WebSocket
关于WebSocket: WebSocket 协议在2008年诞生,2011年成为国际标准。现在所有浏览器都已经支持了。 WebSocket 的最大特点就是,服务器可以主动向客户端推送信息,客户端也可以主动向服务器发送信息,是真正的双向平等对话…...
GA-PEG-GA,Glutaric Acid-PEG-Glutaric Acid,戊二酸-聚乙二醇-戊二酸供应
英文名称:Glutaric Acid-PEG-Glutaric Acid,GA-PEG-GA 中文名称:戊二酸-聚乙二醇-戊二酸 GA-PEG-GA是一种线性双功能PEG羧酸试剂。PEG和羧基COOH之间存在C4酯键。PEG羧酸可用于与氨基反应,与NHS和DCC、EDC等肽偶联试剂反应。 P…...
使用sqlmap + burpsuite sql工具注入拿flag
使用sqlmap burpsuite sql工具注入拿flag 记录一下自己重新开始学习web安全之路③。 目标网站:http://mashang.eicp.vip:1651/7WOY59OBj74nTwKzs3aftsh1MDELK2cG/ 首先判断网站是否存在SQL注入漏洞 1.找交互点 发现只有url这一个交互点,搜索框和登录…...
替代AG9300|替代NCS8823|CS5260 Type-C转VGA视频转换方案
替代AG9300|替代NCS8823|CS5260 Type-C转VGA视频转换方案 CS5260是一款是一款实现USB TYPE-C到VGA视频转换的单片机解决方案转换器。CS5260支持USB Type-C显示端口交替模式,CS5260可以将视频和音频流从USB Type-C接口传输到VGA端口。在CS5260芯片中,显示…...
乐鑫特权隔离机制的 OTA 固件升级
固件空中升级 (OTA, Over-The-Air) 是任何联网设备的重要功能之一,支持开发人员通过远程更新固件,以发布新功能或修复错误。乐鑫特权隔离框架中包含两类应用程序:受保护的应用程序 (protected_app) 和用户应用程序 (user_app) ,这…...
C++数据结构 —— 二叉搜索树
目录 1.二叉搜索树的基本概念 1.1二叉搜索树的基本特征 2.二叉搜索树的实现 2.1数据的插入(迭代实现) 2.2数据的搜索(迭代实现) 2.3中序遍历(递归实现) 2.4数据的删除(迭代实现) 2.5数据的搜索(递归实现) 2.6数据的插入(递归实现) 2.7数据的删除(递归实现) 2.8类的完…...
Maven面试题及答案
1、Maven有哪些优点和缺点 优点: 1、简化项目依赖管理 2、方便与持续集成工具(Jenkins)整合 3、有助于多模块项目开发,比如一个模块开发好后发布到仓库,依赖该模块时可以直接从远程仓库更新,不用自己手动去编译 4、有很多插件&am…...
WebRTC系列-Qos系列之接收放RTX处理
文章目录 1. RTX详解1.1 RTX包头解析1.2 RTX包中的OSN2. RTX在WebRTC中处理2.1 组包2.2 解包2.3 发送及接收处理流程2.3.1 发送流程2.3.2 rtx标记的设置流程2.3.3 解析流程2.3.4 RTX解包在上一篇 WebRTC系列-Qos系列之接收NACK文章中分析了接收到nack后解析的主要流程。在WebR…...
国内能否炒伦敦金,2023国际十大正规伦敦金交易平台排名
在目前的投资市场环境中,现货黄金是一种屡见不鲜的投资选择,它依靠国际化的投资环境,成为了世界范围内投资者的重要选择对象。进行现货黄金投资,人们除了要认识市场发展基本现状之外,更要做好基本面和技术面分析工作&a…...
react路由 - react-router-dom
react路由 现代的前端应用大多都是 SPA(单页应用程序),也就是只有一个 HTML 页面的应用程序。因为它的用户体验更好、对服务器的压力更小,所以更受欢迎。为了有效的使用单个页面来管理原来多页面的功能,前端路由应运而…...
01-RTOS
对于裸机而言,对于RTOS而言即:对于裸机,打游戏意味着不能回消息 回消息意味着不能打游戏对于RTOS 打游戏和裸机的切换只需要一个时间片节拍 1ms 从宏观来看 就是同时进行的两件事(但要在这两件事情的优先级一样的情况下࿰…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
