【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 内存访问热度分析(100分) - 三语言AC题解(Python/Java/Cpp)

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

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

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

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

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1064

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

🧷 字符串环游戏

问题描述

K小姐有一个由小写字母组成的字符串 $s$，她想把这个字符串首尾相连形成一个环，然后在环中找出包含偶数个 'o' 字符的最长子串的长度。你能帮助她解决这个问题吗？

输入格式

输入一个由小写字母组成的字符串 $s$。

输出格式

输出一个整数，表示环中包含偶数个 'o' 字符的最长子串的长度。

样例输入

alolobo

样例输出

6

样例解释

在给定的样例中，最长的满足条件的子串之一是 "alolob"，它包含 $2$ 个 'o' 字符。

数据范围

$1\le |s|\le 5\times 10^5$

题解

本题可以通过统计字符串中 'o' 字符的个数来解决。具体步骤如下：

1. 统计字符串 $s$ 中 'o' 字符的个数，记为 $cnt$。
2. 如果 $cnt$ 是偶数，那么字符串 $s$ 本身就是满足条件的最长子串，直接输出字符串 $s$ 的长度即可。
3. 如果 $cnt$ 是奇数，那么我们需要删除字符串 $s$ 中的任意一个字符，使得删除后的字符串中 'o' 字符的个数变为偶数。此时满足条件的最长子串长度为字符串 $s$ 的长度减 $1$。

因此，我们只需要判断字符串 $s$ 中 'o' 字符的个数的奇偶性，然后根据奇偶性输出相应的结果即可。

时间复杂度：$O(n)$，其中 $n$ 为字符串 $s$ 的长度。
空间复杂度：$O(1)$。

参考代码

• Python

def solve(s):
    cnt = s.count('o')
    if cnt % 2 == 0:
        return len(s)
    else:
        return len(s) - 1

s = input().strip()
print(solve(s))

• Java

import java.util.Scanner;

public class Main {
    public static int solve(String s) {
        int cnt = 0;
        for (char c : s.toCharArray()) {
            if (c == 'o') {
                cnt++;
            }
        }
        if (cnt % 2 == 0) {
            return s.length();
        } else {
            return s.length() - 1;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        System.out.println(solve(s));
    }
}

• Cpp

#include <iostream>
#include <string>

using namespace std;

int solve(string s) {
    int cnt = 0;
    for (char c : s) {
        if (c == 'o') {
            cnt++;
        }
    }
    if (cnt % 2 == 0) {
        return s.length();
    } else {
        return s.length() - 1;
    }
}

int main() {
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}