하나의 이진 배열 num과 값 k가 있다고 가정합니다. 한 번에 두 개의 인접한 인덱스를 선택하고 값을 바꿀 수 있습니다. 숫자가 k 연속 1이 되도록 필요한 최소 이동 횟수를 찾아야 합니다.
따라서 입력이 nums =[1,0,0,1,0,1,0,1], k =3과 같으면 출력은 2가 됩니다. 한 번의 스왑으로 [1,0]에서 배열을 만들 수 있기 때문입니다. ,0,1,0,1,0,1] ~ [1,0,0,0,1,1,0,1] 다음 [1,0,0,0,1,1,1,0] .
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
j :=0
-
값 :=0
-
답변 :=999999
-
loc :=새 목록
-
각 인덱스 i 및 숫자 x 값에 대해 수행
-
x가 0이 아니면
-
loc의 끝에 i 삽입
-
m :=(j + 위치 크기 - 1) /2의 몫
-
val :=val + loc[-1] - loc[m] - (loc -j의 크기)/2
의 몫 -
loc의 길이 - j> k인 경우
-
m :=(j + 위치의 크기) /2의 몫
-
val :=val - loc[m] - loc[j] - (loc -j의 크기)/2
의 몫 -
j :=j + 1
-
-
loc -j의 크기가 k와 같으면
-
ans :=ans와 val의 최소값
-
-
-
-
반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(nums, k):
j = val = 0
ans = 999999
loc = []
for i, x in enumerate(nums):
if x:
loc.append(i)
m = (j + len(loc) - 1)//2
val += loc[-1] - loc[m] - (len(loc)-j)//2
if len(loc) - j > k:
m = (j + len(loc))//2
val -= loc[m] - loc[j] - (len(loc)-j)//2
j += 1
if len(loc)-j == k:
ans = min(ans, val)
return ans
nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k)) 입력
[1,0,0,1,0,1,0,1], 3
출력
2