最新华为OD机试真题-字符串分割(100分)

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

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

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> 字符串分割(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

字符串分割

问题描述

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

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

输入格式

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

输出格式

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

样例输入

XXYYXY

样例输出

2

数据范围

题解

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

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

时间复杂度 ，空间复杂度 。

参考代码

• 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);
    }
}

• Cpp

#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;
}