1. 項(xiàng)目概述從一道題看編程思維的構(gòu)建最近在帶新人刷題發(fā)現(xiàn)很多人對(duì)LeetCode 771這道“寶石與石頭”的題有種復(fù)雜的情緒。一方面覺(jué)得它太簡(jiǎn)單看一眼就知道用集合Set或者哈希表Hash Table來(lái)解另一方面真正動(dòng)手寫(xiě)的時(shí)候又會(huì)在邊界條件、代碼簡(jiǎn)潔性或者不同解法的性能差異上栽跟頭。這道題就像編程世界里的“Hello World Plus”它不滿足于讓你打印一句話而是要求你處理數(shù)據(jù)、應(yīng)用基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)并輸出一個(gè)有意義的結(jié)果。今天我就以這道題為例拆解一下如何從“看懂題”到“寫(xiě)出好代碼”并深入聊聊那些看似簡(jiǎn)單背后的設(shè)計(jì)考量與性能玄機(jī)。題目本身很簡(jiǎn)單給你一個(gè)字符串jewels代表寶石類(lèi)型另一個(gè)字符串stones代表你擁有的石頭。stones中的每個(gè)字符代表一種石頭jewels中的每個(gè)字符代表一種寶石。你需要統(tǒng)計(jì)stones中有多少顆“石頭”是“寶石”。換句話說(shuō)就是統(tǒng)計(jì)stones中有多少個(gè)字符出現(xiàn)在jewels中。例如jewels “aA”,stones “aAAbbbb”那么寶石‘a(chǎn)’和‘A’在石頭中出現(xiàn)了3次‘a(chǎn)’出現(xiàn)1次‘A’出現(xiàn)2次。這題的核心價(jià)值不在于算法有多高深而在于它完美地詮釋了“問(wèn)題抽象 - 數(shù)據(jù)結(jié)構(gòu)選擇 - 代碼實(shí)現(xiàn) - 優(yōu)化分析”這一完整的編程思維鏈條。無(wú)論是剛?cè)腴T(mén)的新手還是想鞏固基礎(chǔ)的老手重新審視這道題都能有新的收獲。接下來(lái)我們就一步步拆解。1.1 核心需求與抽象建模面對(duì)任何編程問(wèn)題第一步永遠(yuǎn)是理解并抽象需求。LeetCode 771的需求非常明確輸入兩個(gè)字符串jewels和stones。處理判斷stones中的每個(gè)字符是否存在于jewels這個(gè)字符集合中。輸出滿足條件的字符個(gè)數(shù)計(jì)數(shù)。抽象來(lái)看這是一個(gè)典型的集合成員判定與計(jì)數(shù)問(wèn)題。jewels定義了一個(gè)“有效字符”的集合我們需要遍歷stones這個(gè)序列并對(duì)每個(gè)元素進(jìn)行“是否屬于某個(gè)集合”的檢查屬于則計(jì)數(shù)加一。這個(gè)抽象直接指向了兩個(gè)關(guān)鍵操作高效查找Lookup我們需要頻繁地查詢(xún)一個(gè)字符是否在寶石類(lèi)型中。在編程中數(shù)組列表的按值查找是O(n)的而哈希表在Python中是set或dict的查找平均是O(1)的。因此將jewels轉(zhuǎn)換為一個(gè)支持高效查找的數(shù)據(jù)結(jié)構(gòu)是優(yōu)化的關(guān)鍵。遍歷與計(jì)數(shù)Iteration Counting我們需要訪問(wèn)stones中的每一個(gè)字符。這是一個(gè)標(biāo)準(zhǔn)的線性遍歷過(guò)程。理解到這一層解決方案的大方向就確定了將jewels預(yù)處理為哈希集合set然后遍歷stones進(jìn)行計(jì)數(shù)。這就是從問(wèn)題描述到技術(shù)方案的第一次跳躍。2. 解法深度剖析從暴力到優(yōu)雅很多人覺(jué)得這道題只有一種解法其實(shí)不然。從最直觀的暴力法到最Pythonic的寫(xiě)法中間體現(xiàn)了對(duì)語(yǔ)言特性和算法效率的不同理解層次。我們逐一分析。2.1 解法一雙重循環(huán)暴力法新手易犯這是最直觀的解法也是很多新手在不假思索時(shí)的第一反應(yīng)。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 # 找到即可跳出內(nèi)層循環(huán) return count原理與復(fù)雜度分析原理對(duì)stones中的每一顆“石頭”外層循環(huán)都去jewels字符串中從頭到尾掃描一遍內(nèi)層循環(huán)看是否存在相同的字符。時(shí)間復(fù)雜度O(m * n)其中 m 是stones的長(zhǎng)度n 是jewels的長(zhǎng)度。在最壞情況下沒(méi)有寶石或只有最后一顆是寶石需要對(duì)每個(gè)石頭遍歷整個(gè)寶石串?？臻g復(fù)雜度O(1)只使用了常數(shù)級(jí)別的額外空間一個(gè)計(jì)數(shù)變量。注意雖然這段代碼邏輯正確但在LeetCode上提交當(dāng)字符串長(zhǎng)度較大時(shí)很容易因?yàn)槌瑫r(shí)Time Limit Exceeded而失敗。它揭示了算法設(shè)計(jì)中一個(gè)基本原則減少不必要的重復(fù)計(jì)算。這里jewels被反復(fù)遍歷了m次這是性能瓶頸。2.2 解法二哈希集合標(biāo)準(zhǔn)解法這是本題的標(biāo)準(zhǔn)答案也是面試官期望看到的解法。它通過(guò)空間換時(shí)間將查找效率從O(n)提升到O(1)。class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: jewel_set set(jewels) # 關(guān)鍵步驟預(yù)處理為集合 count 0 for stone in stones: if stone in jewel_set: # 集合的in操作平均時(shí)間復(fù)雜度為O(1) count 1 return count原理與復(fù)雜度分析原理jewel_set set(jewels)將字符串jewels轉(zhuǎn)換為一個(gè)集合。集合的特性是元素唯一且基于哈希表實(shí)現(xiàn)支持平均時(shí)間復(fù)雜度為O(1)的成員查詢(xún)in操作。遍歷stones對(duì)于每個(gè)字符用in操作判斷其是否在jewel_set中。時(shí)間復(fù)雜度O(m n)。其中構(gòu)建集合需要遍歷jewels復(fù)雜度O(n)遍歷stones并進(jìn)行m次查找由于每次查找是O(1)所以總復(fù)雜度為O(m)。整體是線性復(fù)雜度。空間復(fù)雜度O(n)用于存儲(chǔ)寶石集合。在最壞情況下所有字符都不同需要存儲(chǔ)n個(gè)字符。為什么用set而不用list這是核心考點(diǎn)。if stone in list的操作對(duì)于列表list是線性查找復(fù)雜度O(n)。而if stone in set對(duì)于集合是平均常數(shù)查找。當(dāng)n很大時(shí)兩者的性能差異是天壤之別。將jewels預(yù)存為集合相當(dāng)于為后續(xù)的m次查詢(xún)制作了一份“速查表”。2.3 解法三利用Python內(nèi)置函數(shù)與生成器Pythonic寫(xiě)法對(duì)于Python而言我們可以寫(xiě)出更簡(jiǎn)潔、更具表達(dá)力的代碼。class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: jewel_set set(jewels) # 方法1使用生成器表達(dá)式與sum return sum(1 for stone in stones if stone in jewel_set) # 方法2直接使用集合的交集思想需稍作轉(zhuǎn)換 # return sum(stone in jewel_set for stone in stones)原理與技巧sum(1 for stone in stones if stone in jewel_set)這是一個(gè)生成器表達(dá)式。它并不立即創(chuàng)建一個(gè)完整的列表而是產(chǎn)生一個(gè)迭代器。對(duì)于stones中的每個(gè)stone如果它在jewel_set中就生成一個(gè)1否則不生成。sum()函數(shù)則將這些1累加起來(lái)得到總數(shù)。這種方式內(nèi)存效率極高尤其適合處理超長(zhǎng)字符串。sum(stone in jewel_set for stone in stones)這里利用了Python中布爾值True/False在算術(shù)運(yùn)算中會(huì)被當(dāng)作1/0的特性。表達(dá)式stone in jewel_set的結(jié)果是布爾值sum會(huì)自動(dòng)將其轉(zhuǎn)換為整數(shù)求和。寫(xiě)法更短但可讀性稍遜于顯式寫(xiě)1。哪種寫(xiě)法更好在算法競(jìng)賽或面試中解法二顯式循環(huán)通常是更安全、更清晰的選擇因?yàn)樗逦卣故玖恕邦A(yù)處理集合”和“遍歷計(jì)數(shù)”兩個(gè)步驟意圖明確所有語(yǔ)言的面試官都能看懂。而在實(shí)際Python工程或追求代碼簡(jiǎn)潔時(shí)解法三生成器表達(dá)式是更地道的Python風(fēng)格性能相同且更優(yōu)雅。2.4 解法四基于字典Counter的計(jì)數(shù)我們還可以換一個(gè)角度思考先統(tǒng)計(jì)stones中每種石頭出現(xiàn)的次數(shù)然后只累加那些是寶石的石頭數(shù)量。from collections import Counter class Solution: def numJewelsInStones(self, jewels: str, stones: str) - int: stone_counter Counter(stones) # 統(tǒng)計(jì)石頭頻率例如 {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原理與適用場(chǎng)景原理Counter(stones)會(huì)遍歷一次stones生成一個(gè)字典記錄每個(gè)字符及其出現(xiàn)的次數(shù)。然后我們遍歷這個(gè)計(jì)數(shù)器如果字符是寶石就將其頻率累加到結(jié)果中。時(shí)間復(fù)雜度O(m n)。遍歷stones構(gòu)建Counter是O(m)遍歷Counter最多m個(gè)鍵并查找是O(k)k是stones中不同字符的數(shù)量總體仍是線性。空間復(fù)雜度O(m)在最壞情況下所有字符都不同Counter需要存儲(chǔ)m個(gè)鍵值對(duì)。與解法二的對(duì)比當(dāng)stones中重復(fù)字符非常多時(shí)這種方法的遍歷次數(shù)可能更少。解法二需要遍歷stones的每個(gè)字符m次而本方法只需要遍歷stones中不同的字符k次k ≤ m。如果stones是”aaaaabbbbb…”這種大量重復(fù)的k很小本方法在常數(shù)項(xiàng)上有優(yōu)勢(shì)。但是它引入了額外的數(shù)據(jù)結(jié)構(gòu)Counter空間開(kāi)銷(xiāo)通常比單純的jewel_set大。對(duì)于本題的常規(guī)輸入解法二集合在時(shí)間和空間的平衡上是最優(yōu)的也是面試中最常見(jiàn)的答案。3. 關(guān)鍵細(xì)節(jié)與邊界條件處理即使是一個(gè)簡(jiǎn)單的題目健壯的代碼也需要考慮邊界情況。以下是幾個(gè)容易忽略的細(xì)節(jié)3.1 輸入字符串可能為空題目沒(méi)有明確說(shuō)明字符串不會(huì)為空因此防御性編程是好的習(xí)慣。def numJewelsInStones(self, jewels: str, stones: str) - int: if not jewels: # 如果沒(méi)有寶石那么結(jié)果一定是0 return 0 jewel_set set(jewels) # ... 后續(xù)邏輯不變實(shí)際上即使jewels為空set(jewels)會(huì)得到一個(gè)空集合后續(xù)遍歷stones時(shí)if stone in empty_set永遠(yuǎn)為False結(jié)果也是0。所以從功能上講不特殊處理也是正確的。但顯式處理空輸入能使代碼意圖更清晰。3.2 字符集與大小寫(xiě)敏感題目示例使用了大小寫(xiě)字母這提示我們本題是大小寫(xiě)敏感的?！產(chǎn)‘和’A‘被視為不同的寶石類(lèi)型。這是很多字符串處理題目的常見(jiàn)陷阱。我們的基于集合的解法天然支持這一點(diǎn)因?yàn)榧现械摹痑‘和’A‘就是兩個(gè)不同的元素。3.3 選擇set而非list的再?gòu)?qiáng)調(diào)我見(jiàn)過(guò)有人寫(xiě)出這樣的代碼# 低效代碼 jewel_list list(jewels) # 或者直接 jewels_str jewels count 0 for stone in stones: if stone in jewel_list: # 這里是O(n)的線性查找 count 1這本質(zhì)上和暴力法沒(méi)有區(qū)別只是把內(nèi)層循環(huán)隱藏在了in操作符里。務(wù)必記住對(duì)list使用in操作符是線性查找。這是本題最核心的考察點(diǎn)之一。3.4 空間復(fù)雜度的權(quán)衡有同學(xué)可能會(huì)問(wèn)既然jewels和stones都只包含英文字母那是不是可以用一個(gè)大小為5226大寫(xiě)26小寫(xiě)的布爾數(shù)組或列表來(lái)代替setdef numJewelsInStones(self, jewels: str, stones: str) - int: is_jewel [False] * 128 # ASCII碼范圍更安全 for c in jewels: is_jewel[ord(c)] True # 標(biāo)記寶石字符 count 0 for c in stones: if is_jewel[ord(c)]: count 1 return count這完全是一個(gè)可行的、并且在某些情況下更優(yōu)的解法時(shí)間復(fù)雜度O(mn)同樣是線性?？臻g復(fù)雜度O(1)因?yàn)閿?shù)組大小是固定的128或52與輸入規(guī)模無(wú)關(guān)。優(yōu)點(diǎn)查找速度極快是直接的數(shù)組索引操作O(1)常數(shù)項(xiàng)時(shí)間可能比哈希集合的查找更小。缺點(diǎn)通用性稍差。如果題目擴(kuò)展了字符范圍比如包含數(shù)字、符號(hào)、Unicode字符這個(gè)固定大小的數(shù)組就需要調(diào)整或變得不適用。而set可以處理任意可哈希的元素。在面試中提出這種基于數(shù)組的解法并分析其與哈希集合的優(yōu)劣能很好地展示你對(duì)計(jì)算機(jī)基礎(chǔ)ASCII、數(shù)組和問(wèn)題泛化能力的思考。4. 性能測(cè)試與對(duì)比分析“紙上得來(lái)終覺(jué)淺絕知此事要躬行?！?我們寫(xiě)一段簡(jiǎn)單的測(cè)試代碼來(lái)直觀感受一下不同解法在性能上的差異。import timeit import random # 生成測(cè)試數(shù)據(jù) def generate_test_case(length_j, length_s): # 假設(shè)字符范圍是大小寫(xiě)字母 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 # 測(cè)試函數(shù) def test_performance(): jewels, stones generate_test_case(50, 1000000) # 50種寶石100萬(wàn)顆石頭 sol Solution() # 測(cè)試暴力法 (對(duì)于大數(shù)據(jù)會(huì)很慢這里用小數(shù)據(jù)測(cè)試其正確性即可) # 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) # 固定數(shù)組法 t_arr timeit.timeit(lambda: sol.numJewelsInStones_array(jewels, stones), number10) print(fArray Index Method:{t_arr:.4f} seconds) if __name__ __main__: test_performance()在我的環(huán)境中運(yùn)行一次可能得到類(lèi)似下面的結(jié)果具體時(shí)間因機(jī)器而異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結(jié)果分析哈希集合法和生成器法性能幾乎一致印證了它們本質(zhì)是相同的算法只是寫(xiě)法不同。Counter法稍慢因?yàn)樗枰~外構(gòu)建一個(gè)完整的頻率字典這個(gè)開(kāi)銷(xiāo)在石頭種類(lèi)很多時(shí)比較明顯。固定數(shù)組法表現(xiàn)最好因?yàn)樗牟檎沂羌兇獾臄?shù)組索引沒(méi)有哈希計(jì)算的開(kāi)銷(xiāo)。這驗(yàn)證了我們之前的理論分析。所有O(mn)復(fù)雜度的方法在處理百萬(wàn)級(jí)數(shù)據(jù)時(shí)都在零點(diǎn)幾秒內(nèi)完成而暴力法O(m*n)在此數(shù)據(jù)規(guī)模下將完全不可行理論上需要約500億次比較。5. 常見(jiàn)“坑點(diǎn)”與面試擴(kuò)展在實(shí)際編碼和面試中圍繞這道題可能衍生出一些更深層次的討論。5.1 關(guān)于in操作符的誤解初學(xué)者容易混淆in在不同數(shù)據(jù)結(jié)構(gòu)上的復(fù)雜度。務(wù)必牢記x in list- O(n) 線性查找x in set- O(1)平均時(shí)間復(fù)雜度哈希查找x in dict- O(1)平均時(shí)間復(fù)雜度鍵查找x in str- O(n) 線性查找在不確定數(shù)據(jù)結(jié)構(gòu)時(shí)使用in要小心。5.2 如果stones是一個(gè)超大的流Stream這是面試中一個(gè)很好的擴(kuò)展問(wèn)題。如果stones不是一個(gè)可以一次性讀入內(nèi)存的字符串而是一個(gè)來(lái)自網(wǎng)絡(luò)或文件的流一次只能讀一個(gè)字符我們的解法如何調(diào)整答案是解法二集合法依然有效且是最佳選擇。預(yù)處理階段將jewels讀入內(nèi)存構(gòu)建jewel_set。這部分?jǐn)?shù)據(jù)通常很小。統(tǒng)計(jì)階段從流中逐個(gè)讀取stone字符判斷if stone in jewel_set并計(jì)數(shù)。內(nèi)存中只需要維持一個(gè)計(jì)數(shù)器和集合內(nèi)存消耗是O(n)與stones的總大小無(wú)關(guān)。而Counter法在這里就不適用了因?yàn)樗枰冉y(tǒng)計(jì)整個(gè)stones的頻率這在流式數(shù)據(jù)下無(wú)法做到。5.3 多語(yǔ)言實(shí)現(xiàn)的差異這道題幾乎可以用所有編程語(yǔ)言實(shí)現(xiàn)。理解其核心思想后在不同語(yǔ)言中只是語(yǔ)法轉(zhuǎn)換Java/C使用HashSet/unordered_set。JavaScript使用Set對(duì)象。Go使用map[rune]bool或map[byte]bool來(lái)模擬集合。關(guān)鍵點(diǎn)始終是將寶石集合預(yù)處理為哈希結(jié)構(gòu)以實(shí)現(xiàn)常數(shù)時(shí)間查找。5.4 單元測(cè)試的編寫(xiě)?zhàn)B成寫(xiě)單元測(cè)試的習(xí)慣能極大提高代碼質(zhì)量。針對(duì)本題可以設(shè)計(jì)以下測(cè)試用例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()覆蓋了正常情況、邊界情況空字符串、大小寫(xiě)敏感、全部匹配等場(chǎng)景這樣的代碼才足夠健壯。回過(guò)頭看LeetCode 771 “Jewels and Stones” 遠(yuǎn)不止是一道簡(jiǎn)單的計(jì)數(shù)題。它是一個(gè)絕佳的樣本讓我們練習(xí)如何將問(wèn)題抽象為集合查找模型如何根據(jù)操作頻率選擇合適的數(shù)據(jù)結(jié)構(gòu)哈希集合如何寫(xiě)出不同風(fēng)格但同樣高效的代碼以及如何思考邊界條件和性能權(quán)衡。下次再遇到它不妨多花幾分鐘想想還有沒(méi)有其他寫(xiě)法每種寫(xiě)法的優(yōu)缺點(diǎn)是什么。把這些基礎(chǔ)打牢面對(duì)更復(fù)雜的題目時(shí)你才能游刃有余。