京东 · 双指针 · 算法编程题
京东 双指针 N ≤ 1e5 时限 1 秒 / 256 MB

题目描述

"你叉叉,唱日出,穷哈哈,唱日落.....",小哈开心地哼着小调,因此小哈是一个爱笑的人,每次笑都很有魔性,调皮地小哼记录了小哈的一次说的话,其中里面可能包含了小哈的笑声,并以为字符串来记录小哈的话。已知,小哈的笑声是字母 a 和 h 交替的序列,例如: ahahah , aha , a , h 是符合笑声的合法序列。但是, abacaba , aa 不符合笑声的合法序列。
通过小哼的记录,请你求出小哈笑声的最大长度。

输入输出

输入描述
输入的第一行给出小哈说话的长度 N 。
随后一行中输入一行长度为 N 字符串 S ——表示小哈的话。
1 ≤ N ≤ 10^5
S 仅由小写字母组成。
输出描述
输出小哈笑声的最大长度。

样例共 2 组

样例 1
输入
7
abacaba
输出
1
样例 2
输入
20
ahahahahahahahahahah
输出
20

算法解析依据充分

考点:字符串 · 双指针

数据规模 N ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:N ≤ 1e5
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:双指针

用两个指针协同移动,把两层循环的 O(n²) 优化到 O(n)。

思路框架(双指针 通法 · 非本题专属)

  1. 判断是「对撞指针」(一左一右向中间靠拢)还是「快慢指针」(同向不同速)。
  2. 确定指针移动的单调条件:什么情况下移动左指针,什么情况下移动右指针。
  3. 每一步根据当前指针位置更新答案,直到指针相遇或越界。
  4. 常配合有序性使用:无序时先排序。

实现要点:写成 while (l < r) 循环最清晰,切记每轮至少有一个指针移动,否则死循环。

复杂度:时间 O(n)(排序则 O(n log n)) | 空间 O(1)

该范式的通法易错点

  • 指针移动条件写反,漏解或死循环。
  • 两指针同时移动导致跳过合法解。

对照本题

  • 数据规模 N ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。

样例

样例 1

  • 输入:7 / abacaba
  • 输出:1

样例 2

  • 输入:20 / ahahahahahahahahahah
  • 输出:20

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2024年春招-京东-技术通用岗位-第二批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解