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