สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และอีกค่าหนึ่งคือ k XOR ของเซ็กเมนต์ [left, right] (left <=right) คือ XOR ขององค์ประกอบทั้งหมดที่มีดัชนีอยู่ระหว่างซ้ายและขวา (รวม)
เราต้องหาจำนวนองค์ประกอบขั้นต่ำที่จะเปลี่ยนในอาร์เรย์เพื่อให้ XOR ของทุกส่วนของขนาด 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
-
สำหรับแต่ละดัชนี i และค่า x เป็น nums ทำ
-
อุณหภูมิ[i mod k, x] :=อุณหภูมิ[i mod k, x] + 1
-
-
dp :=อาร์เรย์ขนาด LIMIT และเติมด้วย -2000
-
dp[0] :=0
-
สำหรับแต่ละแถวในอุณหภูมิ ให้ทำ
-
maxprev :=สูงสุดของ dp
-
new_dp :=อาร์เรย์ขนาด LIMIT และเติม maxprev
-
สำหรับแต่ละดัชนี i และค่า cnt แถว ทำ
-
ถ้า cnt> 0 แล้ว
-
สำหรับแต่ละดัชนี j และค่าก่อนหน้าใน dp ทำ
-
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
