当前位置: 首页 > 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…...

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

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

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...