蓝桥杯第1037题子串分值和 C++ 字符串 逆向思维 巧解
题目

思路和解题方法
方案一——遍历+哈希表
仅能过60%样例,大多数同学都用的该方法,就不过多赘述
#include <iostream> #include <unordered_map> using namespace std; int main() {string s;cin >> s;int n = s.size();int res = n;for (int i = 0; i < n; ++i) {unordered_map<char, int> m;++m[s[i]];for (int j = i + 1; j < n; ++j) {++m[s[j]];res += m.size();}}cout << res;return 0; }
首先,代码声明了一些变量:
i、n和sum是用于迭代、记录字符串长度和计算最终结果的变量,都被初始化为 0。a是一个字符数组,用于存储输入的字符串,数组大小为 1000000。s是一个长度为 26 的整型数组,用于记录每个小写字母最后一次出现的位置。通过
cin输入字符串到数组a中,并使用strlen函数获取字符串a的长度赋值给变量n。使用
for循环遍历字符串a中的每一个字符:
- 在循环内部,根据公式
(i+1-s[a[i]-'a']) * (n-i)更新变量sum的值,其中:
i+1表示当前字符在字符串中的位置(从 1 开始计数)。s[a[i]-'a']表示当前字符最后一次出现的位置(将字母映射为数组索引)。(n-i)表示以当前字符结尾的子串的个数。- 然后,将当前字符的位置信息
i+1更新到数组s中对应字母的位置上,以便后续计算时使用。最后,通过
cout输出最终计算得到的结果sum。代码
#include <iostream> #include <stdlib.h> #include <cstring> using namespace std; int main() {long long int i, n, sum = 0; // 声明变量 i,n,sum,并初始化 sum 为 0char a[1000000]; // 声明一个字符数组 a,用于存储输入的字符串,数组大小为 1000000int s[26] = {0}; // 声明一个长度为 26 的整型数组 s,用于记录每个小写字母最后一次出现的位置cin>>a; // 输入字符串到数组 a 中n = strlen(a); // 获取字符串 a 的长度for(i = 0; i < n; i++) // 遍历字符串 a{sum += (i+1-s[a[i]-'a']) * (n-i); // 根据公式更新 sum 的值s[a[i] - 'a'] = i+1; // 更新数组 s 中对应字母的位置信息}cout<<sum<<endl; // 输出最终计算得到的结果 sumreturn 0; }
复杂度
时间复杂度:
O(n)
时间复杂度:
- 输入字符串的长度为 n,因此遍历字符串的时间复杂度为 O(n)。
- 在循环内部,执行的操作是常数时间的,不随输入规模变化。
- 因此,整个代码的时间复杂度为 O(n)。
空间复杂度
O(1)
空间复杂度:
- 使用了常数大小的辅助变量和数组,不随输入规模变化。
- 因此,代码的空间复杂度为 O(1)。
总结起来,这段代码的时间复杂度为 O(n),空间复杂度为 O(1)。
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
相关文章:
蓝桥杯第1037题子串分值和 C++ 字符串 逆向思维 巧解
题目 思路和解题方法 方案一——遍历哈希表 仅能过60%样例,大多数同学都用的该方法,就不过多赘述 #include <iostream> #include <unordered_map> using namespace std; int main() {string s;cin >> s;int n s.size();int res n;for (int i 0…...
力扣题:字符串的反转-11.23
力扣题-11.23 [力扣刷题攻略] Re:从零开始的力扣刷题生活 力扣题1:557. 反转字符串中的单词 III 解题思想:先读取单词,然后将单词进行翻转即可 class Solution(object):def reverseWords(self, s):""":type s…...
【软件测试】盘一盘工作中遇到的 Redis 异常测试
在测试工作中,涉及到与 redis 交互的场景变的越来越多了。关于redis本身就不作赘述了,网上随便搜,本人也做过一些整理。 今天只来复盘一下,在测试过程中与 redis 的二三事儿。其中提到的案例是经过抽象化的,用作辅助说…...
14.Oracle中RegExp_Like 正则表达式基本用法
--基本用法,是否包含某字符串 like %36% select * from k_micfo where regexp_like(loginid,36);if regexp_like(str,^[0-9\.]$) --只包含数字0-9,,小数点.--oracle判断字段是否是纯数字 (四种写法结果一样) select * from k_micfo where r…...
Docker Swarm总结+Jenkins安装配置与集成(5/5)
博主介绍:Java领域优质创作者,博客之星城市赛道TOP20、专注于前端流行技术框架、Java后端技术领域、项目实战运维以及GIS地理信息领域。 🍅文末获取源码下载地址🍅 👇🏻 精彩专栏推荐订阅👇🏻…...
docker安装Sentinel zipkin
文章目录 引言I Sentinel安装1.1 运行容器1.2 DOCKERFILE 参考1.3 pom 依赖1.4 .yml配置(整合springboot)II 资源保护2.1 Feign整合Sentinel2.2 CommonExceptionAdvice:限流异常处理类III zipkin引言 消息服务和请求第三方服务可不配置Sentinel。 </...
利用python实现文件压缩打包的功能
主要是利用了zipfile实现文件压缩打包,简单实例代码如下: import zipfilewith zipfile.ZipFile("archive.zip",w) as zipf:zipf.write("config.ini")zipf.write("test.py") 其中的模式 w表示如果没有该文件则创建该文件…...
如何创建百科?建立百科词条的意义何在?九问百科营销
在营销工作实践中,小马识途营销顾问经常接到关于百科营销的咨询,现整理了最受关注的九个问题分享给热爱营销工作的小伙伴。 一、什么是百科营销? 百科营销是借助百科知识传播,可以将企业、品牌、人物所拥有的对用户有价值的信息&a…...
Django如何设置时区为北京时间?
Django默认使用的是UTC时间,北京时间比UTC早8个小时,即如果UTC是凌晨两点,那么北京时间是早上八点。 Django中把setting.py中的语句: TIME_ZONE UTC修改为: TIME_ZONE Asia/Shanghai就把时区改为了北京时间。 这…...
Basemap地图绘制_Python数据分析与可视化
Basemap地图绘制 安装和使用地图投影地图背景在地图上画数据 Basemap是Matplotlib的一个子包,负责地图绘制。在数据可视化过程中,我们常需要将数据在地图上画出来。 比如说我们在地图上画出城市人口,飞机航线,军事基地,…...
C#编程题分享(5)
判断质数问题 输⼊⼀个正整数,判断该数是否是质数。如果为质数输出 yes,如果不是输出no 样例输⼊113 输出yes int n Convert.ToInt32(Console.ReadLine()); int count 0; for (int i 1; i < n 1; i) {if (n % i 0) // 判断该数能被整除{coun…...
群晖Video Station 添加海报墙-新方法
海报墙 一般我们找到的都是mp4、mkv等格式的视频资源,而没有像上图这样的海报资源,那要怎样实现海报墙呢? 按照以前的方法,是可以通过The Movie Database的API Key来搜刮电影海报信息,但是现在这个方法不行了 现在介绍…...
【MODBUS】Modbus协议入门简介
Modbus(Modicon Communication Protocol)是一种用于工业自动化领域的通信协议,最初由Modicon(现在是施耐德电气的一部分)开发。Modbus协议被广泛应用于连接不同厂商的工业设备,实现设备之间的通信和数据交换…...
ORA-00257: archiver error. Connect internal only, until freed……
今天给客户测 试问题,让客户把数据发过来了。解压缩后一看,他们还是用的oracle 815版本的(他们exp导出时,带了导出日志,从导出日志中看出来是oracle 815版本的),不过没有关系,低版本的exp是可以用高版本的i…...
继承 和 多肽(超重点 ! ! !)
[本节目标] 1.继承 2.组合 3.多肽 1.继承 1.1 为什么要继承 Java中使用类对现实世界中实体来进行描述,类经过实例化之后的产物对象,则可以用来表示现实中的实体,但是现实世界错综复杂,事物之间可能会存在一些关联࿰…...
H265、VP9、AV1视频编码器性能对比
1、背景介绍 目前在视频编解码器中,H264 已经成为绝对的主流,被大部分设备、浏览器所支持。虽然有更先进的编码器推出,但是受限于推广速度和设备支持成本,一直未能成为主流。 今年公司的目标是持续降本增效,现在将”屠刀“指向了视频业务的存储成本。视频文件存储主要两…...
C语言-结构体
---------------------------- ------------------ 岁月漫长心怀热爱,携手共赴星辰大海 --------今天来到我们自定义类型 -----结构体的讲解 目录 结构体的类型声明和初始化 结构体的类型声明 结构体成员的直接访问 结构体成员的间接访问 嵌套结构体进行访问 使用…...
C#拼夕夕自动化登录,电商网页自动化操作。WebView2
单纯靠WebView2是没办法通过JS实现自动登录操作的,包括浏览器插件,都不行,因为大公司对反爬机制控制的还是挺严格。 下面是实现效果,私信我,咨询解决方案。 20231202_153912 C#有偿Q群:927860652博客仅为…...
【Spring Boot 源码学习】BootstrapRegistryInitializer 详解
Spring Boot 源码学习系列 BootstrapRegistryInitializer 详解 引言往期内容主要内容1. 初识 BootstrapRegistryInitializer2. 加载 BootstrapRegistryInitializer3. BootstrapRegistryInitializer 的初始化 总结 引言 书接前文《初识 SpringApplication》,我们从 …...
预览功能实现
需求:将后端返回来的文字或者图片和视频展示在页面上。 <!-- 预览 --><el-dialog title"预览" :visible.sync"dialogPreviewVisible" width"50%" append-to-body :close-on-click-modal"false" close"Previe…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
