1. 題目背景與核心需求今天我們來拆解LeetCode第3314題構(gòu)造最小位運(yùn)算數(shù)組 I。這是一道典型的位運(yùn)算與數(shù)組構(gòu)造結(jié)合的題目題目要求我們根據(jù)給定的整數(shù)數(shù)組構(gòu)造一個(gè)新的數(shù)組其中每個(gè)元素滿足特定的位運(yùn)算條件。題目描述通常如下給定一個(gè)整數(shù)數(shù)組nums構(gòu)造一個(gè)新數(shù)組answer使得answer[i]等于nums中除nums[i]之外所有元素的位運(yùn)算AND結(jié)果。位運(yùn)算AND操作是將兩個(gè)數(shù)的二進(jìn)制表示逐位進(jìn)行與運(yùn)算。注意位運(yùn)算AND的特性是任何數(shù)與0進(jìn)行AND操作結(jié)果都是0而與全1數(shù)進(jìn)行AND操作則保留原數(shù)。這個(gè)特性在解題中非常關(guān)鍵。這道題看似簡單但考察了幾個(gè)重要知識點(diǎn)位運(yùn)算的基本原理與應(yīng)用數(shù)組遍歷與元素操作算法的時(shí)間復(fù)雜度優(yōu)化思路2. 暴力解法分析與實(shí)現(xiàn)2.1 最直觀的暴力解法對于初學(xué)者來說最直接的思路是對于每個(gè)元素nums[i]遍歷數(shù)組中所有其他元素進(jìn)行位運(yùn)算AND操作。這種方法雖然直觀但時(shí)間復(fù)雜度為O(n2)在數(shù)據(jù)量較大時(shí)性能會很差。def constructArray(nums): n len(nums) answer [0] * n for i in range(n): temp ~0 # 初始化為全1 for j in range(n): if j ! i: temp nums[j] answer[i] temp return answer這種解法的問題在于對于每個(gè)元素都要遍歷整個(gè)數(shù)組進(jìn)行了大量重復(fù)計(jì)算沒有利用到位運(yùn)算的特性進(jìn)行優(yōu)化2.2 暴力解法的局限性當(dāng)數(shù)組長度為n時(shí)暴力解法需要進(jìn)行n*(n-1)次位運(yùn)算操作。對于LeetCode的測試用例來說當(dāng)n達(dá)到10^5量級時(shí)這種解法肯定會超時(shí)。因此我們需要尋找更優(yōu)化的解決方案。3. 優(yōu)化思路與數(shù)學(xué)原理3.1 位運(yùn)算的數(shù)學(xué)特性位運(yùn)算AND有一個(gè)重要特性一系列數(shù)的AND結(jié)果等于這些數(shù)在每一位上共同為1的位的組合。也就是說對于最終結(jié)果的每一位只有當(dāng)所有參與運(yùn)算的數(shù)在該位都為1時(shí)結(jié)果位才為1只要有一個(gè)數(shù)在該位為0結(jié)果位就為0基于這個(gè)特性我們可以得出一個(gè)重要結(jié)論整個(gè)數(shù)組的AND結(jié)果等于所有元素的AND結(jié)果。而題目要求的answer[i]其實(shí)就是整個(gè)數(shù)組的AND結(jié)果再與nums[i]的逆進(jìn)行AND操作。3.2 前綴與后綴數(shù)組優(yōu)化我們可以使用前綴和后綴數(shù)組的技術(shù)來優(yōu)化計(jì)算預(yù)先計(jì)算從左到右的前綴AND數(shù)組預(yù)先計(jì)算從右到左的后綴AND數(shù)組對于每個(gè)元素nums[i]answer[i] prefix[i-1] suffix[i1]這種方法將時(shí)間復(fù)雜度降低到了O(n)只需要三次遍歷數(shù)組一次計(jì)算前綴數(shù)組一次計(jì)算后綴數(shù)組一次計(jì)算最終結(jié)果def constructArray(nums): n len(nums) prefix [0] * n suffix [0] * n answer [0] * n prefix[0] nums[0] for i in range(1, n): prefix[i] prefix[i-1] nums[i] suffix[-1] nums[-1] for i in range(n-2, -1, -1): suffix[i] suffix[i1] nums[i] answer[0] suffix[1] answer[-1] prefix[-2] for i in range(1, n-1): answer[i] prefix[i-1] suffix[i1] return answer4. 空間復(fù)雜度優(yōu)化4.1 進(jìn)一步優(yōu)化思路雖然前綴后綴數(shù)組的方法已經(jīng)很高效但我們還可以進(jìn)一步優(yōu)化空間復(fù)雜度。觀察到在計(jì)算answer數(shù)組時(shí)我們實(shí)際上只需要知道prefix[i-1]和suffix[i1]而不需要存儲整個(gè)前綴和后綴數(shù)組。因此我們可以先計(jì)算整個(gè)數(shù)組的AND結(jié)果total_and然后對于每個(gè)nums[i]answer[i] total_and (~nums[i])不過這種方法有一個(gè)前提條件只有當(dāng)nums[i]在total_and的基礎(chǔ)上沒有貢獻(xiàn)額外的0位時(shí)才成立。在實(shí)際應(yīng)用中這種方法可能不總是適用。4.2 最優(yōu)解法實(shí)現(xiàn)經(jīng)過分析我們發(fā)現(xiàn)最可靠的還是前綴后綴數(shù)組的方法。下面是經(jīng)過空間優(yōu)化的實(shí)現(xiàn)def constructArray(nums): n len(nums) answer [0] * n # 先計(jì)算后綴數(shù)組 answer[-1] nums[-1] for i in range(n-2, -1, -1): answer[i] answer[i1] nums[i] # 再計(jì)算前綴并同時(shí)計(jì)算最終結(jié)果 prefix nums[0] final_answer [0] * n final_answer[0] answer[1] for i in range(1, n-1): final_answer[i] prefix answer[i1] prefix nums[i] final_answer[-1] prefix return final_answer這種方法只需要O(1)的額外空間除了輸出數(shù)組達(dá)到了最優(yōu)的空間復(fù)雜度。5. 邊界條件與測試用例5.1 常見邊界情況在實(shí)現(xiàn)這類算法時(shí)需要特別注意以下邊界條件空數(shù)組輸入雖然題目保證非空單元素?cái)?shù)組全0數(shù)組全1數(shù)組大數(shù)數(shù)組接近整數(shù)最大值混合正負(fù)數(shù)數(shù)組5.2 測試用例設(shè)計(jì)好的測試用例應(yīng)該包含test_cases [ ([1,2,3,4], [0,1,0,0]), # 常規(guī)情況 ([0,0,0,0], [0,0,0,0]), # 全0 ([1,1,1,1], [1,1,1,1]), # 全1 ([1,3,5,7], [1,1,1,1]), # 奇數(shù)特例 ([2,4,8,16], [0,0,0,0]), # 不同位 ([1], [0]), # 單元素 ([255,255,255], [255,255,255]) # 全255 ]6. 復(fù)雜度分析與比較6.1 時(shí)間復(fù)雜度對比暴力解法O(n2)對于每個(gè)元素遍歷其他所有元素不適合大規(guī)模數(shù)據(jù)前綴后綴數(shù)組O(n)三次線性遍歷適合大規(guī)模數(shù)據(jù)空間優(yōu)化版O(n)兩次線性遍歷同樣適合大規(guī)模數(shù)據(jù)6.2 空間復(fù)雜度對比暴力解法O(1)不包括輸出數(shù)組只需要常數(shù)空間但時(shí)間復(fù)雜度太高前綴后綴數(shù)組O(n)需要存儲前綴和后綴數(shù)組空間開銷較大空間優(yōu)化版O(1)不包括輸出數(shù)組最優(yōu)的空間復(fù)雜度只需要常數(shù)額外空間7. 實(shí)際應(yīng)用與擴(kuò)展7.1 位運(yùn)算的實(shí)際應(yīng)用場景位運(yùn)算在計(jì)算機(jī)科學(xué)中有廣泛應(yīng)用權(quán)限控制系統(tǒng)如Linux文件權(quán)限數(shù)據(jù)壓縮與編碼哈希算法圖形處理如像素操作網(wǎng)絡(luò)協(xié)議如IP地址處理7.2 題目擴(kuò)展思考這道題可以有多種變體使用OR運(yùn)算代替AND運(yùn)算使用XOR運(yùn)算組合多種位運(yùn)算三維數(shù)組的位運(yùn)算處理流式數(shù)據(jù)的位運(yùn)算處理例如如果題目改為OR運(yùn)算我們可以使用類似的優(yōu)化思路但需要注意OR運(yùn)算的特性任何數(shù)與1進(jìn)行OR操作結(jié)果都是1。8. 刷題建議與技巧8.1 位運(yùn)算常見技巧判斷奇偶x 1取最低位的1x -x將最低位的1變?yōu)?x (x-1)判斷是否為2的冪x (x-1) 0交換兩個(gè)數(shù)a ^ b; b ^ a; a ^ b;8.2 LeetCode刷題策略先理解題目要求明確輸入輸出思考暴力解法確保理解題意分析時(shí)間/空間復(fù)雜度尋找優(yōu)化點(diǎn)考慮數(shù)據(jù)結(jié)構(gòu)和算法技巧的應(yīng)用編寫代碼并測試邊界條件反思是否有更優(yōu)解對于位運(yùn)算題目特別要注意二進(jìn)制表示的特性位運(yùn)算的數(shù)學(xué)性質(zhì)常見位運(yùn)算技巧的應(yīng)用場景9. 從簡單題到難題的過渡這道題目標(biāo)為I意味著可能有更復(fù)雜的II版本。在實(shí)際刷題中我們應(yīng)該先掌握基礎(chǔ)解法理解優(yōu)化思路思考如何應(yīng)對更大規(guī)模數(shù)據(jù)考慮問題的各種變體將解法抽象成通用模式對于后續(xù)的II版本可能會涉及更大的數(shù)據(jù)規(guī)模更復(fù)雜的位運(yùn)算組合動態(tài)數(shù)據(jù)更新多維數(shù)組處理分布式計(jì)算環(huán)境下的處理10. 個(gè)人實(shí)戰(zhàn)經(jīng)驗(yàn)分享在實(shí)際解決這類問題時(shí)我總結(jié)了一些經(jīng)驗(yàn)位運(yùn)算題目常常有靈光一現(xiàn)的特性需要多練習(xí)培養(yǎng)直覺畫二進(jìn)制表示圖有助于理解問題小規(guī)模手動計(jì)算可以幫助驗(yàn)證思路注意整數(shù)溢出問題Python中不用擔(dān)心但其他語言需要考慮位運(yùn)算優(yōu)先級較低多用括號明確運(yùn)算順序一個(gè)常見的坑是忽略位運(yùn)算的優(yōu)先級。例如# 錯(cuò)誤寫法 if x 1 0: # 實(shí)際是 x (1 0) pass # 正確寫法 if (x 1) 0: pass另一個(gè)實(shí)用技巧是使用掩碼來操作特定位# 設(shè)置第k位為1 def set_bit(x, k): return x | (1 k) # 清除第k位 def clear_bit(x, k): return x ~(1 k) # 切換第k位 def toggle_bit(x, k): return x ^ (1 k)最后對于LeetCode刷題建議建立一個(gè)位運(yùn)算工具函數(shù)庫把常用操作封裝起來可以大大提高解題效率。