2025.08.25 PDD笔试第四题
题干和例子相互冲突。
题干:
题意给定长度为n的01串,定义一次操作为, 将整个字符串按顺序分为两部分, 将两部分各自翻转后再按原顺序拼接。提问,进行任意次的操作后,可以得到的最长的连续的01交替的子串有多长。例:原01串为 01001,可以先将原串分为 010 和 01 两部分, 分别翻转得到 010 和 10 ,按原顺序拼接后得到 01010. 此时最长的连续交替子串为 01010,长度为5.
有公众号提供正解是拆分没有意义,因为两部分都要翻转。
是这种解法和题干给的例子相悖,样例都过不去吧。
有没有100%通过的大佬提供一下正解?
PS:笔试的时候右下角小窗反映了这个问题,工作人员让我“独立思考”,乐。
题干:
题意给定长度为n的01串,定义一次操作为, 将整个字符串按顺序分为两部分, 将两部分各自翻转后再按原顺序拼接。提问,进行任意次的操作后,可以得到的最长的连续的01交替的子串有多长。例:原01串为 01001,可以先将原串分为 010 和 01 两部分, 分别翻转得到 010 和 10 ,按原顺序拼接后得到 01010. 此时最长的连续交替子串为 01010,长度为5.
有公众号提供正解是拆分没有意义,因为两部分都要翻转。
是这种解法和题干给的例子相悖,样例都过不去吧。
有没有100%通过的大佬提供一下正解?
PS:笔试的时候右下角小窗反映了这个问题,工作人员让我“独立思考”,乐。
全部评论
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 读取字符串的长度
String s = sc.next(); // 读取字符串
s += s; // 将字符串自身拼接,模拟环形序列
int ans = 1; // 用于记录最长的连续不同字符子序列的长度
int cur = 1; // 当前连续不同字符子序列的长度
// 遍历拼接后的字符串,寻找最长的连续不同字符子序列
for (int i = 1; i < 2 * n; i++) {
if (s.charAt(i) != s.charAt(i - 1)) { // 当前字符与前一个字符不同
cur++;
ans = Math.max(ans, cur); // 更新最大长度
} else {
cur = 1; // 如果字符相同,重新开始计数
}
}
// 最终结果应该是 ans 与 n 的最小值,避免环形序列的重复计数
System.out.println(Math.min(ans, n));
sc.close();
}
假设在某个位置上拆分,左边的反转右边的反转,再拼在一起,本质上就相当于这个字符串在逆时针旋转。例如01001,拆成010 01,反转后 01010,实际上就是原字符串从第三个字符开始逆时针遍历一遍
哪个公众号,数据范围多少呀
相关推荐
receive177...:性压抑了
点赞 评论 收藏
分享
05-29 13:37
北京科技大学 算法工程师 认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的
开发你这个也没有项目啊
点赞 评论 收藏
分享