1. 从“宝石与石头”看LeetCode刷题的底层逻辑最近在带几个刚入门算法的朋友刷题他们总问我一个问题“LeetCode上这么多题到底该怎么刷才有效” 我通常会拿一些经典题目当例子比如这道771. Jewels and Stones宝石与石头。别看它简单在LeetCode上被标记为“简单”难度但恰恰是这类题目最能检验一个程序员对基础数据结构的理解是否扎实也最能体现Python这门语言在解决算法问题时的优雅与效率。很多人刷题一上来就追求“奇技淫巧”或者死记硬背模板反而忽略了最根本的“解题思维”和“工具选择”。今天我就以这道题为例拆解一下面对一个具体问题时从理解题意、选择数据结构、编写代码到优化性能的完整思考链条。无论你是正在备战面试的新手还是想巩固基础的熟手相信都能从中获得一些启发。2. 问题拆解理解题意与明确输入输出2.1 问题描述还原题目“Jewels and Stones”的描述非常直白给你两个字符串jewels和stones。字符串jewels代表的是宝石类型其中的每个字符都是一种独特的宝石。字符串stones代表你拥有的石头其中的每个字符是一种石头有可能是宝石也可能是普通石头。你需要统计在stones字符串中有多少个“石头”其实是“宝石”也就是字符出现在jewels字符串中。举个例子输入jewels “aA”,stones “aAAbbbb”输出3解释宝石类型是‘a’和‘A’。在石头中‘a’出现了1次‘A’出现了2次所以总共有3颗宝石。这里有几个关键约束和隐含条件需要明确这些往往是新手容易忽略导致边界情况出错的点字符区分大小写这是一个非常重要的条件。‘a’和‘A’被视为两种不同的宝石类型。这在Python中是天生的因为字符串比较是大小写敏感的。jewels中的每个字符都是唯一的。题目没说但根据常识和一般测试用例我们可以认为jewels字符串内无重复字符。不过一个健壮的解法不应该依赖这个假设。字符串只包含英文字母。这是从示例和常规LeetCode约束中可以推断的意味着我们可以安全地使用基于ASCII码的操作。注意永远不要轻视题目描述中的任何一个单词。像“case sensitive”这样的字眼直接决定了你能否使用某些简化操作比如统一转成小写。在面试中明确这些约束并向面试官确认是专业性的体现。2.2 核心需求与抽象建模剥开“宝石”和“石头”这个有趣的故事外壳这道题的核心需求可以抽象为一个经典的集合成员判定问题我们有一个候选集合jewels中的字符。我们有一个数据流stones中的字符序列。我们需要对数据流中的每个元素进行快速判断它是否存在于候选集合中最终目标是统计符合条件的元素个数。这个抽象帮助我们跳出了具体场景直指算法核心如何高效地进行大量stones长度可能很大的集合成员查询针对每个stone字符一旦完成这个抽象我们的思路就清晰了——寻找一个支持高效in操作的数据结构。3. 方案演进从暴力枚举到哈希优化3.1 方案一暴力双重循环新手直觉最直观的想法是遍历stones中的每个字符对于每个字符再遍历jewels字符串检查是否存在匹配。def numJewelsInStones_brute_force(jewels: str, stones: str) - int: count 0 for stone in stones: for jewel in jewels: if stone jewel: count 1 break # 找到即可跳出内层循环 return count复杂度分析时间复杂度O(n * m)其中 n 是stones的长度m 是jewels的长度。这是一个平方级的复杂度。空间复杂度O(1)只使用了常数个额外变量。为什么这是次优解虽然代码简单易懂但当jewels或stones很长时性能会急剧下降。假设stones有10万长度jewels有50种那么最坏情况下需要进行500万次比较。在算法题中这通常是无法通过所有测试用例的会超时。这个方法的价值在于它是最直接的逻辑体现可以作为思考的起点和验证其他算法正确性的基准。3.2 方案二利用列表与in操作常见误区知道双重循环慢一个常见的改进是使用Python的in操作符来检查成员关系。def numJewelsInStones_in_operator(jewels: str, stones: str) - int: count 0 for stone in stones: if stone in jewels: count 1 return count这段代码看起来更简洁了。很多初学者会认为if stone in jewels的时间复杂度是 O(1)从而认为这个算法是 O(n) 的。这是一个经典的误区。关键剖析在Python中对字符串str使用in操作符进行成员检查其底层实现仍然是线性扫描对于字符串jewelsstone in jewels这个操作在最坏情况下需要遍历整个jewels字符串才能确定stone是否存在。因此这个算法的时间复杂度依然是 O(n * m)和暴力法在渐进复杂度上没有本质区别只是代码更简洁且利用了Python内置的、用C实现的循环可能比手写Python层的for循环稍快一些但无法改变平方复杂度的本质。3.3 方案三哈希集合最优解要真正实现高效的成员查询我们需要一个支持平均 O(1) 时间复杂度查询的数据结构。在Python中这就是集合set。def numJewelsInStones_hash_set(jewels: str, stones: str) - int: # 将宝石类型集合化实现O(1)查询 jewel_set set(jewels) count 0 for stone in stones: if stone in jewel_set: # 此处的in操作是O(1) count 1 return count为什么集合是O(1)Python的set是基于哈希表实现的。当我们执行set(jewels)时会将jewels字符串中的所有字符插入哈希表。这个构建过程的时间复杂度是 O(m)其中 m 是jewels的长度。之后每次执行stone in jewel_set哈希表可以通过计算stone的哈希值直接定位到可能存储它的桶从而在常数时间内完成查找。复杂度分析时间复杂度O(m n)。构建集合需要 O(m)遍历stones并查询需要 O(n)。因为查询是 O(1)所以总时间是线性的。空间复杂度O(m) 或 O(k)。这里 k 是字符集的大小。由于jewels中的字符是英文字母最多52种大小写所以空间复杂度可以看作是 O(1) 或 O(52)是一个很小的常数。但在抽象分析时我们通常说 O(m)表示其依赖于输入。这个方案是本题的标准最优解清晰、高效是面试官期望看到的答案。3.4 方案四利用列表推导与sum函数Pythonic写法在掌握了哈希集合的核心思想后我们可以用更“Pythonic”的方式写出简洁的一行代码。def numJewelsInStones_pythonic(jewels: str, stones: str) - int: jewel_set set(jewels) return sum(stone in jewel_set for stone in stones)代码解读stone in jewel_set for stone in stones这是一个生成器表达式。它会遍历stones对每个stone计算stone in jewel_set这个布尔值True或False。在Python中布尔值True和False在参与算术运算时分别被视为1和0。sum()函数将这个生成器产生的所有1是宝石和0不是宝石加起来自然就得到了宝石的总数。这种写法在功能上和方案三完全等价但更加简洁优雅充分体现了Python“用表达代替语句”的风格。它在LeetCode社区中非常受欢迎也是展示你Python功力的一个好机会。实操心得在面试中我建议先写出方案三清晰的哈希集合循环因为它逻辑步骤明确易于讲解。如果面试官表现出兴趣或时间充裕再提一句“这个问题也可以用更Pythonic的生成器表达式一行解决”并简要说明原理。这样既展示了扎实的算法基础又体现了对语言的熟练运用。4. 深入原理哈希表与字符编码4.1 哈希表是如何工作的我们一直在说“集合的in操作是O(1)”这背后是哈希表的功劳。简单来说哈希表通过一个哈希函数将任意大小的输入比如一个字符映射到一个固定大小的索引桶的位置。插入当执行jewel_set set(‘aA’)时哈希表会计算‘a’和‘A’的哈希值根据哈希值找到对应的桶并将字符存储进去。查询当执行‘a’ in jewel_set时哈希表再次计算‘a’的哈希值直接去对应的桶里查找。理想情况下没有哈希冲突一次访问就能得到结果。对于字符这种简单的键Python的哈希函数效率极高并且由于可能的字符总数有限本题中是字母哈希冲突的概率很小因此能保证接近完美的 O(1) 性能。4.2 基于ASCII码的数组模拟哈希表既然我们知道字符范围有限通常是ASCII字母我们甚至可以不用内置的set而用一个固定大小的布尔数组或列表来模拟一个简单的哈希表实现极致的速度。这是一种更底层的优化思路。def numJewelsInStones_array(jewels: str, stones: str) - int: # 创建一个长度为128的布尔数组覆盖标准ASCII码 is_jewel [False] * 128 # 标记宝石字符 for jewel in jewels: is_jewel[ord(jewel)] True # ord()获取字符的ASCII码 # 统计 count 0 for stone in stones: if is_jewel[ord(stone)]: count 1 return count原理解析ord(char)函数返回字符的Unicode码点。对于英文字母这个值在0-127之间ASCII范围。我们创建一个长度为128的列表is_jewel初始值全为False。遍历jewels对于每个字符将其ASCII码作为索引将列表中对应位置标记为True。这相当于构建了一个“直接寻址表”。遍历stones对于每个字符通过ord(stone)直接索引列表如果值为True则计数。复杂度与对比时间复杂度O(m n)和哈希集合相同。空间复杂度O(1)因为数组大小是固定的128与输入规模无关。优势访问数组is_jewel[index]是真正的 O(1)且比哈希表计算哈希值、处理潜在冲突的开销更小。在追求极限性能的场合如竞赛或字符串非常长时这种方法可能略有优势。劣势通用性差。如果输入包含非ASCII字符如中文这种方法就需要扩大数组尺寸不够优雅。而哈希集合可以处理任意可哈希对象。对于LeetCode这道题使用内置set的方案在可读性、简洁性和通用性上是最佳平衡也是面试中的首选。了解数组方法则有助于你深入理解数据结构的本质。5. 边界条件与测试用例设计一个健壮的程序必须能处理各种边界输入。我们可以自己设计测试用例来验证代码。# 测试函数 def test(): solution numJewelsInStones_hash_set # 或用其他函数测试 # 1. 普通用例 assert solution(“aA”, “aAAbbbb”) 3 # 2. 没有宝石 assert solution(“z”, “ZZ”) 0 # 3. 所有石头都是宝石 assert solution(“abc”, “cbaabcabc”) 9 # 4. jewels为空字符串 assert solution(“”, “asdf”) 0 # 5. stones为空字符串 assert solution(“aA”, “”) 0 # 6. 两者都为空 assert solution(“”, “”) 0 # 7. 单个字符 assert solution(“a”, “a”) 1 # 8. 大小写敏感验证 assert solution(“a”, “A”) 0 print(“All tests passed!”)为什么这些测试用例重要用例2和4测试当没有匹配项时程序是否能正确返回0。这检查了循环和累加逻辑的初始化。用例5和6测试空字符串输入。这是常见的边界条件能检验代码是否错误地尝试访问空序列。用例7最小化测试验证基本逻辑。用例8核心约束测试确保没有错误地进行大小写转换。在面试中写完代码后主动提出这些测试用例并解释能极大提升面试官对你的印象说明你思维严谨具备工程化能力。6. 性能对比与实战分析理论分析很重要但实际运行时间如何呢我们可以用Python的timeit模块做一个简单的性能对比假设在非竞赛环境下数据规模适中。import timeit setup_code “““ jewels ‘aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ’ stones ‘a’ * 10000 ‘A’ * 10000 ‘z’ * 10000 # 混合数据 “““ brute_force_code “““ count 0 for s in stones: for j in jewels: if s j: count1 break “““ hash_set_code “““ j_set set(jewels) count 0 for s in stones: if s in j_set: count1 “““ pythonic_code “““ j_set set(jewels) sum(s in j_set for s in stones) “““ array_code “““ is_jewel [False]*128 for j in jewels: is_jewel[ord(j)] True count 0 for s in stones: if is_jewel[ord(s)]: count1 “““ print(“暴力法:”, timeit.timeit(brute_force_code, setupsetup_code, number100)) print(“哈希集:”, timeit.timeit(hash_set_code, setupsetup_code, number100)) print(“Pythonic:”, timeit.timeit(pythonic_code, setupsetup_code, number100)) print(“数组法:”, timeit.timeit(array_code, setupsetup_code, number100))在我的环境中运行结果趋势非常明显哈希集合、Pythonic写法和数组法的耗时处于同一数量级且远快于暴力法。数组法有时会略快一点点但优势并不绝对因为现代Python的set实现已经高度优化。这个实验告诉我们选择正确的数据结构哈希表带来的性能提升是数量级的而在此基础上的语法优化Pythonic写法更多是锦上添花。7. 常见“坑点”与排查技巧即便是一个简单的题目在实际编写和调试时也可能遇到问题。以下是我总结的几个常见“坑点”混淆变量名在循环中误用了相同的迭代变量名。例如写成了for jewel in jewels: if jewel in jewel…。这虽然听起来可笑但在紧张或疲劳时很容易发生。技巧使用有明确意义的变量名如stone_char,jewel_type。错误理解in操作符的复杂度如前所述误以为stone in jewels是 O(1) 操作。这是对Python基础数据结构性能理解不深导致的。排查当你的代码在长输入下超时而算法看起来是 O(n) 时首先检查你是否对字符串、列表等线性结构进行了频繁的in操作。忽略大小写敏感想当然地调用了jewels.lower()或stones.lower()。题目明确要求区分大小写这样做会导致错误。技巧审题时把“case sensitive”这类词圈出来。未处理空输入代码假设输入非空直接开始遍历当输入为空字符串时可能导致错误或非预期结果如for循环跳过返回初始值0这反而是正确的但依赖语言特性。更稳健的做法是不做假设。技巧空字符串是合法的输入你的代码应该能正确处理它。通常我们使用的循环结构for char in “”不会执行因此返回计数器的初始值0是正确的。但如果是其他操作如访问索引就必须先判断长度。使用list代替set知道要用一个容器存jewels但顺手写成了list(jewels)。这样后续的in操作依然是 O(m) 的线性查找性能没有提升。排查问自己“我需要频繁查找吗”如果需要set或dict是你的首选。避坑指南养成“先抽象后具体”的思维习惯。拿到问题先像第二节那样抽象出核心操作频繁查找。这个操作直接决定了你应该选择什么样的数据结构。数据结构选对了代码就成功了一大半。8. 举一反三相关题型与模式识别“Jewels and Stones”代表了一类更广泛的算法问题模式“统计一个集合中元素在另一个序列中出现次数”的变体。掌握这道题你就解锁了解决以下问题的钥匙LeetCode 387. First Unique Character in a String找到第一个不重复的字符。核心同样是先统计每个字符的出现次数可以用哈希表dict或collections.Counter再遍历寻找计数为1的字符。LeetCode 409. Longest Palindrome用给定字母构造最长回文串。需要统计所有字符的频数偶数全用奇数最多用一个。这需要用到字符频率统计。LeetCode 242. Valid Anagram判断两个字符串是否为字母异位词。经典解法是用一个长度为26的数组模拟哈希表统计字符频率或使用collections.Counter直接比较。任何需要“快速查找/去重”的场景比如在处理日志文件时快速过滤掉某个IP列表在用户标签系统中判断用户是否拥有某个特权标签等。它们的共同点是都需要一个辅助的、高效的数据结构哈希表/集合/数组来存储中间状态或查询键。当你看到问题涉及“是否存在”、“出现次数”、“去重”等关键词时第一时间就应该想到哈希表。我个人在刷题和实际开发中有一个习惯对于字符串或序列处理的问题会先画一个“数据结构选择决策树”。如果只是判断存在性首选set如果需要关联计数首选dict(或collections.Counter)如果键的范围很小且是连续整数如小写字母可以考虑用数组列表来获得极致性能。这道“宝石与石头”题就是这张决策树最完美的入门案例。它用最简洁的形式让你深刻体会到选择比努力更重要——在编程中选择合适的数据结构往往比写出复杂的算法逻辑更能提升代码效率。
