Giả sử chúng ta có một mảng được gọi là nums và một giá trị khác k. XOR của phân đoạn [left, right] (left <=right) là XOR của tất cả các phần tử có chỉ số nằm giữa trái và phải (bao gồm).
Chúng ta phải tìm số phần tử tối thiểu để thay đổi trong mảng sao cho XOR của tất cả các phân đoạn có kích thước k bằng không.
Vì vậy, nếu đầu vào giống như nums =[3,4,5,2,1,7,3,4,7], k =3, thì đầu ra sẽ là 3 vì chúng ta có thể sửa đổi các phần tử ở chỉ số 2, 3, 4 để tạo mảng [3,4,7,3,4,7,3,4,7].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
LIMIT:=1024
-
temp:=tạo một mảng có kích thước là LIMIT x k và điền bằng 0
-
đối với mỗi chỉ số i và giá trị x tính bằng nums, thực hiện
-
temp [i mod k, x]:=temp [i mod k, x] + 1
-
-
dp:=một mảng có kích thước LIMIT và điền bằng -2000
-
dp [0]:=0
-
đối với mỗi hàng ở chế độ tạm thời, hãy thực hiện
-
maxprev:=tối đa là dp
-
new_dp:=một mảng có kích thước LIMIT và lấp đầy bằng maxprev
-
đối với mỗi chỉ mục i và giá trị hàng cnt, thực hiện
-
nếu cnt> 0, thì
-
đối với mỗi chỉ số j và giá trị trước trong dp, thực hiện
-
new_dp [i XOR j]:=tối đa new_dp [i XOR j] và pres + cnt
-
-
-
-
dp:=new_dp
-
-
trả về kích thước của nums - new_dp [0]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
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)) Đầu vào
[3,4,5,2,1,7,3,4,7], 3
Đầu ra
-9