nums라는 배열과 다른 값 k가 있다고 가정합니다. 세그먼트 [left, right](left <=right)의 XOR은 인덱스가 왼쪽과 오른쪽(포함) 사이에 있는 모든 요소의 XOR입니다.
크기가 k인 모든 세그먼트의 XOR이 0과 같도록 배열에서 변경할 요소의 최소 수를 찾아야 합니다.
따라서 입력이 nums =[3,4,5,2,1,7,3,4,7], k =3과 같으면 인덱스 2, 3에서 요소를 수정할 수 있으므로 출력은 3이 됩니다. 4 배열을 [3,4,7,3,4,7,3,4,7]로 만듭니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
제한:=1024
-
temp :=크기가 LIMIT x k인 배열을 만들고 0으로 채웁니다.
-
숫자로 된 각 인덱스 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
-
-
숫자 반환 크기 - 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