最新华为OD机试真题-字符串环游戏(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🧷 字符串环游戏
问题描述
K小姐有一个由小写字母组成的字符串 ,她想把这个字符串首尾相连形成一个环,然后在环中找出包含偶数个
'o'
字符的最长子串的长度。你能帮助她解决这个问题吗?
输入格式
输入一个由小写字母组成的字符串 。
输出格式
输出一个整数,表示环中包含偶数个 'o'
字符的最长子串的长度。
样例输入
alolobo
样例输出
6
样例解释
在给定的样例中,最长的满足条件的子串之一是 "alolob"
,它包含 个
'o'
字符。
数据范围
题解
本题可以通过统计字符串中 'o'
字符的个数来解决。具体步骤如下:
- 统计字符串
中
'o'
字符的个数,记为。
- 如果
是偶数,那么字符串
本身就是满足条件的最长子串,直接输出字符串
的长度即可。
- 如果
是奇数,那么我们需要删除字符串
中的任意一个字符,使得删除后的字符串中
'o'
字符的个数变为偶数。此时满足条件的最长子串长度为字符串的长度减
。
因此,我们只需要判断字符串 中
'o'
字符的个数的奇偶性,然后根据奇偶性输出相应的结果即可。
时间复杂度:,其中
为字符串
的长度。 空间复杂度:
。
参考代码
- Python
def solve(s):
cnt = s.count('o')
if cnt % 2 == 0:
return len(s)
else:
retu
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
最新华为OD机试-E+D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测