資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：使所有片段的異或結果為零
假設我們有一個名為 nums 的陣列和另一個值 k。一個片段 [left, right]（left <= right）的異或結果是指所有索引在 left 和 right 之間（包括 left 和 right）的元素的異或結果。
我們需要找到更改陣列中元素的最小數量，以使所有大小為 k 的片段的異或結果都等於零。
因此，如果輸入類似於 nums = [3,4,5,2,1,7,3,4,7]，k = 3，則輸出將為 3，因為我們可以修改索引為 2、3、4 的元素，使陣列變為 [3,4,7,3,4,7,3,4,7]。
為了解決這個問題，我們將遵循以下步驟：
LIMIT := 1024
temp := 建立一個大小為 LIMIT x k 的陣列，並用 0 填充
對於 nums 中的每個索引 i 和值 x，執行以下操作：
temp[i mod k, x] := temp[i mod k, x] + 1
dp := 建立一個大小為 LIMIT 的陣列，並用 -2000 填充
dp[0] := 0
對於 temp 中的每一行，執行以下操作：
maxprev := dp 的最大值
new_dp := 建立一個大小為 LIMIT 的陣列，並用 maxprev 填充
對於每一行中的每個索引 i 和值 cnt，執行以下操作：
如果 cnt > 0，則執行以下操作：
對於 dp 中的每個索引 j 和值 prev，執行以下操作：
new_dp[i XOR j] := new_dp[i XOR j] 和 prev+cnt 的最大值
dp := new_dp
返回 nums 的大小 - new_dp[0]
示例
讓我們看看以下實現以更好地理解
def solve(nums, k):
LIMIT = 2**10
temp = [[0 for _ in range(LIMIT)] for _ in range(k)]
for i,x in enumerate(nums):
temp[i%k][x] += 1
dp = [-2000 for _ in range(LIMIT)]
dp[0] = 0
for row in temp:
maxprev = max(dp)
new_dp = [maxprev for _ in range(LIMIT)]
for i,cnt in enumerate(row):
if cnt > 0:
for j,prev in enumerate(dp):
new_dp[i^j] = max(new_dp[i^j], prev+cnt)
dp = new_dp
return len(nums) - new_dp[0]
nums = [3,4,5,2,1,7,3,4,7]
k = 3
print(solve(nums, k))輸入
[3,4,5,2,1,7,3,4,7], 3
輸出
-9
更新於： 2021年10月8日
250 次瀏覽
廣告