LeetCode 771宝石与石头：从集合查找看哈希表与算法优化-北京尧图网络

1. 项目概述从一道题看编程思维的构建最近在带新人刷题发现很多人对LeetCode 771这道“宝石与石头”的题有种复杂的情绪。一方面觉得它太简单看一眼就知道用集合Set或者哈希表Hash Table来解另一方面真正动手写的时候又会在边界条件、代码简洁性或者不同解法的性能差异上栽跟头。这道题就像编程世界里的“Hello World Plus”它不满足于让你打印一句话而是要求你处理数据、应用基础数据结构并输出一个有意义的结果。今天我就以这道题为例拆解一下如何从“看懂题”到“写出好代码”并深入聊聊那些看似简单背后的设计考量与性能玄机。题目本身很简单给你一个字符串jewels代表宝石类型另一个字符串stones代表你拥有的石头。stones中的每个字符代表一种石头jewels中的每个字符代表一种宝石。你需要统计stones中有多少颗“石头”是“宝石”。换句话说就是统计stones中有多少个字符出现在jewels中。例如jewels “aA”,stones “aAAbbbb”那么宝石‘a’和‘A’在石头中出现了3次‘a’出现1次‘A’出现2次。这题的核心价值不在于算法有多高深而在于它完美地诠释了“问题抽象 - 数据结构选择 - 代码实现 - 优化分析”这一完整的编程思维链条。无论是刚入门的新手还是想巩固基础的老手重新审视这道题都能有新的收获。接下来我们就一步步拆解。1.1 核心需求与抽象建模面对任何编程问题第一步永远是理解并抽象需求。LeetCode 771的需求非常明确输入两个字符串jewels和stones。处理判断stones中的每个字符是否存在于jewels这个字符集合中。输出满足条件的字符个数计数。抽象来看这是一个典型的集合成员判定与计数问题。jewels定义了一个“有效字符”的集合我们需要遍历stones这个序列并对每个元素进行“是否属于某个集合”的检查属于则计数加一。这个抽象直接指向了两个关键操作高效查找Lookup我们需要频繁地查询一个字符是否在宝石类型中。在编程中数组列表的按值查找是O(n)的而哈希表在Python中是set或dict的查找平均是O(1)的。因此将jewels转换为一个支持高效查找的数据结构是优化的关键。遍历与计数Iteration Counting我们需要访问stones中的每一个字符。这是一个标准的线性遍历过程。理解到这一层解决方案的大方向就确定了将jewels预处理为哈希集合set然后遍历stones进行计数。这就是从问题描述到技术方案的第一次跳跃。2. 解法深度剖析从暴力到优雅很多人觉得这道题只有一种解法其实不然。从最直观的暴力法到最Pythonic的写法中间体现了对语言特性和算法效率的不同理解层次。我们逐一分析。2.1 解法一双重循环暴力法新手易犯这是最直观的解法也是很多新手在不假思索时的第一反应。class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: count 0 for stone in stones: for jewel in jewels: if stone jewel: count 1 break # 找到即可跳出内层循环 return count原理与复杂度分析原理对stones中的每一颗“石头”外层循环都去jewels字符串中从头到尾扫描一遍内层循环看是否存在相同的字符。时间复杂度O(m * n)其中 m 是stones的长度n 是jewels的长度。在最坏情况下没有宝石或只有最后一颗是宝石需要对每个石头遍历整个宝石串。空间复杂度O(1)只使用了常数级别的额外空间一个计数变量。注意虽然这段代码逻辑正确但在LeetCode上提交当字符串长度较大时很容易因为超时Time Limit Exceeded而失败。它揭示了算法设计中一个基本原则减少不必要的重复计算。这里jewels被反复遍历了m次这是性能瓶颈。2.2 解法二哈希集合标准解法这是本题的标准答案也是面试官期望看到的解法。它通过空间换时间将查找效率从O(n)提升到O(1)。class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: jewel_set set(jewels) # 关键步骤预处理为集合 count 0 for stone in stones: if stone in jewel_set: # 集合的in操作平均时间复杂度为O(1) count 1 return count原理与复杂度分析原理jewel_set set(jewels)将字符串jewels转换为一个集合。集合的特性是元素唯一且基于哈希表实现支持平均时间复杂度为O(1)的成员查询in操作。遍历stones对于每个字符用in操作判断其是否在jewel_set中。时间复杂度O(m n)。其中构建集合需要遍历jewels复杂度O(n)遍历stones并进行m次查找由于每次查找是O(1)所以总复杂度为O(m)。整体是线性复杂度。空间复杂度O(n)用于存储宝石集合。在最坏情况下所有字符都不同需要存储n个字符。为什么用set而不用list这是核心考点。if stone in list的操作对于列表list是线性查找复杂度O(n)。而if stone in set对于集合是平均常数查找。当n很大时两者的性能差异是天壤之别。将jewels预存为集合相当于为后续的m次查询制作了一份“速查表”。2.3 解法三利用Python内置函数与生成器Pythonic写法对于Python而言我们可以写出更简洁、更具表达力的代码。class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: jewel_set set(jewels) # 方法1使用生成器表达式与sum return sum(1 for stone in stones if stone in jewel_set) # 方法2直接使用集合的交集思想需稍作转换 # return sum(stone in jewel_set for stone in stones)原理与技巧sum(1 for stone in stones if stone in jewel_set)这是一个生成器表达式。它并不立即创建一个完整的列表而是产生一个迭代器。对于stones中的每个stone如果它在jewel_set中就生成一个1否则不生成。sum()函数则将这些1累加起来得到总数。这种方式内存效率极高尤其适合处理超长字符串。sum(stone in jewel_set for stone in stones)这里利用了Python中布尔值True/False在算术运算中会被当作1/0的特性。表达式stone in jewel_set的结果是布尔值sum会自动将其转换为整数求和。写法更短但可读性稍逊于显式写1。哪种写法更好在算法竞赛或面试中解法二显式循环通常是更安全、更清晰的选择因为它清晰地展示了“预处理集合”和“遍历计数”两个步骤意图明确所有语言的面试官都能看懂。而在实际Python工程或追求代码简洁时解法三生成器表达式是更地道的Python风格性能相同且更优雅。2.4 解法四基于字典Counter的计数我们还可以换一个角度思考先统计stones中每种石头出现的次数然后只累加那些是宝石的石头数量。from collections import Counter class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: stone_counter Counter(stones) # 统计石头频率例如 {a:1, A:2, b:4} jewel_set set(jewels) count 0 for stone, freq in stone_counter.items(): if stone in jewel_set: count freq return count原理与适用场景原理Counter(stones)会遍历一次stones生成一个字典记录每个字符及其出现的次数。然后我们遍历这个计数器如果字符是宝石就将其频率累加到结果中。时间复杂度O(m n)。遍历stones构建Counter是O(m)遍历Counter最多m个键并查找是O(k)k是stones中不同字符的数量总体仍是线性。空间复杂度O(m)在最坏情况下所有字符都不同Counter需要存储m个键值对。与解法二的对比当stones中重复字符非常多时这种方法的遍历次数可能更少。解法二需要遍历stones的每个字符m次而本方法只需要遍历stones中不同的字符k次k ≤ m。如果stones是”aaaaabbbbb…”这种大量重复的k很小本方法在常数项上有优势。但是它引入了额外的数据结构Counter空间开销通常比单纯的jewel_set大。对于本题的常规输入解法二集合在时间和空间的平衡上是最优的也是面试中最常见的答案。3. 关键细节与边界条件处理即使是一个简单的题目健壮的代码也需要考虑边界情况。以下是几个容易忽略的细节3.1 输入字符串可能为空题目没有明确说明字符串不会为空因此防御性编程是好的习惯。def numJewelsInStones(self, jewels: str, stones: str) - int: if not jewels: # 如果没有宝石那么结果一定是0 return 0 jewel_set set(jewels) # ... 后续逻辑不变实际上即使jewels为空set(jewels)会得到一个空集合后续遍历stones时if stone in empty_set永远为False结果也是0。所以从功能上讲不特殊处理也是正确的。但显式处理空输入能使代码意图更清晰。3.2 字符集与大小写敏感题目示例使用了大小写字母这提示我们本题是大小写敏感的。‘a‘和’A‘被视为不同的宝石类型。这是很多字符串处理题目的常见陷阱。我们的基于集合的解法天然支持这一点因为集合中的’a‘和’A‘就是两个不同的元素。3.3 选择set而非list的再强调我见过有人写出这样的代码# 低效代码 jewel_list list(jewels) # 或者直接 jewels_str jewels count 0 for stone in stones: if stone in jewel_list: # 这里是O(n)的线性查找 count 1这本质上和暴力法没有区别只是把内层循环隐藏在了in操作符里。务必记住对list使用in操作符是线性查找。这是本题最核心的考察点之一。3.4 空间复杂度的权衡有同学可能会问既然jewels和stones都只包含英文字母那是不是可以用一个大小为5226大写26小写的布尔数组或列表来代替setdef numJewelsInStones(self, jewels: str, stones: str) - int: is_jewel [False] * 128 # ASCII码范围更安全 for c in jewels: is_jewel[ord(c)] True # 标记宝石字符 count 0 for c in stones: if is_jewel[ord(c)]: count 1 return count这完全是一个可行的、并且在某些情况下更优的解法时间复杂度O(mn)同样是线性。空间复杂度O(1)因为数组大小是固定的128或52与输入规模无关。优点查找速度极快是直接的数组索引操作O(1)常数项时间可能比哈希集合的查找更小。缺点通用性稍差。如果题目扩展了字符范围比如包含数字、符号、Unicode字符这个固定大小的数组就需要调整或变得不适用。而set可以处理任意可哈希的元素。在面试中提出这种基于数组的解法并分析其与哈希集合的优劣能很好地展示你对计算机基础ASCII、数组和问题泛化能力的思考。4. 性能测试与对比分析“纸上得来终觉浅绝知此事要躬行。” 我们写一段简单的测试代码来直观感受一下不同解法在性能上的差异。import timeit import random # 生成测试数据 def generate_test_case(length_j, length_s): # 假设字符范围是大小写字母 chars [chr(i) for i in range(ord(a), ord(z)1)] [chr(i) for i in range(ord(A), ord(Z)1)] jewels .join(random.choices(chars, klength_j)) stones .join(random.choices(chars, klength_s)) return jewels, stones # 测试函数 def test_performance(): jewels, stones generate_test_case(50, 1000000) # 50种宝石100万颗石头 sol Solution() # 测试暴力法 (对于大数据会很慢这里用小数据测试其正确性即可) # print(Brute Force:, timeit.timeit(lambda: sol.numJewelsInStones_brute(jewels[:5], stones[:100]), number10)) print(fTest with |J|{len(jewels)}, |S|{len(stones)}) print(- * 40) # 哈希集合法 t_set timeit.timeit(lambda: sol.numJewelsInStones_set(jewels, stones), number10) print(fHash Set Method: {t_set:.4f} seconds) # Pythonic生成器法 t_gen timeit.timeit(lambda: sol.numJewelsInStones_gen(jewels, stones), number10) print(fGenerator Method: {t_gen:.4f} seconds) # Counter法 t_cnt timeit.timeit(lambda: sol.numJewelsInStones_counter(jewels, stones), number10) print(fCounter Method: {t_cnt:.4f} seconds) # 固定数组法 t_arr timeit.timeit(lambda: sol.numJewelsInStones_array(jewels, stones), number10) print(fArray Index Method:{t_arr:.4f} seconds) if __name__ __main__: test_performance()在我的环境中运行一次可能得到类似下面的结果具体时间因机器而异Test with |J|50, |S|1000000 ---------------------------------------- Hash Set Method: 0.0987 seconds Generator Method: 0.1021 seconds Counter Method: 0.1354 seconds Array Index Method:0.0753 seconds结果分析哈希集合法和生成器法性能几乎一致印证了它们本质是相同的算法只是写法不同。Counter法稍慢因为它需要额外构建一个完整的频率字典这个开销在石头种类很多时比较明显。固定数组法表现最好因为它的查找是纯粹的数组索引没有哈希计算的开销。这验证了我们之前的理论分析。所有O(mn)复杂度的方法在处理百万级数据时都在零点几秒内完成而暴力法O(m*n)在此数据规模下将完全不可行理论上需要约500亿次比较。5. 常见“坑点”与面试扩展在实际编码和面试中围绕这道题可能衍生出一些更深层次的讨论。5.1 关于in操作符的误解初学者容易混淆in在不同数据结构上的复杂度。务必牢记x in list- O(n) 线性查找x in set- O(1)平均时间复杂度哈希查找x in dict- O(1)平均时间复杂度键查找x in str- O(n) 线性查找在不确定数据结构时使用in要小心。5.2 如果stones是一个超大的流Stream这是面试中一个很好的扩展问题。如果stones不是一个可以一次性读入内存的字符串而是一个来自网络或文件的流一次只能读一个字符我们的解法如何调整答案是解法二集合法依然有效且是最佳选择。预处理阶段将jewels读入内存构建jewel_set。这部分数据通常很小。统计阶段从流中逐个读取stone字符判断if stone in jewel_set并计数。内存中只需要维持一个计数器和集合内存消耗是O(n)与stones的总大小无关。而Counter法在这里就不适用了因为它需要先统计整个stones的频率这在流式数据下无法做到。5.3 多语言实现的差异这道题几乎可以用所有编程语言实现。理解其核心思想后在不同语言中只是语法转换Java/C使用HashSet/unordered_set。JavaScript使用Set对象。Go使用map[rune]bool或map[byte]bool来模拟集合。关键点始终是将宝石集合预处理为哈希结构以实现常数时间查找。5.4 单元测试的编写养成写单元测试的习惯能极大提高代码质量。针对本题可以设计以下测试用例import unittest class TestSolution(unittest.TestCase): def setUp(self): self.sol Solution() def test_case1(self): self.assertEqual(self.sol.numJewelsInStones(aA, aAAbbbb), 3) def test_case2(self): self.assertEqual(self.sol.numJewelsInStones(z, ZZ), 0) def test_empty_jewels(self): self.assertEqual(self.sol.numJewelsInStones(, abc), 0) def test_empty_stones(self): self.assertEqual(self.sol.numJewelsInStones(aA, ), 0) def test_both_empty(self): self.assertEqual(self.sol.numJewelsInStones(, ), 0) def test_all_stones_are_jewels(self): self.assertEqual(self.sol.numJewelsInStones(abc, aaabbbccc), 9) if __name__ __main__: unittest.main()覆盖了正常情况、边界情况空字符串、大小写敏感、全部匹配等场景这样的代码才足够健壮。回过头看LeetCode 771 “Jewels and Stones” 远不止是一道简单的计数题。它是一个绝佳的样本让我们练习如何将问题抽象为集合查找模型如何根据操作频率选择合适的数据结构哈希集合如何写出不同风格但同样高效的代码以及如何思考边界条件和性能权衡。下次再遇到它不妨多花几分钟想想还有没有其他写法每种写法的优缺点是什么。把这些基础打牢面对更复杂的题目时你才能游刃有余。

LeetCode 771宝石与石头：从集合查找看哈希表与算法优化

相关推荐

基于SpringBoot的工厂车间生产流程与设备管理系统[源码免费+文档免费]

上海计算机学会|2026年2月月赛|T2奇怪的展开式|顺序输出解法

什么是接口？

更多资讯

大朗电工证在哪里考2026河南最新政策下怎么应对

煤气工特种作业证怎么考？学历不高怕报不上名？良心建议来了

老电工证样子怎么转异地？2026河南最新政策别踩坑

溆浦电工证保姆级教程：工地太忙根本没时间复习考试怎么办？

电工证能上网查你学历不高也能报上名

电工证培训多少天与郑州报考避坑指南

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？