Python에서 교대 값을 갖는 데 필요한 최소 뒤집기 횟수를 찾는 프로그램

<시간/>

이진 문자열 s가 있다고 가정합니다. 이제 접두사를 가져와서 뒤로 이동할 수 있다고 가정합니다. 그런 다음, 동일한 값의 연속 문자가 없도록 뒤집어야 하는 최소 문자 수를 찾으십시오.

따라서 입력이 s ="10010101111"과 같으면 출력은 2가 됩니다. 접두사 "10"을 사용할 수 있으므로 뒤로 이동하여 문자열이 "01010111110"이 되도록 한 다음 세 번째 및 다섯 번째 비트를 오른쪽에서 0으로 뒤집습니다. ("01010101010").

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

as :=S
의 크기
N :=S
의 크기
s :=0
0 ~ 2 * N 범위의 i에 대해 수행
- s :=s + (S[i mod N] XOR (i AND 1))
  의 정수
- i>=N - 1이면
  - ans :=ans, s 및 N - s의 최소값
  - s :=s - (S[(i -(N - 1)) mod N]) XOR ((i - (N - 1)) AND 1)
    의 정수
반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, S):
      ans = N = len(S)
      s = 0
      for i in range(2 * N):
         s += int(S[i % N]) ^ (i & 1)
         if i >= N - 1:
            ans = min(ans, s, N - s)
            s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
      return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))

입력

"10010101111"