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

第 385 场 LeetCode 周赛题解

A 统计前后缀下标对 I

在这里插入图片描述
在这里插入图片描述

模拟

class Solution {
public:int countPrefixSuffixPairs(vector<string> &words) {int n = words.size();int res = 0;for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++)if (words[i].size() <= words[j].size()) {int li = words[i].size(), lj = words[j].size();if (words[i] == words[j].substr(0, li) && words[i] == words[j].substr(lj - li, li))res++;}return res;}
};

B 最长公共前缀的长度

在这里插入图片描述
在这里插入图片描述

字典树:先将 a r r 1 arr1 arr1 中元素加入字典树,然后遍历 a r r 2 arr2 arr2 中元素,在字典树上查询最长的匹配的前缀

class Solution {
public:int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2) {trie tree;for (auto x: arr1)tree.insert(x);int res = 0;for (auto x: arr2)res = max(res, tree.query(x));return res;}class trie {//字典树public:vector<trie *> next;trie() {next = vector<trie *>(10);}void insert(int x) {string s = to_string(x);trie *cur = this;for (auto c: s) {if (!cur->next[c - '0'])cur->next[c - '0'] = new trie();cur = cur->next[c - '0'];}}int query(int x) {string s = to_string(x);trie *cur = this;int res = 0;for (auto c: s)if (cur->next[c - '0']) {res++;cur = cur->next[c - '0'];} elsebreak;return res;}};
};

C 出现频率最高的素数

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

枚举:枚举并计数各个单元格向各方向能生成的大于10的素数

class Solution {
public:int mostFrequentPrime(vector<vector<int>> &mat) {int m = mat.size(), n = mat[0].size();int dr[8] = {1, 0, -1, 0, 1, 1, -1, -1};int dc[8] = {0, 1, 0, -1, 1, -1, 1, -1};unordered_map<int, int> cnt;for (int r = 0; r < m; r++)for (int c = 0; c < n; c++) {for (int k = 0; k < 8; k++) {int cur = mat[r][c];for (int nr = r + dr[k], nc = c + dc[k];; nr += dr[k], nc += dc[k]) {if (nr < 0 || nr >= m || nc < 0 || nc >= n)break;cur = cur * 10 + mat[nr][nc];if (isprime(cur))cnt[cur]++;}}}int mx = 0, res = -1;for (auto &[vi, ci]: cnt)if (ci > mx || ci == mx && vi > res) {res = vi;mx = ci;}return res;}bool isprime(int x) {for (int i = 2; i * i <= x; i++)if (x % i == 0)return false;return true;}
};

D 统计前后缀下标对 II

在这里插入图片描述
在这里插入图片描述

哈希 + 字符串哈希:遍历 w o r d [ i ] word[i] word[i] ,枚举 w o r d [ i ] word[i] word[i] 的前缀,若其长为 l l l 的前缀和长为 l l l 的后缀相同,则答案增加 w o r d [ 0 , i − 1 ] word[0,i-1] word[0,i1] w o r d [ i ] word[i] word[i] 长为 l l l 的前缀的出现次数

class Solution {
public:long long countPrefixSuffixPairs(vector<string> &words) {int n = words.size();srand(time(0));int e = 2333 + rand() % 10, mod = 1e9 + rand() % 10;unordered_map<int, int> cnt;//记录字符串(通过哈希值表示)的出现次数long long res = 0;for (int i = 0; i < n; i++) {shash hi(words[i], e, mod);int m = words[i].size();for (int l = 1; l <= m; l++) {if (auto pre = hi(0, l - 1);pre == hi(m - l, m - 1) && cnt.count(pre))res += cnt[pre];}cnt[hi(0, m - 1)]++;}return res;}class shash {//字符串哈希模板public:using ll = long long;vector<ll> pres;vector<ll> epow;ll e, p;shash(string &s, ll e, ll p) {int n = s.size();this->e = e;this->p = p;pres = vector<ll>(n + 1);epow = vector<ll>(n + 1);epow[0] = 1;for (int i = 0; i < n; i++) {pres[i + 1] = (pres[i] * e + s[i]) % p;epow[i + 1] = (epow[i] * e) % p;}}ll operator()(int l, int r) {ll res = (pres[r + 1] - pres[l] * epow[r - l + 1] % p) % p;return (res + p) % p;}};
};

相关文章:

第 385 场 LeetCode 周赛题解

A 统计前后缀下标对 I 模拟 class Solution { public:int countPrefixSuffixPairs(vector<string> &words) {int n words.size();int res 0;for (int i 0; i < n; i)for (int j i 1; j < n; j)if (words[i].size() < words[j].size()) {int li words[…...

什么是RabbitMQ?

一、引言 RabbitMQ是一个开源的消息代理软件&#xff0c;用于在分布式系统中传递消息。它实现了高级消息队列协议&#xff08;AMQP&#xff09;&#xff0c;提供了一种可靠的、强大的、灵活的消息传递机制&#xff0c;使得不同应用程序或组件之间可以轻松地进行通信。 二、概念…...

JWT登录验证前后端设计与实现笔记

设计内容 前端 配置全局前置路由守卫axios拦截器登录页面和主页 后端 JWT的封装登录接口中间件放行mysql数据库的连接 详细设计 路由设计 配置全局前置守卫&#xff0c;如果访问的是登录页面则放行&#xff0c;不是则进入判断是否有token&#xff0c;没有则拦截回到登录…...

自定义类型详解 ----结构体,位段,枚举,联合

目录 结构体 1.不完全声明 2.结构体的自引用 3.定义与初始化 4.结构体内存对齐与结构体类型的大小 结构体嵌套问题 位段 1.什么是位段&#xff1f; 2.位段的内存分配 枚举 1.枚举类型的定义 2.枚举的优点 联合&#xff08;共同体&#xff09; 1.联合体类型的声明以…...

VueCLI核心知识综合案例TodoList

目录 1 拿到一个功能模块首先需要拆分组件&#xff1a; 2 使用组件实现静态页面的效果 3 分析数据保存在哪个组件 4 实现添加数据 5 实现复选框勾选 6 实现数据的删除 7 实现底部组件中数据的统计 8 实现勾选全部的小复选框来实现大复选框的勾选 9 实现勾选大复选框来…...

关于cuda路径问题

问题&#xff1a;Could not load dynamic library ‘libcudart.so.11.0’ 原因&#xff1a;调用系统环境下的cuda但系统环境没有装cuda 解决&#xff1a; 1.在系统环境装cuda&#xff0c;但如果每权限就不好操作&#xff1b; 2.用虚拟环境装好的cuda路径丢给环境变量 暂时性&am…...

六、Spring/Spring Boot整合ActiveMQ

Spring/Spring Boot整合ActiveMQ 一、Spring整合ActiveMQ1.pom.xml2.Queue - 队列2.1 applicationContext.xml2.2 生产者2.3 消费者 3.Topic - 主题3.1 applicationContext.xml3.2 生产者3.3 消费者 4.消费者 - 监听器4.1 编写监听器类4.2 配置监听器4.3 生产者消费者一体 二、…...

树莓派4B(Raspberry Pi 4B)使用docker搭建springBoot/springCloud服务

树莓派4B&#xff08;Raspberry Pi 4B&#xff09;使用docker搭建springBoot/springCloud服务 前提&#xff1a;本文基于Ubuntu&#xff0c;Java8&#xff0c;SpringBoot 2.6.13讲解 准备工作 准备SpringBoot/SpringCloud项目jar包 用 maven 打包springBoot/springCloud项目&…...

数据库设计、JDBC、数据库连接池

数据库设计 数据库设计概念 数据库设计就是根据业务 系统的具体需求&#xff0c;结合我们所选用的DBMS,为这个业务系统构造出最优的数据存储模型。建立数据库中的表结构以及表与表之间的关联关系的过程。有哪些表?表里有哪些字段?表和表之间有什么关系? 数据库设计的步骤…...

SpringBoot实现OneDrive文件上传

SpringBoot实现OneDrive文件上传 源码 OneDriveUpload: SpringBoot实现OneDrive文件上传 获取accessToken步骤 参考文档&#xff1a;针对 OneDrive API 的 Microsoft 帐户授权 - OneDrive dev center | Microsoft Learn 1.访问Azure创建应用Microsoft Azure&#xff0c;使…...

C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现

介绍完了list类的相关内容后&#xff1a;C初阶&#xff1a;适合新手的手撕list&#xff08;模拟实现list&#xff09; 接下来进入新的篇章&#xff0c;stack和queue的介绍以及模拟&#xff1a; 文章目录 1.stack的初步介绍2.stack的使用3.queue的初步介绍4.queue的使用5.容器适…...

GRUB and the Boot Process on UEFI-based x86 Systems

background info : BIOS and UEFI-CSDN博客 The UEFI-based platform reads the partition table on the system storage and mounts the EFI System Partition (ESP), a VFAT partition labeled with a particular globally unique identifier (GUID). The ESP contains EFI a…...

2.C语言——输入输出

1.字符输入输出函数 1.输入:getchar() 字面意思&#xff0c;接收单个字符&#xff0c;使用方法 char a; a getchar();实际上效果等同于char a; scanf("%c",&a);2.输出:putchar() 2.格式化输入输出函数 1.输入:scanf() 格式&#xff1a; scanf(“格式控制…...

MySQL篇之SQL优化

一、表的设计优化 表的设计优化&#xff08;参考阿里开发手册《嵩山版》&#xff09;&#xff1a; 1. 比如设置合适的数值&#xff08;tinyint int bigint&#xff09;&#xff0c;要根据实际情况选择。 2. 比如设置合适的字符串类型&#xff08;char和varchar&#xff09…...

QGis —— 1、Windows10下载安装QGis及插件

QGis官网 QGIS&#xff08;自由开源的地理信息系统&#xff09;是一个专业的GIS应用程序&#xff0c;它建立在免费和开源软件&#xff08;FOSS&#xff09;之上&#xff0c;并为此而自豪。QGIS 是一个方便使用的开源地理信息系统 (GIS)&#xff0c;根据 GNU 通用公共许可授权。…...

【打工日常】使用docker部署Dashdot工具箱

一、Dashdot介绍 dashdot是一个简洁清晰的服务器数据仪表板&#xff0c;基于React实现 &#xff0c;主要是显示操作系统、进程、存储、内存、网络这五个的数据。 二、本次实践介绍 1. 本次实践简介 本次实践部署环境为个人测试环境 2. 本地环境规划 本次实践环境规划&#xf…...

使用client-only 解决组件不兼容SSR问题

目录 前言 一、解决方案 1.基于Nuxt 框架的SSR应用 2.基于vue2框架的应用 3.基于vue3框架的应用 二、总结 往期回顾 前言 最近在我的单页面SSR应用上开发JSON编辑器功能&#xff0c;在引入组件后直接客户端跳转OK&#xff0c;但是在直接加载服务端渲染的时候一直报这…...

基于Java SSM框架实现网上报名系统项目【项目源码+论文说明】

基于java的SSM框架实现网上报名系统演示 摘要 随着互联网时代的到来&#xff0c;同时计算机网络技术高速发展&#xff0c;网络管理运用也变得越来越广泛。因此&#xff0c;建立一个B/S结构的网上报名系统&#xff0c;会使网上报名系统工作系统化、规范化&#xff0c;也会提高网…...

7.1 Qt 中输入行与按钮

目录 前言&#xff1a; 技能&#xff1a; 内容&#xff1a; 参考&#xff1a; 前言&#xff1a; line edit 与pushbotton的一点联动 当输入行有内容时&#xff0c;按钮才能使用&#xff0c;并能读出输入行的内容 技能&#xff1a; pushButton->setEnabled(false) 按钮不…...

云计算基础-网络虚拟化

虚拟交换机 什么是虚拟交换机 虚拟交换机是一种运行在虚拟化环境中的网络设备&#xff0c;其运行在宿主机的内存中&#xff0c;通过软件方式在宿主机内部实现了部分物理交换机的功能&#xff0c;如 VLAN 划分、流量控制、QoS 支持和安全功能等网络管理特性 虚拟交换机在云平…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...