Python에서 모든 1을 함께 그룹화하는 데 필요한 최소 스왑을 찾는 프로그램

<시간/>

이진 문자열이 있다고 가정하고 문자열의 어느 위치에서든 모든 1을 그룹화하는 데 필요한 최소 스왑 수를 찾아야 합니다. 따라서 입력이 "10101001101"과 같으면 출력은 3이 되며 가능한 솔루션은 "00000111111"입니다.

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

data :=주어진 문자열의 비트 목록
하나를 설정하십시오 :=0, n:=데이터 배열의 길이
크기가 n인 배열 합계를 만들고 이를 0으로 채우고 summ[0] :=data[0]
로 설정합니다.
하나 :=하나 + 데이터[0]
범위 1에서 n – 1까지의 i에 대해
- 합계[i] :=합계[i - 1] + 데이터[i]
- 하나 :=하나 + 데이터[i]
as :=하나
왼쪽 :=0, 오른쪽 :=1 – 1
오른쪽 동안
- 왼쪽이 0이면 temp :=summ[right], 그렇지 않으면 temp :=summ[right] –
- 합[왼쪽 - 1]
- ans :=ans의 최소값, 1 – temp
- 좌우 1씩 증가
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution(object):
   def solve(self, data):
      data = list(map(int, list(data)))
      one = 0
      n = len(data)
      summ=[0 for i in range(n)]
      summ[0] = data[0]
      one += data[0]
      for i in range(1,n):
         summ[i] += summ[i-1]+data[i]
         one += data[i]
      ans = one
      left = 0
      right = one-1
      while right <n:
         if left == 0:
            temp = summ[right]
         else:
            temp = summ[right] - summ[left-1]
         ans = min(ans,one-temp)
         right+=1
         left+=1
         return ans
ob = Solution()
print(ob.solve("10101001101"))

입력

"10101001101"