贝壳找房 · 字符串 · 算法编程题
贝壳找房 字符串 T ≤ 1e3 时限 1 秒 / 64 MB

题目描述

牛牛的吉他老师牛妹告诉他，吉他初学者需要熟练弹奏三个旋律： 63231323, 53231323, 43231323 ，即：吉他从下到上一共 6 根弦，依次编号为 1 ~ 6 ，然后右手分别用相应的手指按照上述顺序拨动对应的弦。
牛牛为了测试牛妹老师的专业性，特意弹奏了若干段，希望牛妹听完后告诉它，其中包括了几次上述基本旋律。

输入输出

输入描述
本题为多组测试数据，第一行输入一个正整数 T( 1≤ T≤ 1000) ，代表测试数据组数。
对于每组测试数据，一行输入一个仅包含数字 1 ~ 6 的字符串 s( s≤ 1000) ，代表牛牛弹奏的旋律。
输出描述
对于每段旋律，一行输出一个整数，代表这段旋律一共包含了多少次基本旋律。

样例共 1 组

样例 1
输入
3
165432313236
632313225323
666653231323
输出
1
0
1

算法解析依据充分

考点：字符串

数据规模 T ≤ 1e3 ｜ 限制 1 秒 / 64MB ｜ 标准输入输出

题目画像

  • 数据规模：T ≤ 1e3
  • 元素值域：s ≤ 1e3（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：字符串

本题切入点

统计三种基本旋律在给定串中的出现次数，用窗口逐个位置比对 8 位即可。

按字符逐个处理，或利用字符串的前后缀性质加速匹配。

思路框架（字符串 通法 · 非本题专属）

  1. 明确操作对象是字符还是子串、是否需要保持原顺序。
  2. 子串问题常用双指针 / 滑动窗口；回文问题可用中心扩展或哈希。
  3. 多模式匹配考虑 Trie 或 KMP；只需计数则用哈希表统计字符频次。
  4. 注意字符集大小写敏感性与输入是否带引号。

实现要点：Python 切片 s[l:r+1] 取子串；注意字符串不可变，频繁拼接改用 list。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 下标与切片边界差 1。
  • 忽略了大小写、空白字符的影响。

对照本题

  • 数据规模 T ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：3 / 165432313236 / 632313225323 / 666653231323
  • 输出：1 / 0 / 1

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

本题来源：贝壳找房2023届校招算法卷2。

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