P2562 [AHOI2002] Kitty猫基因编码
P1498P2562 [AHOI2002] Kitty猫基因编码
#include <iostream>
using namespace std;
#include <cmath>
#include <vector>
#include <string>
string encode(string str){if(str.find("0") == string::npos) return "B";if(str.find("1") == string::npos) return "A";int half = str.size()/2;return "C" + encode(str.substr(0,half)) + encode(str.substr(half));
}
int main(){string s;cin>>s;cout<< encode(s)<<endl;}
你完全理解正确!这段代码采用的是 直接返回值的方式,而不是对原先字符串进行修改,主要原因有以下几点:
1. 避免复杂性:处理重复元素
如果直接对原始字符串进行修改,当字符串中存在多个相同的 0
或 1
时,就需要对整个字符串的每个字符进行跟踪和修改。例如:
- 如果遇到全为
0
的字符串(如000
),我们需要将它整体替换为一个A
。 - 直接修改原字符串会导致以下问题:
- 需要移除多余字符: 例如,原来的
000
需要被替换为单个A
,那么我们需要移除其余的两个0
。 - 调整字符串结构: 修改会导致字符串长度缩短,后续的递归和分割操作需要动态调整。
- 状态管理复杂: 在原字符串上操作,可能需要额外的标记或数组来管理哪些字符已经被处理,增加了逻辑复杂性。
- 需要移除多余字符: 例如,原来的
因此,采用 直接返回值 的方式,可以避免这些问题,不需要对原字符串进行任何修改,所有逻辑都在返回值中完成。
2. 返回值递归的自然适配
采用递归返回值的方式非常符合分治问题的特点:
- 每个子问题的结果独立于其他子问题,直接通过返回值组合即可。
- 父问题只需要知道子问题的结果,而不需要直接修改父问题的原始数据。
对于这道题:
- 如果字符串全是
0
,直接返回"A"
,无需修改原字符串。 - 如果字符串全是
1
,直接返回"B"
。 - 如果既包含
0
又包含1
,分为两部分递归计算,并将子结果通过返回值合并为C + left + right
。
这种模式避免了原字符串的复杂修改,递归组合也非常简洁自然。
3. 原字符串的不可变性
递归过程中,字符串的不可变性是一个很大的优势:
- 每次递归分割出新的子串(如
substr
),这些子串和原字符串没有耦合关系。 - 这保证了递归调用之间不会互相干扰,逻辑清晰且容易调试。
- 如果直接修改原字符串,需要小心管理修改后的状态,防止对后续的递归产生副作用。
4. 避免修改的复杂示例
如果采用修改原字符串的方式,代码会变得更复杂。例如:
void encode_inplace(string &s, int start, int end) {// 判断当前范围是否全是 0 或全是 1bool all_zero = true, all_one = true;for (int i = start; i < end; ++i) {if (s[i] == '1') all_zero = false;if (s[i] == '0') all_one = false;}// 修改原字符串内容if (all_zero) {s[start] = 'A';s.erase(start + 1, end - start - 1); // 移除多余字符return;}if (all_one) {s[start] = 'B';s.erase(start + 1, end - start - 1); // 移除多余字符return;}// 递归处理左右两部分int mid = (start + end) / 2;encode_inplace(s, start, mid);encode_inplace(s, mid, end);// 合并结果s[start] = 'C';s.erase(start + 1, mid - start - 1); // 左部分清理s.erase(start + 1 + (mid - start - 1), end - mid - 1); // 右部分清理
}
这种方式复杂性较高:
- 需要手动移除字符串的多余部分。
- 需要实时维护字符串的长度和递归分割点。
- 字符串的状态管理复杂,容易出错。
相比之下,直接返回结果的方式简洁且高效。
5. 返回值方式的简化性
采用返回值的方式,逻辑更加清晰:
- 每次递归只需关注当前子字符串的结果,不用关心如何修改或清理原字符串。
- 递归的返回值天然地形成了合并的链式逻辑,例如:
这种组合方式非常直观,直接体现了分治思想。return "C" + encode(left) + encode(right);
总结
采用直接返回值的方式而非修改原字符串的原因是:
- 避免处理重复字符的复杂性: 直接返回
"A"
或"B"
表示的结果,省去了移除多余字符的麻烦。 - 自然适配递归逻辑: 返回值可以直接用来组合子结果,无需修改字符串。
- 保证字符串不可变性: 避免因修改原字符串而引入的状态管理复杂性。
- 更简洁清晰: 返回值递归更贴合分治思想,代码简洁且易于维护。
这种设计方式很好地平衡了简洁性与效率,尤其适用于这种递归分治的场景!
相关文章:
P2562 [AHOI2002] Kitty猫基因编码
P1498P2562 [AHOI2002] Kitty猫基因编码 #include <iostream> using namespace std; #include <cmath> #include <vector> #include <string> string encode(string str){if(str.find("0") string::npos) return "B";if(str.fin…...
HarmonyOS(65) ArkUI FrameNode详解
Node 1、Node简介2、FrameNode2.1、创建和删除节点2.2、对FrameNode的增删改2.3 FramNode的查询功能3、demo源码4、总结5、参考资料1、Node简介 在HarmonyOS(63) ArkUI 自定义占位组件NodeContainer介绍了自定义节点复用的原理(阅读本本篇博文之前,建议先读读这个),在Node…...
40分钟学 Go 语言高并发:负载均衡与服务治理
负载均衡与服务治理 一、知识要点总览 模块核心内容技术实现难度负载策略轮询、权重、最小连接数自定义负载均衡器中服务降级服务降级、熔断降级、限流降级Hystrix模式高熔断机制熔断器状态机、失败计数、自动恢复Circuit Breaker高限流设计令牌桶、滑动窗口、计数器Rate Lim…...
Python 从入门到实战45(Pandas数据操作)
我们的目标是:通过这一套资料学习下来,可以熟练掌握python基础,然后结合经典实例、实践相结合,使我们完全掌握python,并做到独立完成项目开发的能力。 上篇文章我们学习了pandas数据读写的相关基础知识。今天学习一下…...
node js 历史版本下载
此为node历史版本下载地址 https://nodejs.org/dist/https://nodejs.org/dist/...
无代码探索AI大模型:腾讯云函数计算的卓越实践
在数字化转型的浪潮中,人工智能(AI)技术已经成为企业提升竞争力的关键。然而,对于许多业务人员来说,技术门槛高、开发周期长等问题限制了他们快速探索和应用AI大模型的能力。同时,对于缺乏GPU资源的开发者来…...
网页数据抓取:融合BeautifulSoup和Scrapy的高级爬虫技术
网页数据抓取:融合BeautifulSoup和Scrapy的高级爬虫技术 在当今的大数据时代,网络爬虫技术已经成为获取信息的重要手段之一。Python凭借其强大的库支持,成为了进行网页数据抓取的首选语言。在众多的爬虫库中,BeautifulSoup和Scra…...
vivado中,generate output product 和Create HDL wrapper的作用
generate output product 以zynq的ip核举例,没有generate output product之前,在ip source 什么也看不到。 但是同样的一个ip核,generate output product之后,会生成综合,布线和仿真文件,约束文件等等。 …...
欧盟R156法规注意事项及实例展示
欧盟 R156 法规即《关于批准车辆的软件升级和软件升级管理体系统一规定的法规》,其注意事项及实例如下: 注意事项: 软件升级管理体系方面: 体系建立与维持:汽车制造商和供应商必须建立完善的软件升级管理体系ÿ…...
HTML语义化的案例分析
HTML语义化的案例分析:对比实际网站中语义化与非语义化标签的差异 在现代Web开发中,HTML语义化被广泛认为是提升网页结构和可访问性的重要做法。HTML语义化不仅仅是为了让代码更清晰,更是为了增强搜索引擎优化(SEO)&a…...
使用 pyperclip 进行跨平台剪贴板操作
简介:pyperclip 是一个轻量级的 Python 库,支持在不同操作系统(Windows、macOS、Linux)中进行剪贴板的复制和粘贴。这个库的设计简单易用,非常适合需要频繁进行文本复制粘贴操作的场景。 历史攻略: 使用f…...
微信小程序报错:http://159.75.169.224:7300不在以下 request 合法域名列表中,请参考文档
要解决此问题,需打开微信小程序开发者工具进行设置,打开详情-本地设置重新运行,该报错就没有啦...
Java:181 基于springboot的考编论坛管理系统
作者主页:舒克日记 简介:Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 本系统一共管理员,用户角色。 主要功能:收货地址管理、经验交流平台管理、公告信息管理、跳蚤市场管理、商品留言管理、商品订…...
通义千问sft-甄嬛对话
流程步骤 https://www.datawhale.cn/activity/110/21/76?rankingPage1 按照上面的流程,准备好数据之后就可以直接对7b的模型进行指令微调了,整个流程不是很复杂,操作起来比较方便。但是发布服务等了较长时间,以为出了bug 结果展…...
如何配置Jackson以忽略Java类中为null或空(empty)的字段
Jackson库提供了JsonInclude注解和ObjectMapper配置选项,可以用来控制是否在JSON输出中包含null或空值的字段。 默认情况下,Jackson会包含所有字段,不论其值为何。 本教程将展示如何使用Include.NON_NULL来忽略null值字段,以及使…...
设置笔记本同时连接内外网
原理:通过笔记本和手机相连,实现双网卡功能能。笔记本连接内网wifi、同时手机端开启usb网络共享,笔记本就有了两个网,然配置那个访问外网,那个访问内网。 1.笔记本wifi连接内网wifi 2.手机端共享网络。 手机打开 -【…...
让文章更具说服力:如何巧妙运用逻辑
在写作的过程中,不论是创作小说、撰写学术论文,还是撰写营销文案,逻辑的运用都至关重要。一个没有逻辑支撑的文章,很容易让读者产生困惑、迷失方向,甚至失去阅读兴趣。因此,如何巧妙地运用逻辑,…...
阿里云云服务器Docker-Execrise
申请云服务器 阿里云每个人可以免费申请三个月的使用的服务器可以用作学习使用建议申请规格2核4g的,2g的有点捉襟见肘了选择服务器建议alibaba-linux服务器,就是linux;选择windows可能由于2核4g的限制,docker不匹配系统起码我就是…...
解决 MySQL 启动失败与大小写问题,重置数据库
技术文档:解决 MySQL 启动失败与大小写问题,重置数据库 1. 问题背景 在使用 MySQL 时,可能遇到以下问题: MySQL 启动失败,日志显示 “permission denied” 或 “Can’t create directory” 错误。MySQL 在修改配置文…...
启智畅想集装箱箱号识别算法,2台相机即可实现较高识别率
启智畅想集装箱箱号识别算法,在货车通道中使用时,一般配备2台相机即可。启智畅想集装箱箱号识别算法,在货车通道中使用时,一般配备2台相机即可实现对集装箱箱号的精准捕捉与识别。这两台相机分别安装在货车通道的后侧和随意侧面&a…...
【C++】指针与智慧的邂逅:C++内存管理的诗意
文章目录 RAII 智能指针auto_ptrunique_ptr shared_ptr模拟实现定制删除器循环引用 和 weak_ptr RAII RAII(Resource Acquisition Is Initialization)是一种广泛应用于 C 等编程语言中的编程范式,它的核心思想是:资源的获取和释放…...
python中的高阶函数
1、什么是高阶函数? 高阶函数是指将函数作为参数传入。就是高阶函数 2、高阶函数有哪些? map 映射函数 >>> print(list(map(lambda x:x*x,range(1,11)))) [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] >>> print(list(map(lambda x:st…...
spark关联hive 报 Filesystem Close 错误
请看如下问题: 假如我想将一个sql语句插入hive表中时,比如 insert into table tmp.app_user_active_range partition (dt2022-11-04) 报如下错误: 我的环境是pyspark,pyspark中操作hive,使用datagrip关联spark,在da…...
MySQL主从同步详解
文章目录 MySQL主从同步概述MySQL主从同步原理MySQL主从同步结构模式MySQL主从同步搭建搭建步骤一主一从实验环境master主机slave1主机验证主从同步 一主多从master主机slave2主机验证主从同步 MySQL主从同步复制模式 读写分离技术MaxScale简介部署MaxScale服务器授权用户maste…...
Python 单元测试基础脚本
单元测试的概念: 单元测试是针对程序中最小可测试单元进行检查和验证的过程。在Python中,通常一个函数或方法就是一个测试单元。 unittest框架: Python自带了一个名为unittest的单元测试框架,它受JUnit启发,为开发者提…...
鸿蒙开发-在ArkTS中实现socket功能
基本概念 在 ArkTS 中实现 Socket 功能主要涉及到网络通信中的套接字(Socket)编程。Socket 是一种用于在不同设备(如客户端和服务器)之间进行双向通信的接口,它允许应用程序发送和接收数据。在网络编程中,有两种主要的 Socket 类型:基于 TCP…...
【设计模式系列】策略模式(二十四)
一、什么是策略模式 策略模式(Strategy Pattern)是软件设计模式中的一种行为型模式。它定义了一系列算法,并将每一个算法封装起来,使它们可以互换使用,算法的变化不会影响使用算法的用户。策略模式让算法的变化独立于…...
D92【python 接口自动化学习】- pytest基础用法
day92 pytest的skip和skipif用法 学习日期:20241208 学习目标:pytest基础用法 -- pytest的skip和skipif用法 学习笔记: 测试用例跳过 skip和skipif用法,测试用例跳过 pytest.mark.skip 跳过标记的用例 pytest.mark.skipif(1 …...
spring中的@Bean和@Component有什么区别?
定义和作用范围 Bean: 是一个方法级别的注解。它主要用于在Java配置类(使用Configuration注解的类)中定义一个Bean。这个方法返回的对象会被Spring容器管理。例如,假设我们有一个配置类AppConfig: import org.sprin…...
docker入门
安装 官方下载 系统:CentOS 7.9 配置docker yum源。 sudo yum install -y yum-utils sudo yum-config-manager \ --add-repo \ http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo启动docker 关机后下次开机又得执行 sudo systemctl start dock…...
HDR视频技术之六:色调映射
图像显示技术的最终目的就是使得显示的图像效果尽量接近人们在自然界中观察到的对应的场景。 HDR 图像与视频有着更高的亮度、更深的位深、更广的色域,因此它无法在常见的普通显示器上显示。 入门级的显示器与播放设备(例如普通人家使用的电视࿰…...
MySQL高可用之MHA
华子目录 MHA概述为什么要用MHA什么是MHAMHA的组成MHA的特点故障切换备选主库的算法 MHA工作原理MHA环境搭建环境准备开始部署MHAMHA软件使用介绍配置MHA的管理环境创建MHA管理的模板文件 测试 模拟故障MySQL-master切换手动切换(在master存活状态下切换)…...
区块链——基本概念、技术原理
一、区块链基本概念 (一)区块链定义 区块链(Blockchain)是指通过去中心化和去信任的方式集体维护一个可靠数据库的技术方案。通俗一点说,区块链技术就指一种全民参与记账的方式,是一种防篡改、共享的、可…...
docker 部署共享文档ZFile
1、拉取ZFile镜像 docker pull crpi-k5k93ldwfc7o75ip.cn-hangzhou.personal.cr.aliyuncs.com/tirling-pdf/zfile:latest 2、创建文件夹和进入文件夹 mkdir zfile && cd zfile 3、创建docker-compose.yml配置文件。 vim docker-compose.yml version: 3.3 service…...
C# 自定义组件实现表格的多层表头功能
在 WinForms 中,想要实现多层表头功能时,DataGridView 本身并不支持该功能,而且又不希望使用第三方控件,因此选择通过自定义组件来实现这一需求。 首先,展示一下程序实现的效果: 接下来,创建一…...
给Squid代理添加HTTP basic认证
HTTP basic认证是一种简单的认证机制,要求用户在请求资源前提供有效的用户名和密码。 实例: 给Squid代理添加HTTP basic认证 要求: 只允许用户名为peter,密码为123的请求通过认证, 其他请求返回407(Proxy认证失败) 步骤 1 使用htpasswd工具,生成用户…...
使用伪装IP地址和MAC地址进行Nmap扫描
使用伪装IP地址和MAC地址进行Nmap扫描 在某些网络设置中,攻击者可以使用伪装的IP地址甚至伪装的MAC地址进行系统扫描。这种扫描方式只有在可以保证捕获响应的情况下才有意义。如果从某个随机的网络尝试使用伪装的IP地址进行扫描,很可能无法接收到任何响…...
Oceanbase离线集群部署
准备工作 两台服务器 服务器的配置参照官网要求来 服务器名配置服务器IPoceanbase116g8h192.168.10.239oceanbase216g8h192.168.10.239 这里选oceanbase1作为 obd机器 oceanbase安装包 选择社区版本的时候自己系统的安装包 ntp时间同步rpm包 联网机器下载所需的软件包 …...
剑指Offer-1 存在重复元素
记录学习过程 题目连接 题目连接 题目描述 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。 示例一、 输入:nums [1,2,3,1] 输出:true 解释&…...
react跳转传参的方法
传参 首先下载命令行 npm react-router-dom 然后引入此代码 前面跳转的是页面 后面传的是你需要传的参数接参 引入此方法 useLocation():这是 react-router-dom 提供的一个钩子,用于获取当前路由的位置对象location.state:这是从其他页面传…...
【Java若依框架】RuoYi-Vue的前端和后端配置步骤和启动步骤
🎙告诉你:Java是世界上最美好的语言 💎比较擅长的领域:前端开发 是的,我需要您的: 🧡点赞❤️关注💙收藏💛 是我持续下去的动力! 目录 一. 作者有话说 …...
CSS学习记录04
CSS边框 CSS border 属性指定元素边框的样式、宽度和颜色。border-style 属性指定要显示的边框类型。dotted - 定义点线边框dashed - 定义虚线边框solid - 定义实线边框double - 定义双边框groove - 定义3D坡口边框,效果取决于border-color值ridge - 定义3D脊线边框…...
Kafka怎么发送JAVA对象并在消费者端解析出JAVA对象--示例
1、在pom.xml中加入依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-stream-kafka</artifactId><version>3.1.6</version></dependency> 2、配置application.yml 加入Kafk…...
vue3【实战】图表【组件封装】Chart ( 原生 ECharts ,支持自适配屏幕缩放,动态响应图表配置修改)
效果预览 技术方案 vue3 ( vite | TS | AutoImport ) Element Plus UnoCSS ECharts 技术要点 ECharts 实例的类型 let myChart: echarts.ECharts | null null默认生成随机 id id: {type: String,default: () > Math.random().toString(36).substring(2, 8)},深度监听图…...
Oracle系统性能监控工具oswatcher演示
1、关于 OSW OSWatcher 的使用符合 Oracle 的标准许可条款,并且不需要额外的许可即可使用!!!! OSWatcher (oswbb) 是一种 UNIX shell 脚本的集合,主要用于收集和归档操作系统和网络的度量,以便…...
Unix、GNU、BSD 风格中 ps 参数的区别
注:本文为“不同风格中 ps 命令参数的区别”相关文章合辑。 未去重。 BSD 风格和 UNIX 风格中 ps 参数的区别 作者:Daniel Stori 译者:LCTT Name1e5s | 2017-06-17 10:53 One Last Question ps aux 以及 ps -elf 都是查看进程的方式&…...
Jenkins环境一站式教程:从安装到配置,打造高效CI/CD流水线环境-Ubuntu 22.04.5 环境离线安装配置 Jenkins 2.479.1
文章目录 Jenkins环境一站式教程:从安装到配置,打造高效CI/CD流水线环境-Ubuntu 22.04.5 环境离线安装配置 Jenkins 2.479.1一、环境准备1.1 机器规划1.2 环境配置1.2.1 设置主机名1.2.2 停止和禁用防火墙1.2.3 更新系统 二、安装配置Jenkins2.1 安装JDK…...
百度文心一言全解析
一、技术基础 模型架构 多层神经网络构建:深度神经网络结构,包含多个隐藏层,有效处理复杂语言信息。注意力机制运用:精准聚焦文本关键部分,理解语义关联与重要性分布。多头注意力并行:多维度分析文本&#…...
在python中使用布尔逻辑
布尔是python中常见类型。它的值只能是两项内容之一:true或false. 编写"if"语句 若要在python中表达条件逻辑,可以使用if语句。——编写If语句离不开逻辑运算符:等于、不等于、小于、大于或等于、大于和大于或等于。 在python中…...
【Web】AlpacaHack Round 7 (Web) 题解
Treasure Hunt flag在md5值拼接flagtxt的文件里,如 d/4/1/d/8/c/d/9/8/f/0/0/b/2/0/4/e/9/8/0/0/9/9/8/e/c/f/8/4/2/7/e/f/l/a/g/t/x/t 访问已经存在的目录状态码是301 访问不存在的目录状态码是404 基于此差异可以写爆破脚本 这段waf可以用url编码绕过 做个lab …...