【2024最新华为OD-C卷试题汇总】字符串分割(100分)

【2024最新华为OD-C卷试题汇总】字符串分割(100分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

👏 感谢大家的订阅➕ 和喜欢💗

文章目录

前言
- 🎀关于华为OD
- 🧭 机试备考指南
- 🎧 字符串分割(100分)
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- ✅AC代码截图

前言

🎀关于华为OD

✨华为OD的概念
华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
⌚️华为 OD 应聘流程
- 第一步：投递简历
  - 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。
- 第二步：机试
  - 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 300 分以上，没有过半年之后才能参加下一次考试。
- 第三步：技术面
  - 2 轮技术面试。
- 第四步：HR 与主管面试
- 第五步：录用，发 offer

🧭 机试备考指南

华为OD的题库大半年跟新一次，也就是说，一旦跟新，那么本年用的题目就是从该题库种选题，大概有100～200道左右
最近考试换为C/D卷，C/D卷题库是一样的，D卷为双机位监控，某些外包公司应聘的为D卷。
为此清隆帮大家搜集并整理了C卷的题库，后续会由清隆的ACM银牌团队将题目整理后搬上OJ，支持在线评测。

🎧 字符串分割(100分)

问题描述

K小姐最近在研究字符串问题。现在，她有一个只包含大写字母 $X$ 和 $Y$ 的字符串 $S$ ，且 $S$ 中 $X$ 和 $Y$ 的数量相等。这种字符串被称为均衡串。

K小姐想知道， $S$ 最多可以被分割成多少个连续的子串，使得每个子串都是一个均衡串。

输入格式

输入一个字符串 $S$ ，字符串中只包含大写字母 $X$ 和 $Y$ ，保证 $S$ 是一个均衡串。

输出格式

输出一个整数，表示 $S$ 最多可以被分割成的均衡子串数量。

样例输入

XXYYXY

样例输出

数据范围

$\leq |S| \leq 10000$

题解

这道题可以使用贪心的思想来解决。我们可以从左到右扫描字符串，维护当前子串中 $X$ 和 $Y$ 的数量。如果在某个位置，当前子串中 $X$ 和 $Y$ 的数量相等，那么我们就找到了一个均衡子串，可以将其分割出来，然后继续扫描剩余的字符串。

具体实现时，我们可以用一个变量 $c n t$ 来表示当前子串中 $X$ 的数量减去 $Y$ 的数量。如果遇到 $X$ ，就将 $c n t$ 加 $1$ ，如果遇到 $Y$ ，就将 $c n t$ 减 $1$ 。当 $c n t$ 为 $0$ 时，说明当前子串是一个均衡串，可以将其分割出来。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。

参考代码

Python

s = input()
cnt = 0
ans = 0
for c in s:
    if c == 'X':
        cnt += 1
    else:
        cnt -= 1
    if cnt == 0:
        ans += 1
print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int cnt = 0, ans = 0;
        for (char c : s.toCharArray()) {
            if (c == 'X') {
                cnt++;
            } else {
                cnt--;
            }
            if (cnt == 0) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt = 0, ans = 0;
    for (char c : s) {
        if (c == 'X') {
            cnt++;
        } else {
            cnt--;
        }
        if (cnt == 0) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}