力扣上有一類題讀完題干你會(huì)覺得“這有什么難的”真上手才發(fā)現(xiàn)復(fù)雜度像一把鈍刀慢慢磨你。Maximum Product of Word Lengths 就是非常典型的一道。這道題在力扣LeetCode里編號(hào) 318屬于中等難度表面看是字符串處理實(shí)際考的是二進(jìn)制特性把一個(gè)單詞的字母存在性壓縮成一個(gè)整數(shù)掩碼然后一次按位與就能判斷兩個(gè)單詞有沒有共同字母。我最近把這道題翻出來重新刷了一遍順手整理出三種常見寫法以及一堆藏在細(xì)節(jié)里的坑。這篇筆記既是給自己留檔也是給還在力扣熱題里轉(zhuǎn)悠的朋友們一份可以直接抄作業(yè)的參考。這道題的英文名起得很直白找出兩個(gè)沒有公共字母的單詞讓它們長(zhǎng)度乘積最大。聽起來不難可當(dāng)你面對(duì)幾百上千個(gè)單詞時(shí)就得認(rèn)真想想怎么在 O(n2) 的配對(duì)基礎(chǔ)上把效率提上去以及怎么避免在優(yōu)化過程中偷偷丟掉正確答案。讀完這篇你應(yīng)該能理解為什么位掩碼是這類題的標(biāo)配思路也能搞清楚排序剪枝和去重背后那些容易翻車的小邏輯。1. 題目拆解先搞清楚要計(jì)算的到底是什么1.1 題干速讀與三個(gè)容易被忽略的點(diǎn)題目給一個(gè)字符串?dāng)?shù)組words要求返回length(words[i]) * length(words[j])的最大值條件是兩個(gè)單詞“不含共同字母”。如果不存在這樣的兩個(gè)單詞就返回 0。這里有三個(gè)容易理解偏的地方值得單獨(dú)拎出來說。第一“不含共同字母”指的是兩個(gè)單詞的字母集合沒有交集不是字符計(jì)數(shù)不同。舉個(gè)例子abc和def沒有共同字母完全合規(guī)abc和abd雖然都含 a 和 b但多一個(gè)字母、少一個(gè)字母都不行——只要共同出現(xiàn)過一個(gè)字母就算違規(guī)。所以題目本質(zhì)是在做集合層面的不相交判斷而不是字符串比較。第二目標(biāo)是長(zhǎng)度乘積不是字母種類乘積也不是其他什么指標(biāo)。這意味著句子越長(zhǎng)越值錢兩個(gè)長(zhǎng)單詞如果可以配對(duì)收益遠(yuǎn)大于兩個(gè)短單詞。到這里你已經(jīng)能感受到優(yōu)化方向應(yīng)該圍繞“優(yōu)先討好長(zhǎng)單詞”來展開后面要講的排序剪枝思路正是從這里長(zhǎng)出來的。第三題目只要最大值不要具體是哪兩個(gè)單詞。所以我們?nèi)滩恍枰涗浵聵?biāo)只需要維護(hù)一個(gè)當(dāng)前最優(yōu)值ans不斷嘗試用新配對(duì)的乘積去更新它即可。一個(gè)直觀的例子words [abcw,baz,foo,bar,xtfn,abcdef]。其中abcw和xtfn沒有共同字母長(zhǎng)度是 4 × 4 16abcw和baz雖然長(zhǎng)度乘積也是 4 × 3但共同擁有 a直接出局。最終答案就是 16。1.2 為什么 O(n2) 逃不掉但能偷懶最原始的思路是兩層循環(huán)枚舉所有下標(biāo)對(duì)(i, j)對(duì)每一對(duì)再逐個(gè)字符檢查兩個(gè)單詞是否共享字母。數(shù)組長(zhǎng)度 n 平均是幾百上千單詞長(zhǎng)度 L 最長(zhǎng)也能到 1000于是總開銷是 O(n2 × L)。最壞情況下比如 1000 個(gè)單詞、每個(gè)單詞 1000 個(gè)字符就有約 10 億次字符操作跑到超時(shí)幾乎是板上釘釘?shù)氖?。但?qǐng)注意一個(gè)關(guān)鍵事實(shí)配對(duì)檢查這一層理想情況下必須巡檢所有候選對(duì)——因?yàn)槟銦o法預(yù)測(cè)哪一對(duì)會(huì)給出最大乘積除非已經(jīng)把它們?nèi)靠催^一遍。也就是說O(n2) 這個(gè)數(shù)量級(jí)對(duì)這類“找全局兩兩關(guān)系最大值”的問題來說基本是繞不開的下界。真正能優(yōu)化的點(diǎn)有兩個(gè)把單次檢查的成本從 O(L) 壓到 O(1)。這正是位掩碼的用武之地。通過排序和剪枝讓實(shí)際執(zhí)行的對(duì)數(shù)明顯少于 n2平均情況大幅提速雖然最壞情況仍然是 O(n2)。所以整道題的解題路線其實(shí)非常清晰先用二進(jìn)制特性把字符串變成整數(shù)再想辦法讓枚舉過程更聰明一點(diǎn)。接下來我們一步一步看。2. 二進(jìn)制特性把單詞壓縮成 26 位掩碼2.1 用 int 的 26 個(gè)位給字母“蓋章”為什么一說起“去重判斷”就想到位運(yùn)算因?yàn)樾懹⑽淖帜钢挥?26 個(gè)而一個(gè)int在 Java 里是 32 位在 Python 里雖然整數(shù)無限大但我們只關(guān)心低 26 位也完全夠用。于是可以建立一張固定映射字母a對(duì)應(yīng)第 0 位字母b對(duì)應(yīng)第 1 位字母c對(duì)應(yīng)第 2 位...字母z對(duì)應(yīng)第 25 位單詞里出現(xiàn)某個(gè)字母就把對(duì)應(yīng)位置 1沒出現(xiàn)就保持 0。這樣每個(gè)單詞都會(huì)被轉(zhuǎn)換成一個(gè)非負(fù)整數(shù)我習(xí)慣叫它“掩碼”或“簽名”。比如abc就會(huì)變成二進(jìn)制最低三位全是 1也就是數(shù)字 7abd是 0b1011也就是第三位和最低兩位是 1。構(gòu)造過程用位運(yùn)算寫核心就是兩行int mask 0; for (char c : word.toCharArray()) { mask | 1 (c - a); }拆開看是三件事1 (c - a)讓數(shù)字 1 左移若干位產(chǎn)生一個(gè)“只在某一位上是 1”的整數(shù)|是做按位或|等于把當(dāng)前所有已標(biāo)記的位和新位合并。每遍歷到一個(gè)字母就把白板上對(duì)應(yīng)的那一格點(diǎn)亮。重復(fù)字母不影響結(jié)果因?yàn)榘次换蛱烊痪哂袃绲刃浴＿@里可以打一個(gè)生活化比方掩碼就像一張 26 格的白板卡出現(xiàn)過的字母對(duì)應(yīng)的格子被貼上標(biāo)簽。判斷兩個(gè)單詞是否共用字母等價(jià)于把兩張白板卡疊在一起看看有沒有重疊的標(biāo)簽。而位與運(yùn)算做的正是這件事。2.2 掩碼和長(zhǎng)度必須分開記錄拿到掩碼之后馬上會(huì)遇到一個(gè)容易忽略的問題掩碼只是“字母存在性”的編碼它并不攜帶字符串的真實(shí)長(zhǎng)度信息。所以在預(yù)處理階段我習(xí)慣用兩個(gè)平行結(jié)構(gòu)分別保存int[] masks new int[n]; int[] lens new int[n];或者用二元組打包Java 里可以寫成int[n][2]Python 里就是list[tuple]。無論哪種原則只有一個(gè)掩碼和長(zhǎng)度必須同步保存、永不分離。為什么這么強(qiáng)調(diào)因?yàn)閍abb和ab的掩碼完全一樣都只有最低兩位是 1數(shù)值為 3但真實(shí)長(zhǎng)度分別是 4 和 2。如果后面只拿著掩碼去和別人比較算最終乘積時(shí)卻用“掩碼里的 1 的個(gè)數(shù)”當(dāng)長(zhǎng)度那就徹底跑偏了。Integer.bitCount(mask)只能告訴你這個(gè)單詞里有幾種不同字母而不是字符串有幾個(gè)字符。這一點(diǎn)我在后面第 4 節(jié)還會(huì)再拎出來當(dāng)反面教材。2.3 一次按位與完成集合交集判斷掩碼建好后判斷兩個(gè)單詞是否共享字母就只剩一條代碼if ((masks[i] masks[j]) 0) { // 無共同字母 } else { // 有共同字母跳過 }按位與的規(guī)則是“同一位都為 1 結(jié)果才為 1”。兩個(gè)掩碼如果在任何一位上同時(shí)為 1說明這兩個(gè)單詞都擁有那個(gè)字母結(jié)果那一位置 1整個(gè)整數(shù)不為 0。反之結(jié)果為零則代表沒有任何一位同時(shí)為 1兩詞自然沒有共同字母。這個(gè)轉(zhuǎn)化的威力在于我們把“字母集合交集是否為空”直接變成“兩個(gè)整數(shù)按位與是否為零”。判斷不再依賴字符串長(zhǎng)度也不再依賴字母順序時(shí)間復(fù)雜度從 O(L) 降到 O(1)。預(yù)處理階段雖然花掉一次 O(總字符數(shù)) 的代價(jià)去建掩碼但之后每次配對(duì)判斷都是 CPU 級(jí)常數(shù)操作。整道題的總復(fù)雜度就從 O(n2L) 好看地降到了 O(n2 總字符數(shù))。這也是標(biāo)題里“二進(jìn)制特性”這四個(gè)字的分量所在。3. 三個(gè)版本的實(shí)現(xiàn)與演進(jìn)3.1 第一版最樸素的位掩碼二重循環(huán)先給出最容易理解、也最容易驗(yàn)證正確性的版本。它不做任何排序和剪枝純粹靠位運(yùn)算把配對(duì)檢查變成 O(1)。Java 寫法class Solution { public int maxProduct(String[] words) { int n words.length; int[] masks new int[n]; int[] lens new int[n]; for (int i 0; i n; i) { int mask 0; for (char c : words[i].toCharArray()) { mask | 1 (c - a); } masks[i] mask; lens[i] words[i].length(); } int ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { if ((masks[i] masks[j]) 0) { ans Math.max(ans, lens[i] * lens[j]); } } } return ans; } }Python 版本長(zhǎng)得差不多class Solution: def maxProduct(self, words: List[str]) - int: masks [] lens [] for w in words: mask 0 for ch in w: mask | 1 (ord(ch) - 97) masks.append(mask) lens.append(len(w)) ans 0 n len(words) for i in range(n): for j in range(i 1, n): if (masks[i] masks[j]) 0: ans max(ans, lens[i] * lens[j]) return ans這一版的思路一句話就能概括先預(yù)處理再二重循環(huán)見縫插針地更新最大乘積。實(shí)測(cè)跑力扣50 萬次配對(duì)對(duì) n1000 來說是 10 的 6 次方量級(jí)每次配對(duì)只有一條位運(yùn)算整體毫秒級(jí)完成其實(shí)已經(jīng)能通過絕大多數(shù)測(cè)試數(shù)據(jù)。很多標(biāo)答比這版多做的其實(shí)是讓平均情況更快而不是推翻這套框架。3.2 第二版按長(zhǎng)度降序加剪枝第一版的問題在于它把每對(duì)都平等看待?？墒穷}目要的是最大乘積而且內(nèi)層循環(huán)里的lens[i] * lens[j]明顯受長(zhǎng)度影響長(zhǎng)度越大的配對(duì)越有機(jī)會(huì)打破當(dāng)前最優(yōu)。反過來說一旦某個(gè)配對(duì)就算乘積再大也比不過手里已有的ans那后面的全部配對(duì)就都沒必要看了。于是第二版的做法是先把所有單詞按長(zhǎng)度從大到小排序再套上二重循環(huán)。這里需要保證排序的原子性也就是長(zhǎng)度和掩碼必須作為一個(gè)整體跟著動(dòng)不能用兩個(gè)獨(dú)立數(shù)組去排。我習(xí)慣用二維數(shù)組或元組class Solution { public int maxProduct(String[] words) { int n words.length; int[][] items new int[n][2]; // items[i][0] len, items[i][1] mask for (int i 0; i n; i) { int mask 0; for (char c : words[i].toCharArray()) { mask | 1 (c - a); } items[i][0] words[i].length(); items[i][1] mask; } Arrays.sort(items, (a, b) - b[0] - a[0]); int ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { if (items[i][0] * items[j][0] ans) { break; } if ((items[i][1] items[j][1]) 0) { ans items[i][0] * items[j][0]; } } } return ans; } }Pythonclass Solution: def maxProduct(self, words: List[str]) - int: items [] for w in words: mask 0 for ch in w: mask | 1 (ord(ch) - 97) items.append((len(w), mask)) items.sort(keylambda x: -x[0]) # 只按長(zhǎng)度降序 ans 0 n len(items) for i in range(n): for j in range(i 1, n): len1, mask1 items[i] len2, mask2 items[j] if len1 * len2 ans: break if (mask1 mask2) 0: ans max(ans, len1 * len2) return ans這段代碼里最關(guān)鍵的是break的條件。因?yàn)橥鈱訂卧~長(zhǎng)度從大到小內(nèi)層單詞長(zhǎng)度也是從大到小所以對(duì)于固定的i隨著j往右移動(dòng)len2只降不升len1 * len2也一定單調(diào)遞減。一旦某個(gè)len1 * len2不大于ans后面所有j的乘積只會(huì)更小繼續(xù)枚舉純屬浪費(fèi)。這就是剪枝的數(shù)學(xué)依據(jù)。這個(gè)版本的正確性完全建立在“長(zhǎng)度降序”這個(gè)前提上。如果排序時(shí)只排了長(zhǎng)度沒有連帶掩碼一起交換那內(nèi)層循環(huán)遇到的長(zhǎng)度序列不再是降序break就會(huì)把潛在的正確答案也一起剪掉。這種錯(cuò)誤非常隱蔽我在初學(xué)時(shí)踩過一次后面第 4 節(jié)會(huì)專門展開。3.3 第三版相同掩碼只保留最長(zhǎng)單詞繼續(xù)觀察你還能發(fā)現(xiàn)一個(gè)更聰明的壓縮點(diǎn)如果兩個(gè)單詞的掩碼完全相同說明它們的字母集合一模一樣。對(duì)于外部任意一個(gè)單詞來說這兩個(gè)單詞要么都能配對(duì)要么都不能配對(duì)因?yàn)榕袛鄺l件只看掩碼這位“身份證”。既然它們?cè)谒信鋵?duì)場(chǎng)景下都是同一個(gè)命運(yùn)那我只需要留下其中長(zhǎng)度更長(zhǎng)的那一個(gè)因?yàn)樽詈笏愠朔e時(shí)長(zhǎng)度更大的那個(gè)一定帶來更大的數(shù)值。具體做法是用一張哈希表掩碼 - 該掩碼對(duì)應(yīng)的最大長(zhǎng)度。遍歷所有單詞算出掩碼后不斷更新這張表。class Solution { public int maxProduct(String[] words) { MapInteger, Integer map new HashMap(); for (String w : words) { int mask 0; for (char c : w.toCharArray()) { mask | 1 (c - a); } map.merge(mask, w.length(), Math::max); } Listint[] items new ArrayList(); for (Map.EntryInteger, Integer e : map.entrySet()) { items.add(new int[]{e.getValue(), e.getKey()}); // {最大長(zhǎng)度, 掩碼} } items.sort((a, b) - b[0] - a[0]); int ans 0; int m items.size(); for (int i 0; i m; i) { for (int j i 1; j m; j) { if (items.get(i)[0] * items.get(j)[0] ans) { break; } if ((items.get(i)[1] items.get(j)[1]) 0) { ans items.get(i)[0] * items.get(j)[0]; } } } return ans; } }Pythonclass Solution: def maxProduct(self, words: List[str]) - int: best {} for w in words: mask 0 for ch in w: mask | 1 (ord(ch) - 97) best[mask] max(best.get(mask, 0), len(w)) items sorted(best.items(), keylambda kv: -kv[1]) # (mask, maxLen)按 maxLen 降序 ans 0 m len(items) for i in range(m): mask1, len1 items[i] for j in range(i 1, m): mask2, len2 items[j] if len1 * len2 ans: break if (mask1 mask2) 0: ans max(ans, len1 * len2) return ans這里有個(gè)非常隱蔽但必須強(qiáng)調(diào)的細(xì)節(jié)去重后如果你直接用map.entrySet()的遍歷順序去套用第二版的break剪枝會(huì)出錯(cuò)。因?yàn)镠ashMap的迭代順序和長(zhǎng)度大小沒有任何關(guān)系內(nèi)層循環(huán)的乘積不是單調(diào)遞減的此時(shí)break就等于漏答案。正確做法是先把map里的條目按“最大長(zhǎng)度”降序排序再進(jìn)入雙層循環(huán)。第三版代碼里我特意先排序再循環(huán)就是吸取了這個(gè)教訓(xùn)。當(dāng)然如果你不想排序也可以那就老老實(shí)實(shí)跑 O(m2) 的全量枚舉其中 m 是去重后掩碼數(shù)量。大多數(shù)情況下 m 遠(yuǎn)小于原始 n所以即使不剪枝性能也夠看。3.4 復(fù)雜度對(duì)比與正確性論證把三版放在一起看方案預(yù)處理復(fù)雜度配對(duì)次數(shù)單次配對(duì)成本核心代價(jià)樸素位掩碼O(總字符數(shù))O(n2)O(1)代碼最簡(jiǎn)單排序剪枝O(總字符數(shù) n log n)平均遠(yuǎn)小于 n2最壞 O(n2)O(1)需要理解單調(diào)性掩碼去重O(總字符數(shù) m log m)O(m2)m ≤ nO(1)需要小心迭代順序其中總字符數(shù)就是所有字符串長(zhǎng)度之和一般遠(yuǎn)小于 n2可以忽略。三版的正確性都建立在一個(gè)共同邏輯鏈上掩碼構(gòu)造的正確性第 i 位是否為 1等價(jià)于字符串是否包含字母ai由構(gòu)造過程逐位保證配對(duì)判斷的正確性兩掩碼按位與為 0當(dāng)且僅當(dāng)不存在某一位同時(shí)為 1當(dāng)且僅當(dāng)不存在共同字母排序剪枝的正確性外層固定的情況下內(nèi)層乘積單調(diào)不增一旦不大于當(dāng)前最優(yōu)值后面不可能更好去重的正確性相同掩碼的外部可配對(duì)性完全相同只保留最長(zhǎng)長(zhǎng)度不會(huì)漏掉更大的乘積。每一條都環(huán)環(huán)相扣。如果你在面試中把這幾條順出來面試官基本不會(huì)再追問優(yōu)化細(xì)節(jié)。4. 常見問題與避坑實(shí)錄4.1 踩過的坑把 bitCount 當(dāng)成了字符串長(zhǎng)度我見過不少人在算完掩碼后順手用Integer.bitCount(mask)去代替長(zhǎng)度理由是“掩碼里每一位代表一個(gè)字母1 的個(gè)數(shù)不就是字母?jìng)€(gè)數(shù)嗎”。這句話聽著挺有理其實(shí)是把“字母種類數(shù)”和“字符串長(zhǎng)度”混為一談。aaa的掩碼只有最低一位是 1bitCount是 1但它的實(shí)際長(zhǎng)度是 3。如果題目算的是“種類乘積”那倒無所謂可它要的是length(words[i]) * length(words[j])這是原始字符串的長(zhǎng)度。掩碼從來沒有攜帶過重復(fù)計(jì)數(shù)信息它在構(gòu)造時(shí)就被設(shè)計(jì)為“存在性”而非“計(jì)數(shù)性”。所以無論在哪一版實(shí)現(xiàn)里長(zhǎng)度都必須單獨(dú)存、單獨(dú)取永遠(yuǎn)不要從掩碼反推長(zhǎng)度。4.2 踩過的坑排序剪枝時(shí)掩碼和長(zhǎng)度錯(cuò)位第二版和第三版都有排序操作這里是最容易出隱性 bug 的地方。比如有人先建了masks數(shù)組和lens數(shù)組然后只對(duì)lens做了降序排序masks還停留在原始順序。此時(shí)內(nèi)層循環(huán)看到的長(zhǎng)度雖然是降序但掩碼和長(zhǎng)度根本對(duì)不上號(hào)判斷條件里用到的mask是另一個(gè)單詞的配對(duì)的正確性直接被破壞。更隱蔽的是如果lens和masks都各自排序但排序規(guī)則不一致比如一個(gè)降序一個(gè)升序那也會(huì)得到亂序配對(duì)。我給出的方案是從一開始就把(len, mask)打包成同一個(gè)數(shù)組元素或元組保證排序過程中它倆永遠(yuǎn)不分離。這個(gè)習(xí)慣可以避免一整類難以定位的問題。還有一點(diǎn)剪枝的break只適用于內(nèi)層外兩層都以長(zhǎng)度降序?yàn)闇?zhǔn)的循環(huán)。如果你改用哈希表遍歷或者外層固定的是最短單詞千萬不能照搬這個(gè)條件。4.3 踩過的坑空串、單元素?cái)?shù)組與初始值題目允許words[i].length() 0嗎在力扣這道題的約束里是允許的。空串的掩碼是 0長(zhǎng)度是 0。空串與其他任何單詞做“無共同字母”的判斷時(shí)都是合規(guī)的因?yàn)榭占c任何集合的交集為空但它參與計(jì)算的乘積永遠(yuǎn)是 0所以不會(huì)對(duì)最大值產(chǎn)生影響。真正需要注意的反而是一開始初始化ans的方式。如果你把a(bǔ)ns初始化為負(fù)數(shù)或者Integer.MIN_VALUE那么空串配對(duì)產(chǎn)生的 0 反而可能被當(dāng)成一個(gè)“正確答案”返回題目實(shí)際期望在沒有合規(guī)配對(duì)時(shí)返回 0這樣就會(huì)出錯(cuò)。因此初始值請(qǐng)務(wù)必明確寫為 0。同理words只有一個(gè)元素時(shí)雙層循環(huán)壓根進(jìn)不去直接返回 0所有單詞都共享同一個(gè)字母a時(shí)任意兩個(gè)掩碼按位與非零同樣返回 0。這些都是合法結(jié)果不是異常。4.4 排查技巧對(duì)拍測(cè)試與問題速查表刷題時(shí)我最推薦的對(duì)拍式調(diào)試方法寫一個(gè)簡(jiǎn)單的暴力解法作為基準(zhǔn)再寫一個(gè)優(yōu)化解法然后用隨機(jī)數(shù)據(jù)反復(fù)對(duì)比兩個(gè)解法的輸出是否一致。生成幾個(gè)樣例、幾十組樣例、上千組樣例只要有一組不一致就立刻暴露優(yōu)化代碼里隱藏的錯(cuò)誤。這個(gè)方法在驗(yàn)證排序剪枝、去重邏輯時(shí)特別好用因?yàn)槭止?gòu)造的小數(shù)據(jù)往往曬不出問題隨機(jī)數(shù)據(jù)反而容易撞見邊界。下面是一張我總結(jié)的問題速查表現(xiàn)象可能原因解決辦法返回乘積比預(yù)期小排序剪枝時(shí)掩碼與長(zhǎng)度錯(cuò)位將(len, mask)打包排序結(jié)果在某些用例下偏小去重后未按長(zhǎng)度排序就用了break去重后再排序或在去重后用全量枚舉空串輸入時(shí)結(jié)果異常ans初始值不是 0初始化為 0超時(shí)沒用掩碼還在逐個(gè)字符掃描預(yù)處理掩碼用按位與判斷5. 一點(diǎn)延伸位掩碼思想還能解決什么問題這道題的核心是把“有限集合的存在性判斷”壓縮成整數(shù)位運(yùn)算這個(gè)套路在力扣上遠(yuǎn)不止出現(xiàn)在 318 題。最經(jīng)典的相關(guān)應(yīng)用是字母異位詞分組如果把每個(gè)字符串都轉(zhuǎn)成一個(gè) 26 位掩碼再對(duì)相同掩碼分組就能在近似線性時(shí)間內(nèi)完成分組而不需要兩兩比較是否異位。另一個(gè)典型的場(chǎng)景是“判斷子集關(guān)系”如果想知道一個(gè)單詞是不是另一個(gè)單詞的“字母子集”可以用(maskA maskB) maskA來判斷這恰好與本題判斷“是否完全不相交”互為鏡像。此外狀態(tài)壓縮動(dòng)態(tài)規(guī)劃里到處都是位掩碼的身影枚舉子集、判斷某個(gè)狀態(tài)是否合法、合并狀態(tài)轉(zhuǎn)移本質(zhì)上都是在用整數(shù)上的位運(yùn)算來描述“哪些元素已經(jīng)被選過”這件事。我經(jīng)常跟同事開玩笑說位掩碼是力扣給刷題人的一份禮物它把所有關(guān)于“集合邊界”的思考都?jí)嚎s成一個(gè)整數(shù)上的常數(shù)時(shí)間操作。以后再遇到“字母不超過 26 個(gè)”“元素不超過 32 個(gè)”這類題目第一反應(yīng)就應(yīng)該是——能不能用位做記號(hào)這類題目見得多了你自然會(huì)形成一種“看見有限集合就想按位編碼”的條件反射。最后分享一個(gè)我在實(shí)際刷題中的體會(huì)與其死記這道題的代碼不如把“為什么可以用位運(yùn)算”這個(gè)問題徹底想透。一旦想透了你會(huì)發(fā)現(xiàn)它只是位掩碼思想的一個(gè)小應(yīng)用后面再碰到類似問題代碼幾乎可以順手拈來。勤寫對(duì)拍、勤分析復(fù)雜度比我當(dāng)初一道題背十遍要高效得多。