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

【LeetCode第 332 场周赛】

传送门

文章目录

  • 6354. 找出数组的串联值
  • 6355. 统计公平数对的数目
  • 6356. 子字符串异或查询
  • 6357. 最少得分子序列

6354. 找出数组的串联值

题目

在这里插入图片描述


思路

前后指针


代码

class Solution {
public:long long findTheArrayConcVal(vector<int>& nums) {long long res = 0;int n = nums.size();for (int i = 0, j = n - 1; i < j; i++, j--) {res += stol(to_string(nums[i]) + to_string(nums[j]));}if (n & 1) res += nums[n / 2];return res; }
};

6355. 统计公平数对的数目

题目

在这里插入图片描述


思路

lower<=nums[i]+nums[j]<=upperlower <= nums[i] + nums[j] <= upperlower<=nums[i]+nums[j]<=upper

转化:

lower−nums[i]<=nums[j]<=upper−nums[i]lower - nums[i] <= nums[j] <= upper - nums[i]lowernums[i]<=nums[j]<=uppernums[i]

倒序遍历,动态查找后缀的在区间如上范围内的值的个数。那么考虑用树状数组获取区间内值的个数。

由于范围过大,且做差会造成负数,树状数组下标从1开始。所以换用map的树状数组,平且值向右平移到正数。


代码

class Solution {
public:using ll = long long;static constexpr ll N = 2e9 + 7;class BIT {public:BIT() {}unordered_map<ll, int> tr;void add(ll x, int v = 1) { for (; x < N << 1; x += x & -x) tr[x] += v; }ll sum(ll x) { ll res = 0; for (; x; x -= x & -x) res += tr[x]; return res; }}; // 切记用 BIT tr; tr.add(); tr.sum();long long countFairPairs(vector<int>& a, int L, int R) {ll res = 0;BIT tree;for (int i = a.size() - 1; i >= 0; i--) {res += tree.sum(R - a[i] + N) - tree.sum(L - a[i] - 1 + N);tree.add(a[i] + N);}return res;}
};

6356. 子字符串异或查询

题目

在这里插入图片描述


思路

映射数值对应的最小开始下标即可,数值在1e9,并且无前导 ‘0’,所以只需要 O(30n)。


代码

class Solution {
public:vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& q) {vector<vector<int>> res;map<int, int> mp;int mn = 1e9;for (int i = 0; i < s.size(); i++) {int x = 0;for (int j = 0; j < 31 && i + j < s.size(); j++) {if (s[i + j] - '0' == 0 && x == 0) {mn = min(mn, i);break;}x = x * 2 + s[i + j] - '0';if (mp.count(x)) {mp[x] = min(mp[x], i);} else {mp[x] = i;}}}for (int i = 0; i < q.size(); i++) {int x = q[i][0] ^ q[i][1];int y = x;int cnt = 0;while (y) { cnt++; y /= 2; }vector<int> v{-1, -1};if (cnt == 0 && mn != 1e9) {v[0] = mn;v[1] = mn;}if (mp.count(x)) {v[0] = mp[x];v[1] = v[0] + cnt - 1;}res.push_back(v);}return res;}
};

6357. 最少得分子序列

题目

在这里插入图片描述


思路

维护前后缀数组,l[i],r[i]l[i],r[i]l[i],r[i]:表示字符串 sss 的前 iii 位子序列在字符串 ttt 中匹配的最长前缀。rrr 同理最长后缀。


代码

class Solution {
public:int minimumScore(string s, string t) {int n = s.size(); vector<int> l(n, 0), r(n, 0); int j = 0;for (int i = 0; i < s.size(); i++) {if (j < t.size() && s[i] == t[j]) ++j;l[i] = j;}j = t.size() - 1;for (int i = s.size() - 1; i >= 0; i--) {if (j >= 0 && s[i] == t[j]) --j;r[i] = t.size() - j - 1;}int res = 1e9; for (int i = 0; i < n - 1; i++) {int L = l[i], R = r[i + 1];if (L + R >= t.size()) return 0; // 都能匹配上,说明t本就是s的子序列res = min(res, (int)((t.size() - R - 1) - (L) + 1));}res = min(res, (int)t.size() - r[0]);res = min(res, (int)t.size() - l[n - 1]);return res;}
};

相关文章:

【LeetCode第 332 场周赛】

传送门 文章目录6354. 找出数组的串联值6355. 统计公平数对的数目6356. 子字符串异或查询6357. 最少得分子序列6354. 找出数组的串联值 题目 思路 前后指针 代码 class Solution { public:long long findTheArrayConcVal(vector<int>& nums) {long long res 0;i…...

【蓝桥杯单片机】Keil5中怎么添加STC头文件;从烧录软件中添加显示添加成功后新建工程时依旧找不到

蓝桥杯单片机的芯片型号&#xff1a;IAP15F2K61S2 添加头文件&#xff1a;STC15F2K60S2.H 【1】如何通过烧录软件添加STC头文件&#xff1a; 从ATC-ISP的Keil仿真设置中添加&#xff08;同时自动下载仿真驱动&#xff09;仔细阅读添加说明 KEIL5添加STC芯片库_Initdev的博客-…...

图解浏览器渲染页面详细过程

渲染详细过程 产生渲染任务&#xff0c;开启渲染流程 当浏览器的网络线程收到 HTML 文档后&#xff0c;会产生一个渲染任务&#xff0c;并将其传递给渲染主线程的消息队列。 在事件循环机制的作用下&#xff0c;渲染主线程取出消息队列中的渲染任务&#xff0c;开启渲染流程。…...

多线程面试题开胃菜1(5道)

一.多线程有什么用&#xff1f;1&#xff09;发挥多核CPU 的优势随着工业的进步&#xff0c;现在的笔记本、台式机乃至商用的应用服务器至少也都是双核的&#xff0c;4 核、8 核甚至 16 核的也都不少见&#xff0c;如果是单线程的程序&#xff0c;那么在双核 CPU 上就浪费了 50…...

植物育种中广义遗传力的定义

大家好&#xff0c; 我是邓飞。 今天聊一下广义遗传力的计算方法。 广义遗传力定义 广义遗传力&#xff08;H2H^2H2&#xff09;定义为归因于基因型总体遗传变异的表型变异比例。 通常他包括三个解释&#xff1a;&#xff08;详见我这篇博客的公式推导 回归系数 相关系数 遗…...

西瓜书读书笔记—绪论

文章目录机器学习典型的机器学习过程基本术语归纳偏好机器学习 机器学习&#xff1a;致力于研究如果通过计算的手段&#xff0c;利用经验来改善系统自身的性能 在计算机系统中&#xff0c;“经验” 通常以 “数据” 形式存在&#xff0c;因此&#xff0c;机器学习所研究的主要内…...

ES8——Generator函数的使用

babel工具插件下载&#xff1a;npm i --save babel-polyfill 引入&#xff1a;polyfill.js进行转码&#xff08;es8->es5&#xff09; 介绍 Generator函数用于生成迭代器 function * (){} yeild: 作用同return类似 {const obj function* () {yield "a";yield 12…...

德馨食品冲刺A股上市:计划募资9亿元,林志勇为实际控制人

近日&#xff0c;浙江德馨食品科技股份有限公司&#xff08;下称“德馨食品”或“德馨饮料”&#xff09;预披露更新招股书&#xff0c;准备在上海证券交易所主板上市。据贝多财经了解&#xff0c;德馨食品于2022年7月5日递交上市申请&#xff0c;安信证券为其保荐机构。 本次…...

湿敏电阻的原理,结构,分类与应用总结

🏡《总目录》 0,概述 湿敏电阻是指电阻值随着环境的湿度变化而变化的电阻,本文对其工作原理,结构,分类和应用场景进行总结。 1,工作原理 湿敏电阻是利用湿敏材料制成的,湿敏材料吸收空气中水分时,自身的阻值发生变化。 2,结构 如下图所示,市民电阻包括4个部分构成,…...

千锋教育嵌入式物联网教程之系统编程篇学习-03

目录 进程的终止 exit函数 _exit函数 进程退出清理 进程间的替换 进程间通信 常见通信机制 进程间通信的实质 信号 产生信号的方式 信号的默认处理方式 进程对信号的处理方式 kill函数 进程的终止 使用exit函数对进程进行终止&#xff0c;而return只是结束函数&a…...

升级到https

现在很多站长都会考虑将自己的站点从http升级到https&#xff0c;不仅是基于安全的考虑&#xff0c;有的也是因为第三方平台的限制&#xff0c;如谷歌浏览器会将http站点标记为不安全的站点&#xff0c;微信平台要求接入的微信小程序必须使用https等。 那如何将一个http站点升…...

【C语言】数据结构-二叉树

主页&#xff1a;114514的代码大冒险 qq:2188956112&#xff08;欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ &#xff09; Gitee&#xff1a;庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 引入 我们之前已经学过线性数据结构&#xff0c;今天我们将介绍非线性数据结构----树 树是一种非线性的…...

c++中std::condition_variable最全用法归纳

前言 建议阅读以下文章前需先对建立 std::thread 多线程与std::mutex 锁有一定程度的熟悉 std::thread最全用法归纳 std::mutex最全用法归纳 概括 使用 std::condition_variable 的 wait 会把目前的线程 thread 停下来并且等候事件通知&#xff0c;而在另一个线程中可以使用…...

Python数据可视化:数据关系图表可视化

目录 1、散点图 1.1、趋势显示的二维散点图 1.2、分布显示的二维散点图 1.3、散点曲线图...

Urho3D约定

Urho3D使用以下约定和原则&#xff1a; 左手坐标系。正X、Y和Z轴指向右侧、上方和前方&#xff0c;正旋转为顺时针。度用于角度。顺时针顶点定义正面。音频音量指定为0.0&#xff08;静音&#xff09;到1.0&#xff08;全音量&#xff09;路径名使用斜杠而不是反斜杠。调用操作…...

python数据结构-列表,元组

列表 列表是Python中最通用的数据类型&#xff0c;可以写成方括号之间的逗号分隔值(项目)列表。 使用列表的重要事项是&#xff0c;列表中的项目不必是相同的类型。也就是说一个列表中的项目(元素)可以是数字&#xff0c;字符串&#xff0c;数组&#xff0c;字典等甚至是列表类…...

Properties类读配置文件、修改配置文件

Properties类简介(1)Properties类是专门用于读写配置文件的集合类(2)配置文件的后缀名为.properties,内容格式为:# 可以用“#”作为注释 键值 键值**注意:**键值对不需要有空格,值不需要用引号一起来。默认类型是String。键、值不可以是null(3)Properties类的方法可查找api文档…...

图解LeetCode——剑指 Offer 24. 反转链表

一、题目 定义一个函数&#xff0c;输入一个链表的头节点&#xff0c;反转该链表并输出反转后链表的头节点。 二、示例 示例: 【输入】 1->2->3->4->5->NULL 【输出】 5->4->3->2->1->NULL 限制&#xff1a; 0 < 节点个数 < 5000 三、…...

【C语言】“指针的运算”、“指针与数组”

文章目录一、指针运算1.指针 - 整数2.指针-指针3.指针关系运算二、指针与数组三、二级指针四、指针数组完结一、指针运算 指针可以进行整数&#xff0c;指针-指针&#xff0c;还有关系运算&#xff0c;其他的运算会被编译器阻止。 1.指针 - 整数 对指针进行的时候一定要注意不…...

Linux高级命令之查找文件命令

查找文件命令学习目标能够说出查找文件使用的命令1. find命令及选项的使用命令说明find在指定目录下查找文件(包括目录)find命令选项:选项说明-name根据文件名(包括目录名)字查找find命令及选项的效果图:2. find命令结合通配符的使用通配符:是一种特殊语句&#xff0c;主要有星…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...