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

蓝桥杯第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;
}

  • 首先,代码声明了一些变量:

    • in 和 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%样例,大多数同学都用的该方法&#xff0c;就不过多赘述 #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&#xff1a;从零开始的力扣刷题生活 力扣题1&#xff1a;557. 反转字符串中的单词 III 解题思想&#xff1a;先读取单词&#xff0c;然后将单词进行翻转即可 class Solution(object):def reverseWords(self, s):""":type s…...

【软件测试】盘一盘工作中遇到的 Redis 异常测试

在测试工作中&#xff0c;涉及到与 redis 交互的场景变的越来越多了。关于redis本身就不作赘述了&#xff0c;网上随便搜&#xff0c;本人也做过一些整理。 今天只来复盘一下&#xff0c;在测试过程中与 redis 的二三事儿。其中提到的案例是经过抽象化的&#xff0c;用作辅助说…...

14.Oracle中RegExp_Like 正则表达式基本用法

--基本用法&#xff0c;是否包含某字符串 like %36% select * from k_micfo where regexp_like(loginid,36);if regexp_like(str,^[0-9\.]$) --只包含数字0-9&#xff0c;,小数点.--oracle判断字段是否是纯数字 (四种写法结果一样&#xff09; select * from k_micfo where r…...

Docker Swarm总结+Jenkins安装配置与集成(5/5)

博主介绍&#xff1a;Java领域优质创作者,博客之星城市赛道TOP20、专注于前端流行技术框架、Java后端技术领域、项目实战运维以及GIS地理信息领域。 &#x1f345;文末获取源码下载地址&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3fb;…...

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实现文件压缩打包&#xff0c;简单实例代码如下&#xff1a; import zipfilewith zipfile.ZipFile("archive.zip",w) as zipf:zipf.write("config.ini")zipf.write("test.py") 其中的模式 w表示如果没有该文件则创建该文件…...

如何创建百科?建立百科词条的意义何在?九问百科营销

在营销工作实践中&#xff0c;小马识途营销顾问经常接到关于百科营销的咨询&#xff0c;现整理了最受关注的九个问题分享给热爱营销工作的小伙伴。 一、什么是百科营销&#xff1f; 百科营销是借助百科知识传播&#xff0c;可以将企业、品牌、人物所拥有的对用户有价值的信息&a…...

Django如何设置时区为北京时间?

Django默认使用的是UTC时间&#xff0c;北京时间比UTC早8个小时&#xff0c;即如果UTC是凌晨两点&#xff0c;那么北京时间是早上八点。 Django中把setting.py中的语句&#xff1a; TIME_ZONE UTC修改为&#xff1a; TIME_ZONE Asia/Shanghai就把时区改为了北京时间。 这…...

Basemap地图绘制_Python数据分析与可视化

Basemap地图绘制 安装和使用地图投影地图背景在地图上画数据 Basemap是Matplotlib的一个子包&#xff0c;负责地图绘制。在数据可视化过程中&#xff0c;我们常需要将数据在地图上画出来。 比如说我们在地图上画出城市人口&#xff0c;飞机航线&#xff0c;军事基地&#xff0c…...

C#编程题分享(5)

判断质数问题 输⼊⼀个正整数&#xff0c;判断该数是否是质数。如果为质数输出 yes&#xff0c;如果不是输出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等格式的视频资源&#xff0c;而没有像上图这样的海报资源&#xff0c;那要怎样实现海报墙呢&#xff1f; 按照以前的方法&#xff0c;是可以通过The Movie Database的API Key来搜刮电影海报信息&#xff0c;但是现在这个方法不行了 现在介绍…...

【MODBUS】Modbus协议入门简介

Modbus&#xff08;Modicon Communication Protocol&#xff09;是一种用于工业自动化领域的通信协议&#xff0c;最初由Modicon&#xff08;现在是施耐德电气的一部分&#xff09;开发。Modbus协议被广泛应用于连接不同厂商的工业设备&#xff0c;实现设备之间的通信和数据交换…...

ORA-00257: archiver error. Connect internal only, until freed……

今天给客户测 试问题&#xff0c;让客户把数据发过来了。解压缩后一看&#xff0c;他们还是用的oracle 815版本的(他们exp导出时&#xff0c;带了导出日志&#xff0c;从导出日志中看出来是oracle 815版本的)&#xff0c;不过没有关系&#xff0c;低版本的exp是可以用高版本的i…...

继承 和 多肽(超重点 ! ! !)

[本节目标] 1.继承 2.组合 3.多肽 1.继承 1.1 为什么要继承 Java中使用类对现实世界中实体来进行描述&#xff0c;类经过实例化之后的产物对象&#xff0c;则可以用来表示现实中的实体&#xff0c;但是现实世界错综复杂&#xff0c;事物之间可能会存在一些关联&#xff0…...

H265、VP9、AV1视频编码器性能对比

1、背景介绍 目前在视频编解码器中,H264 已经成为绝对的主流,被大部分设备、浏览器所支持。虽然有更先进的编码器推出,但是受限于推广速度和设备支持成本,一直未能成为主流。 今年公司的目标是持续降本增效,现在将”屠刀“指向了视频业务的存储成本。视频文件存储主要两…...

C语言-结构体

---------------------------- ------------------ 岁月漫长心怀热爱&#xff0c;携手共赴星辰大海 --------今天来到我们自定义类型 -----结构体的讲解 目录 结构体的类型声明和初始化 结构体的类型声明 结构体成员的直接访问 结构体成员的间接访问 嵌套结构体进行访问 使用…...

C#拼夕夕自动化登录,电商网页自动化操作。WebView2

单纯靠WebView2是没办法通过JS实现自动登录操作的&#xff0c;包括浏览器插件&#xff0c;都不行&#xff0c;因为大公司对反爬机制控制的还是挺严格。 下面是实现效果&#xff0c;私信我&#xff0c;咨询解决方案。 20231202_153912 C#有偿Q群&#xff1a;927860652博客仅为…...

【Spring Boot 源码学习】BootstrapRegistryInitializer 详解

Spring Boot 源码学习系列 BootstrapRegistryInitializer 详解 引言往期内容主要内容1. 初识 BootstrapRegistryInitializer2. 加载 BootstrapRegistryInitializer3. BootstrapRegistryInitializer 的初始化 总结 引言 书接前文《初识 SpringApplication》&#xff0c;我们从 …...

预览功能实现

需求&#xff1a;将后端返回来的文字或者图片和视频展示在页面上。 <!-- 预览 --><el-dialog title"预览" :visible.sync"dialogPreviewVisible" width"50%" append-to-body :close-on-click-modal"false" close"Previe…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考

目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候&#xff0c;显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...

Linux入门(十五)安装java安装tomcat安装dotnet安装mysql

安装java yum install java-17-openjdk-devel查找安装地址 update-alternatives --config java设置环境变量 vi /etc/profile #在文档后面追加 JAVA_HOME"通过查找安装地址命令显示的路径" #注意一定要加$PATH不然路径就只剩下新加的路径了&#xff0c;系统很多命…...