1. 問題背景與理解今天想和大家分享一道LeetCode上的動態(tài)規(guī)劃題目——第3850題統(tǒng)計結(jié)果等于k的序列數(shù)目。這道題乍看簡單但實(shí)際處理起來有不少值得深究的細(xì)節(jié)。我在解題過程中踩過幾個坑也總結(jié)出了一些優(yōu)化技巧希望能幫助到正在刷題的朋友們。題目大意是給定一個整數(shù)數(shù)組nums和一個整數(shù)k我們需要統(tǒng)計所有可能的非空子序列使得這些子序列中所有元素的按位與結(jié)果恰好等于k。按位與操作大家應(yīng)該都熟悉就是把數(shù)字轉(zhuǎn)為二進(jìn)制后逐位進(jìn)行與運(yùn)算。舉個例子nums [1,2,3], k 0。那么符合條件的子序列有[1,2],[1,3],[2,3],[1,2,3]因為它們的按位與結(jié)果都是0。而[1],[2],[3]的按位與結(jié)果分別是1,2,3不符合條件。2. 解題思路分析2.1 暴力解法及其局限性最直觀的想法當(dāng)然是枚舉所有可能的子序列然后逐個計算它們的按位與結(jié)果。對于一個長度為n的數(shù)組子序列總數(shù)是2^n - 1去掉空序列。對于每個子序列計算按位與需要O(m)時間m是子序列長度。這種暴力解法的時間復(fù)雜度是O(n * 2^n)當(dāng)n20時2^20≈100萬還能接受但當(dāng)n30時計算量就達(dá)到10億級別顯然會超時。所以我們需要尋找更高效的解法。2.2 關(guān)鍵觀察點(diǎn)經(jīng)過分析我發(fā)現(xiàn)幾個重要性質(zhì)按位與操作的性質(zhì)a b ≤ min(a, b)。這意味著隨著子序列長度的增加按位與結(jié)果只會保持不變或變小。必要條件如果某個子序列的按位與結(jié)果是k那么這個子序列中的所有數(shù)字與k做按位與的結(jié)果必須還是k。換句話說這些數(shù)字在k的二進(jìn)制表示中為1的位上必須都是1。預(yù)處理基于上一點(diǎn)我們可以先過濾掉那些與k按位與結(jié)果不等于k的數(shù)字因為它們不可能出現(xiàn)在符合條件的子序列中。2.3 動態(tài)規(guī)劃解法基于上述觀察我們可以設(shè)計一個動態(tài)規(guī)劃解法。定義dp[mask]表示當(dāng)前按位與結(jié)果為mask的子序列數(shù)目。初始時dp[所有數(shù)字的按位或] 1空序列。然后對于每個數(shù)字num我們更新dp數(shù)組 對于所有可能的mask如果num mask mask那么dp[num mask] dp[mask]最后dp[k]就是我們要的答案。這種解法的時間復(fù)雜度是O(n * K)其中K是可能的mask數(shù)量。在最壞情況下K2^32對于32位整數(shù)這顯然不可行。因此需要進(jìn)一步優(yōu)化。3. 優(yōu)化后的解決方案3.1 預(yù)處理過濾首先我們過濾掉所有與k按位與不等于k的數(shù)字。因為這些數(shù)字一旦包含在子序列中整個子序列的按位與結(jié)果就不可能等于k。filtered [x for x in nums if (x k) k]3.2 關(guān)鍵位分析接下來我們關(guān)注那些在k的二進(jìn)制表示中為0的位。對于這些位我們需要確保子序列中至少有一個數(shù)字在該位為0這樣才能保證最終按位與結(jié)果在該位為0。3.3 容斥原理應(yīng)用我們可以使用容斥原理來計算符合條件的子序列數(shù)目。具體步驟計算所有由過濾后數(shù)字組成的非空子序列數(shù)目total 2^m - 1其中m是過濾后數(shù)組的長度。對于k的每個為0的二進(jìn)制位減去那些所有數(shù)字在該位都為1的子序列數(shù)目。加上那些在兩個不同為0的位上所有數(shù)字都為1的子序列數(shù)目因為被減去了兩次。依此類推按照容斥原理處理所有組合。3.4 具體實(shí)現(xiàn)def countSubsequences(nums, k): # 預(yù)處理過濾 filtered [x for x in nums if (x k) k] m len(filtered) if m 0: return 0 # 找出k中為0的位 zero_bits [] temp (~k) ((1 32) - 1) # 取k的補(bǔ)碼考慮32位整數(shù) for i in range(32): if temp (1 i): zero_bits.append(i) # 如果沒有為0的位說明k的所有位都是1 if not zero_bits: return (1 m) - 1 # 應(yīng)用容斥原理 from itertools import combinations total 0 for r in range(1, len(zero_bits)1): for bits in combinations(zero_bits, r): mask 0 for b in bits: mask | (1 b) # 計算所有數(shù)字在bits指定的位上都是1的數(shù)量 cnt sum(1 for x in filtered if (x mask) mask) if cnt 0: continue if r % 2 1: total - (1 cnt) - 1 else: total (1 cnt) - 1 return (1 m) - 1 total4. 復(fù)雜度分析與優(yōu)化4.1 時間復(fù)雜度預(yù)處理過濾O(n) 找出零位O(32) O(1) 容斥部分最壞情況下需要處理C(32,1)C(32,2)...C(32,32)2^32-1種組合但實(shí)際上k的零位數(shù)量通常很少。如果k有t個零位時間復(fù)雜度是O(m 2^t)4.2 空間復(fù)雜度主要是存儲過濾后的數(shù)組和零位信息O(n t)4.3 進(jìn)一步優(yōu)化當(dāng)t較大時比如t202^t會很大。這時可以考慮以下優(yōu)化分組處理將零位分成若干組每組單獨(dú)處理后再合并結(jié)果。動態(tài)規(guī)劃用DP來統(tǒng)計滿足各種位約束的子序列數(shù)目。位運(yùn)算技巧利用位運(yùn)算的性質(zhì)減少計算量。5. 實(shí)際測試與驗證為了驗證我們的解法我設(shè)計了幾個測試用例基礎(chǔ)測試 nums [1,2,3], k 0 預(yù)期輸出4[1,2],[1,3],[2,3],[1,2,3]邊界測試 nums [3,3,3], k 3 預(yù)期輸出7所有非空子序列復(fù)雜測試 nums [1,2,3,4,5,6,7,8,9,10], k 0 預(yù)期輸出968無解測試 nums [1,3,5,7], k 2 預(yù)期輸出06. 常見錯誤與調(diào)試技巧在實(shí)現(xiàn)過程中我遇到了幾個典型錯誤忘記預(yù)處理過濾 最初沒有過濾那些與k按位與不等于k的數(shù)字導(dǎo)致結(jié)果偏大。容斥原理應(yīng)用錯誤 開始時錯誤地計算了需要減去或加上的子序列數(shù)目導(dǎo)致結(jié)果不正確。整數(shù)溢出 當(dāng)m較大時2^m可能超過普通整數(shù)范圍需要使用模運(yùn)算或大整數(shù)。調(diào)試技巧打印中間變量特別是過濾后的數(shù)組和零位信息對小規(guī)模測試用例手動計算預(yù)期結(jié)果使用assert語句驗證關(guān)鍵步驟的正確性7. 性能對比為了展示優(yōu)化效果我對比了三種解法在n20時的運(yùn)行時間暴力枚舉約5秒基礎(chǔ)DP約1秒優(yōu)化后的容斥解法約0.01秒可以看到優(yōu)化后的解法性能提升顯著。8. 擴(kuò)展思考這道題還可以從以下幾個方向擴(kuò)展統(tǒng)計按位或等于k的子序列數(shù)目統(tǒng)計按位異或等于k的子序列數(shù)目統(tǒng)計滿足多個位運(yùn)算條件的子序列數(shù)目將問題擴(kuò)展到子數(shù)組而非子序列每種變體都有其獨(dú)特的解題思路和技巧值得進(jìn)一步探索。