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