0과 1을 저장하는 nums라는 숫자 목록이 있다고 가정합니다. 또 다른 값 k가 있습니다.
이제 모든 1이 0이 되고 모든 0이 1이 되도록 길이가 k인 하위 목록을 뒤집는 작업이 있다고 가정합니다. 숫자를 모두 1에서 0으로 변경하는 데 필요한 최소 연산 수를 찾아야 합니다. 변경할 수 없으면 -1을 반환합니다.
따라서 입력이 nums =[1,1,1,0,0,1,1,1], k =3과 같으면 출력은 2가 됩니다. 처음 세 숫자를 0으로 뒤집은 다음 마지막 세 숫자를 0으로 뒤집습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=숫자 크기
-
res :=0, 뒤집힌 :=0
-
to_conv :=크기가 n이고 0으로 채워진 목록
-
0에서 n 사이의 i에 대해 수행
-
뒤집힌 :=뒤집힌 XOR to_conv[i]
-
cur :=숫자[i]
-
cur :=cur XOR 뒤집힘
-
cur가 1과 같으면
-
뒤집힌 :=뒤집힌 XOR 1
-
해상도 :=해상도 + 1
-
i + k - 1>=n이면
-
반환 -1
-
-
i + k
-
to_conv[i + k] :=1
-
-
-
-
반환 해상도
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution: def solve(self, nums, k): n = len(nums) res = 0 flipped = 0 to_conv = [0] * n for i in range(n): flipped ^= to_conv[i] cur = nums[i] cur ^= flipped if cur == 1: flipped ^= 1 res += 1 if i + k - 1 >= n: return -1 if i + k < n: to_conv[i + k] = 1 return res ob = Solution() nums = [1,1,1,0,0,1,1,1] k = 3 print(ob.solve(nums, k))
입력
[1,1,1,0,0,1,1,1], 3
출력
2