【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题目截图
文章目录
- 📎在线评测链接
- 🍓OJ题目截图
- 🧷 字符串环游戏
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例解释
- 数据范围
- 题解
- 参考代码
🧷 字符串环游戏
问题描述
K小姐有一个由小写字母组成的字符串 s s s,她想把这个字符串首尾相连形成一个环,然后在环中找出包含偶数个 'o'
字符的最长子串的长度。你能帮助她解决这个问题吗?
输入格式
输入一个由小写字母组成的字符串 s s s。
输出格式
输出一个整数,表示环中包含偶数个 'o'
字符的最长子串的长度。
样例输入
alolobo
样例输出
6
样例解释
在给定的样例中,最长的满足条件的子串之一是 "alolob"
,它包含 2 2 2 个 'o'
字符。
数据范围
1 ≤ ∣ s ∣ ≤ 5 × 1 0 5 1 \le |s| \le 5 \times 10^5 1≤∣s∣≤5×105
题解
本题可以通过统计字符串中 'o'
字符的个数来解决。具体步骤如下:
- 统计字符串 s s s 中
'o'
字符的个数,记为 c n t cnt cnt。 - 如果 c n t cnt cnt 是偶数,那么字符串 s s s 本身就是满足条件的最长子串,直接输出字符串 s s s 的长度即可。
- 如果 c n t cnt cnt 是奇数,那么我们需要删除字符串 s s s 中的任意一个字符,使得删除后的字符串中
'o'
字符的个数变为偶数。此时满足条件的最长子串长度为字符串 s s s 的长度减 1 1 1。
因此,我们只需要判断字符串 s s s 中 'o'
字符的个数的奇偶性,然后根据奇偶性输出相应的结果即可。
时间复杂度: O ( n ) O(n) O(n),其中 n n n 为字符串 s s s 的长度。
空间复杂度: O ( 1 ) O(1) O(1)。
参考代码
- Python
def solve(s):cnt = s.count('o')if cnt % 2 == 0:return len(s)else:return len(s) - 1s = 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;
}