贝壳找房 · 哈希 · 算法编程题
贝壳找房 哈希 n ≤ 10 时限 1 秒 / 64 MB

题目描述

有一堆单词，里面可能有大写字母或者小写字母。请你先将单词全部转为小写，找出小写单词里面出现最多的一个单词视为关键词，如果这样的单词有多个，那么找出其中字典序最小的一个。
两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。比如a小于b，ah1x小于ahb，acb小于b。

输入输出

输入描述
输入的第一行输入这堆单词的个数 n ，每行一个长度不超过 10 的字符串，代表一个单词。
一堆单词总共不会超过 10 ^ 4 个单词。
输出描述
一行输出一个字符串以及一个正整数，代表提取出的关键词，以及关键词出现的次数。

样例共 3 组

样例 1 · you最多出现了3次
输入
10
Nice
to
meet
you
I
can
help
you
thank
you
输出
you 3
样例 2 · 都出现了1次，ad的字典序最小
输入
3
b
c
ad
输出
ad 1
样例 3 · 先将B转为b，然后b出现2次，最多
输入
4
B
b
c
ad
输出
b 2

算法解析依据一般

考点：哈希

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

题目画像

  • 数据规模：n ≤ 10
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：哈希

用哈希表把「查找/计数」的开销降到 O(1) 均摊。

思路框架（哈希 通法 · 非本题专属）

  1. 一次遍历，把元素作为 key、出现次数/首次位置作为 value 存进哈希表。
  2. 第二次遍历（或边扫边查）拿到需要的信息。
  3. 注意哈希无序：需要按原顺序输出时要额外记录顺序。

实现要点：Python 用 dict / collections.Counter / defaultdict；C++ 用 unordered_map。

复杂度：时间 O(n) 均摊 ｜ 空间 O(n)

该范式的通法易错点

  • 遍历哈希表时依赖了不存在的顺序。
  • 多次查询时每次都重新统计。

对照本题

  • 数据规模 n ≤ 10，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 10 / Nice / to / meet / you / I / can / help / you / thank / you → 输出 you 3

you最多出现了3次

样例 2：输入 3 / b / c / ad → 输出 ad 1

都出现了1次，ad的字典序最小

样例 3：输入 4 / B / b / c / ad → 输出 b 2

先将B转为b，然后b出现2次，最多

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

本题来源：2024年秋招-贝壳找房-前端工程师-第一批笔试；2024年秋招-贝壳找房-测试开发工程师-第一批笔试。

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