【2024年华为OD机试】(C卷,100分)- 分割均衡字符串 (Java JS PythonC/C++)

在这里插入图片描述

一、问题描述

题目描述

均衡串定义:字符串中只包含两种字符,且这两种字符的个数相同。

给定一个均衡字符串,请给出可分割成新的均衡子串的最大个数。

约定:字符串中只包含大写的 XY 两种字符。

输入描述

输入一个均衡串。

字符串的长度:[2, 10000]。
给定的字符串均为均衡字符串

输出描述

输出可分割成新的均衡子串的最大个数。

备注

分割后的子串,是原字符串的连续子串

用例

用例 1

输入:

XXYYXY

输出:

2

说明:
XXYYXY 可分割为 2 个均衡子串,分别为:XXYYXY

题目解析

本题要求分割出最多的均衡子串,含义其实是分割出来的均衡子串无法再分解。

例如,用例 “XXYYXY” 分解出来的两个子串 “XXYY” 和 “XY” 都是无法再次分解出均衡子串的。

如果我们从一个均衡串中取走一个均衡子串,则均衡串剩余部分依旧是一个均衡串,因为取走的均衡子串中 XY 的数量是相等的,因此均衡串剩余部分的 XY 数量也一定是相等的,满足均衡串要求。

因此,本题我们只需要从左往右扫描输入的均衡串每个字符即可,统计扫描过程中,X 字符和 Y 字符的数量,每当两种字符数量相等时,则说明遇到了一个不可分解的均衡子串。

详细步骤

  1. 初始化计数器

    • 使用两个计数器 countXcountY 分别记录 XY 的数量。
    • 使用一个计数器 result 记录不可分解的均衡子串的数量。
  2. 扫描字符串

    • 从左往右遍历输入的均衡串。
    • 对于每个字符,如果是 X,则 countX 加 1;如果是 Y,则 countY 加 1。
  3. 检查均衡条件

    • 每次更新计数器后,检查 countXcountY 是否相等。
    • 如果相等,则说明遇到了一个不可分解的均衡子串,result 加 1,并重置 countXcountY 为 0,继续扫描剩余部分。
  4. 输出结果

    • 遍历结束后,输出 result,即不可分解的均衡子串的数量。

在这里插入图片描述

用例解释

用例 1
  • 输入:
    • XXYYXY
  • 输出:
    • 2

解释

  • 遍历字符串 XXYYXY
    • X -> countX = 1
    • X -> countX = 2
    • Y -> countY = 1
    • Y -> countY = 2,此时 countX == countY,遇到一个均衡子串 XXYYresult = 1,重置 countX = 0countY = 0
    • X -> countX = 1
    • Y -> countY = 1,此时 countX == countY,遇到一个均衡子串 XYresult = 2,重置 countX = 0countY = 0
  • 最终结果为 2

通过上述步骤,我们可以高效地求出可分割成新的均衡子串的最大个数。这种方法的时间复杂度为 O(n),其中 n 是字符串的长度。

二、JavaScript算法源码

以下是 JavaScript 代码 的详细中文注释和逻辑讲解:


JavaScript 代码

// 引入 readline 模块,用于从控制台读取输入
const rl = require("readline").createInterface({ input: process.stdin });// 获取异步迭代器
var iter = rl[Symbol.asyncIterator]();// 定义异步函数 readline,用于读取一行输入
const readline = async () => (await iter.next()).value;// 立即执行异步函数
void (async function () {const s = await readline(); // 从控制台读取输入字符串 slet countX = 0; // 统计字符 'X' 的数量let countY = 0; // 统计字符 'Y' 的数量let ans = 0; // 记录满足条件的子串数量// 遍历字符串 s 中的每个字符for (let c of s) {if (c == "X") {countX++; // 如果字符是 'X',增加 countX} else {countY++; // 如果字符是 'Y',增加 countY}// 如果当前 'X' 和 'Y' 的数量相等,说明找到一个满足条件的子串if (countX == countY) {ans++; // 增加结果计数}}console.log(ans); // 输出结果
})();

代码逻辑讲解

1. 输入处理
  • 使用 readline 模块从控制台读取输入字符串 s
  • readline 是一个异步函数,通过 await 等待输入完成。

2. 统计字符数量
  • 定义两个变量:
    • countX:统计字符 'X' 的数量。
    • countY:统计字符 'Y' 的数量。
  • 遍历字符串 s 中的每个字符:
    • 如果字符是 'X',增加 countX
    • 如果字符是 'Y',增加 countY

3. 判断满足条件的子串
  • 在遍历过程中,每当 countXcountY 相等时:
    • 说明从字符串开头到当前位置的子串中,'X''Y' 的数量相等。
    • 增加结果计数 ans

4. 输出结果
  • 遍历结束后,输出满足条件的子串数量 ans

示例验证

示例 1:s = “XY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
  • 结果:
    • ans = 1(子串 "XY" 满足条件)。
示例 2:s = “XXYY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'X'countX = 2countY = 0
    • 字符 'Y'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 1(子串 "XXYY" 满足条件)。
示例 3:s = “XYXY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
    • 字符 'X'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 2(子串 "XY""XYXY" 满足条件)。

总结

  • 功能:统计字符串 s 中满足 'X''Y' 数量相等的子串数量。
  • 核心逻辑
    1. 遍历字符串,统计 'X''Y' 的数量。
    2. 每当 'X''Y' 的数量相等时,增加结果计数。
  • 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
  • 注意事项
    • 输入字符串只能包含 'X''Y'
    • 如果字符串为空,结果为 0

如果有其他问题,欢迎随时提问!

三、Java算法源码

以下是 Java 代码 的详细中文注释和逻辑讲解:


Java 代码

import java.util.Scanner; // 引入 Scanner 类,用于从控制台读取输入public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); // 创建 Scanner 对象,用于读取输入String s = sc.nextLine(); // 从控制台读取一行输入,存储到字符串 s 中int countX = 0; // 统计字符 'X' 的数量int countY = 0; // 统计字符 'Y' 的数量int ans = 0; // 记录满足条件的子串数量// 遍历字符串 s 中的每个字符for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == 'X') {countX++; // 如果当前字符是 'X',增加 countX} else {countY++; // 如果当前字符是 'Y',增加 countY}// 如果当前 'X' 和 'Y' 的数量相等,说明找到一个满足条件的子串if (countX == countY) {ans++; // 增加结果计数}}System.out.println(ans); // 输出结果}
}

代码逻辑讲解

1. 输入处理
  • 使用 Scanner 类从控制台读取输入字符串 s
  • sc.nextLine() 用于读取一行输入,并将其存储到字符串 s 中。

2. 统计字符数量
  • 定义两个变量:
    • countX:统计字符 'X' 的数量。
    • countY:统计字符 'Y' 的数量。
  • 遍历字符串 s 中的每个字符:
    • 使用 s.charAt(i) 获取当前字符。
    • 如果字符是 'X',增加 countX
    • 如果字符是 'Y',增加 countY

3. 判断满足条件的子串
  • 在遍历过程中,每当 countXcountY 相等时:
    • 说明从字符串开头到当前位置的子串中,'X''Y' 的数量相等。
    • 增加结果计数 ans

4. 输出结果
  • 遍历结束后,输出满足条件的子串数量 ans

示例验证

示例 1:s = “XY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
  • 结果:
    • ans = 1(子串 "XY" 满足条件)。
示例 2:s = “XXYY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'X'countX = 2countY = 0
    • 字符 'Y'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 1(子串 "XXYY" 满足条件)。
示例 3:s = “XYXY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
    • 字符 'X'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 2(子串 "XY""XYXY" 满足条件)。

总结

  • 功能:统计字符串 s 中满足 'X''Y' 数量相等的子串数量。
  • 核心逻辑
    1. 遍历字符串,统计 'X''Y' 的数量。
    2. 每当 'X''Y' 的数量相等时,增加结果计数。
  • 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
  • 注意事项
    • 输入字符串只能包含 'X''Y'
    • 如果字符串为空,结果为 0

如果有其他问题,欢迎随时提问!

四、Python算法源码

以下是 Python 代码 的详细中文注释和逻辑讲解:


Python 代码

# 输入获取
s = input()  # 从控制台读取一行输入,存储到字符串 s 中# 算法入口
def getResult():countX = 0  # 统计字符 'X' 的数量countY = 0  # 统计字符 'Y' 的数量ans = 0  # 记录满足条件的子串数量# 遍历字符串 s 中的每个字符for c in s:if c == 'X':countX += 1  # 如果当前字符是 'X',增加 countXelse:countY += 1  # 如果当前字符是 'Y',增加 countY# 如果当前 'X' 和 'Y' 的数量相等,说明找到一个满足条件的子串if countX == countY:ans += 1  # 增加结果计数return ans  # 返回满足条件的子串数量# 算法调用
print(getResult())  # 输出结果

代码逻辑讲解

1. 输入处理
  • 使用 input() 函数从控制台读取一行输入,并将其存储到字符串 s 中。

2. 统计字符数量
  • 定义两个变量:
    • countX:统计字符 'X' 的数量。
    • countY:统计字符 'Y' 的数量。
  • 遍历字符串 s 中的每个字符:
    • 如果字符是 'X',增加 countX
    • 如果字符是 'Y',增加 countY

3. 判断满足条件的子串
  • 在遍历过程中,每当 countXcountY 相等时:
    • 说明从字符串开头到当前位置的子串中,'X''Y' 的数量相等。
    • 增加结果计数 ans

4. 输出结果
  • 调用 getResult() 函数,计算满足条件的子串数量。
  • 使用 print() 函数输出结果。

示例验证

示例 1:s = “XY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
  • 结果:
    • ans = 1(子串 "XY" 满足条件)。
示例 2:s = “XXYY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'X'countX = 2countY = 0
    • 字符 'Y'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 1(子串 "XXYY" 满足条件)。
示例 3:s = “XYXY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
    • 字符 'X'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 2(子串 "XY""XYXY" 满足条件)。

总结

  • 功能:统计字符串 s 中满足 'X''Y' 数量相等的子串数量。
  • 核心逻辑
    1. 遍历字符串,统计 'X''Y' 的数量。
    2. 每当 'X''Y' 的数量相等时,增加结果计数。
  • 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
  • 注意事项
    • 输入字符串只能包含 'X''Y'
    • 如果字符串为空,结果为 0

如果有其他问题,欢迎随时提问!

五、C/C++算法源码:

以下是 C 代码 的详细中文注释和逻辑讲解:


C 代码

#include <stdio.h>  // 引入标准输入输出库int main() {char s[10001];  // 定义一个字符数组 s,用于存储输入的字符串scanf("%s", s); // 从控制台读取字符串,存储到数组 s 中int countX = 0; // 统计字符 'X' 的数量int countY = 0; // 统计字符 'Y' 的数量int ans = 0;    // 记录满足条件的子串数量int i = 0;      // 定义索引变量 i,用于遍历字符串while (s[i] != '\0') {  // 遍历字符串,直到遇到字符串结束符 '\0'if (s[i] == 'X') {countX++; // 如果当前字符是 'X',增加 countX} else {countY++; // 如果当前字符是 'Y',增加 countY}if (countX == countY) {ans++; // 如果当前 'X' 和 'Y' 的数量相等,增加结果计数}i++; // 移动到下一个字符}printf("%d\n", ans); // 输出结果return 0; // 程序正常结束
}

代码逻辑讲解

1. 输入处理
  • 定义一个字符数组 s,用于存储输入的字符串。
  • 使用 scanf("%s", s) 从控制台读取字符串,并将其存储到数组 s 中。

2. 统计字符数量
  • 定义两个变量:
    • countX:统计字符 'X' 的数量。
    • countY:统计字符 'Y' 的数量。
  • 使用 while 循环遍历字符串 s 中的每个字符:
    • 使用 s[i] 获取当前字符。
    • 如果字符是 'X',增加 countX
    • 如果字符是 'Y',增加 countY

3. 判断满足条件的子串
  • 在遍历过程中,每当 countXcountY 相等时:
    • 说明从字符串开头到当前位置的子串中,'X''Y' 的数量相等。
    • 增加结果计数 ans

4. 输出结果
  • 使用 printf("%d\n", ans) 输出满足条件的子串数量。

示例验证

示例 1:s = “XY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
  • 结果:
    • ans = 1(子串 "XY" 满足条件)。
示例 2:s = “XXYY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'X'countX = 2countY = 0
    • 字符 'Y'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 1(子串 "XXYY" 满足条件)。
示例 3:s = “XYXY”
  • 遍历过程:
    • 字符 'X'countX = 1countY = 0
    • 字符 'Y'countX = 1countY = 1
    • 字符 'X'countX = 2countY = 1
    • 字符 'Y'countX = 2countY = 2
  • 结果:
    • ans = 2(子串 "XY""XYXY" 满足条件)。

总结

  • 功能:统计字符串 s 中满足 'X''Y' 数量相等的子串数量。
  • 核心逻辑
    1. 遍历字符串,统计 'X''Y' 的数量。
    2. 每当 'X''Y' 的数量相等时,增加结果计数。
  • 适用场景:需要统计字符串中满足某种字符数量关系的子串数量。
  • 注意事项
    • 输入字符串只能包含 'X''Y'
    • 如果字符串为空,结果为 0

如果有其他问题,欢迎随时提问!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/1730.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【update 更新数据语法合集】.NET开源ORM框架 SqlSugar 系列

系列文章目录 &#x1f380;&#x1f380;&#x1f380; .NET开源 ORM 框架 SqlSugar 系列 &#x1f380;&#x1f380;&#x1f380; 文章目录 系列文章目录前言 &#x1f343;一、实体对象更新1.1 单条与批量1.2 不更新某列1.3 只更新某列1.4 NULL列不更新1.5 无主键/指定列…

项目概述、开发环境搭建(day01)

软件开发整体介绍 软件开发流程 第1阶段: 需求分析 需求规格说明书&#xff0c; 一般来说就是使用 Word 文档来描述当前项目的各个组成部分&#xff0c;如&#xff1a;系统定义、应用环境、功能规格、性能需求等&#xff0c;都会在文档中描述。产品原型&#xff0c;一般是通过…

数据仓库基础常见面试题

1.数据仓库是什么 ‌数据仓库&#xff08;Data Warehouse&#xff09;是一个面向主题的、集成的、非易失的、随时间变化的数据集合&#xff0c;用于支持企业的管理决策‌。它不同于传统的操作型数据库&#xff0c;后者主要用于处理日常业务交易和实时查询&#xff0c;而数据仓库…

shell脚本回顾1

1、shell 脚本写出检测 /tmp/size.log 文件如果存在显示它的内容&#xff0c;不存在则创建一个文件将创建时间写入。 一、 ll /tmp/size.log &>/dev/null if [ $? -eq 0 ];then cat /tmp/size.log else touch /tmp/size.log echo date > /tmp/size.log fi二、 if …

【C++】PP5015 [NOIP2018 普及组] 标题统计

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示数据规模与约定 &#x1f4af;方法分析方法1&#xff1a;我的做法实…

【C++第三方库】快速上手---轻量级数据库SQLite和单元测试工具Gtest

每日激励&#xff0c;“驾驭命运的舵是奋斗。不抱有幻想&#xff0c;不放弃一点机会&#xff0c;不停止一日努力。” 绪论​&#xff1a; 本篇文章将写道如何快速的上手Gtest和SQLite第三方库&#xff0c;这两个第三方库都是在项目编写过程中非常重要的。 —————— 话不多说…

《机器学习》——贝叶斯算法

贝叶斯简介 贝叶斯公式&#xff0c;又称贝叶斯定理、贝叶斯法则&#xff0c;最初是用来描述两个事件的条件概率间的关系的公式&#xff0c;后来被人们发现具有很深刻的实际意义和应用价值。该公式的实际内涵是&#xff0c;支持某项属性的事件发生得愈多&#xff0c;则该属性成…

优先级队列(算法十四)

简介 优先级队列其实就是堆 默认大根堆 小根堆&#xff1a;greater<T> std::priority_queue<int, std::vector<int>, std::greater<int>> pq; priority_queue 没有迭代器&#xff0c; 不能for&#xff08;auto e:pq); 不改变原来pq&#xff0c;查…

【day5】Redis持久化之AOF + Redis事务_锁机制

AOF是什么 以日志的形式来记录每个写操作(增量保存)&#xff0c;将 Redis 执行过的所有写指令记录下来(比 如 set/del 操作会记录, 读操作 get 不记录 只许追加文件但不可以改写文件 redis 启动之初会读取该文件重新构建数据 redis 重启的话就根据日志文件的内容将写指令从前到…

C#补充----反射,特性,迭代器,特殊语法,值类型运用类型。

1.反射。 《1》获取类的方式 《2》反射的应用 <1>获取类型的所有公共成员 <2>获取构造函数 <3>获取类型的 公共成员变量 <4>获取类型的 公共方法 <5>.获取类型的 属性 <6>.公共接口&#xff0c;公共枚举&#xff0c;公共事件

MyBatis——XML映射文件

在MyBatis中&#xff0c;既可以通过注解的方式配置SQL语句&#xff0c;也可以通过XML映射文件的方式配置SQL语句。对于简单的SQL语句建议直接通过注解的方式配置SQL语句&#xff1a; Delete("delete from user where id#{id}") Integer deleteById(Integer id);但是…

git使用-小白入门2

git使用-小白入门2 分支git branch——显示分支git checkout -b——创建&#xff0c;切换分支git merge——合并分支git log --graph——以图标形式查看分支 推送至远程仓库 分支 在进行多个并行作业时&#xff0c;我们会用到分支。在这类并行开发的过程中&#xff0c;往往同时…

OpenAI Whisper:语音识别技术的革新者—深入架构与参数

当下语音识别技术正以前所未有的速度发展&#xff0c;极大地推动了人机交互的便利性和效率。OpenAI的Whisper系统无疑是这一领域的佼佼者&#xff0c;它凭借其卓越的性能、广泛的适用性和创新的技术架构&#xff0c;正在重新定义语音转文本技术的规则。今天我们一起了解一下Whi…

TiDB常见操作指南:从入门到进阶

TiDB常见操作指南&#xff1a;从入门到进阶 TiDB作为一个分布式数据库&#xff0c;提供了丰富的操作接口和功能。无论是基本的数据库管理&#xff0c;还是更为复杂的分布式事务处理&#xff0c;TiDB都能灵活应对。在这篇文章中&#xff0c;我们将总结几种TiDB常见操作&#xf…

NVIDIA CUDA Linux 官方安装指南

本文翻译自&#xff1a;https://docs.nvidia.com/cuda/cuda-installation-guide-linux/index.html#post-installation-actions NVIDIA CUDALinux安装指南 CUDA工具包的Linux安装说明。 文章目录 1.导言1.1.系统要求1.2.操作系统支持政策1.3.主机编译器支持政策1.3.1.支持的C方言…

rtthread学习笔记系列(4/5/6/7/15/16)

文章目录 4. 杂项4.1 检查是否否是2的幂 5. 预编译命令void类型和rt_noreturn类型的区别 6.map文件分析7.汇编.s文件7.1 汇编指令7.1.1 BX7.1.2 LR链接寄存器7.1.4 []的作用7.1.4 简单的指令 7.2 MSR7.3 PRIMASK寄存器7.4.中断启用禁用7.3 HardFault_Handler 15 ARM指针寄存器1…

一个使用 Golang 编写的新一代网络爬虫框架,支持JS动态内容爬取

大家好&#xff0c;今天给大家分享一个由ProjectDiscovery组织开发的开源“下一代爬虫框架”Katana&#xff0c;旨在提供高效、灵活且功能丰富的网络爬取体验&#xff0c;适用于各种自动化管道和数据收集任务。 项目介绍 Katana 是 ProjectDiscovery 精心打造的命令行界面&…

【Redis】初识Redis

目录 Redis简介 Redis在内存中存储数据 Redis数据库中的应用 Redis缓存中的应用 Redis消息中间件 尾言 Redis简介 如下是Redis官网中&#xff0c;对Redis的一段描述 在这段描述中&#xff0c;我们提取如下关键要点&#xff1a; Redis主要用于在内存中存储数据Redis可…

IDEA的Git界面(ALT+9)log选项不显示问题小记

IDEA的Git界面ALT9 log选项不显示问题 当前问题idea中log界面什么都不显示其他选项界面正常通过命令查询git日志正常 预期效果解决办法1. 检查 IDEA 的 Git 设置2. 刷新 Git Log (什么都没有大概率是刷新不了)3. 检查分支和日志是否存在4. 清理 IDEA 缓存 (我用这个成功解决)✅…

赤店商城系统点餐小程序多门店分销APP共享股东h5源码saas账号独立版全插件全开源

代码介绍 后端编程语言采用&#xff1a;PHP yii2.0框架 前端代码采用&#xff1a;UNIAPP框架环境要求 推荐选择服务器配置&#xff1a;2核4G内存3M带宽 linux操作系统 控制面板&#xff1a;宝塔面板 运行环境&#xff1a;PHP7.2MYSQL5.7 赤店商城系统是一款集点餐小程序、多门…