이진 문자열에서 1 앞에 0을 모두 배치하는 데 필요한 최소 이동 횟수

문제 설명

이진 문자열 str이 주어지고 1 앞에 0을 모두 넣을 수 있도록 문자열에서 최소 문자 수를 제거하라는 요청을 받습니다.

예

들어가세요

으아아아

출력

으아아아

지침

여기서 두 가지 방법으로 출력 3을 얻을 수 있습니다.

문자열에서 arr[2], arr[3] 및 arr[5] 또는 arr[4], arr[6] 및 arr[7]을 제거할 수 있습니다.

들어가세요

으아아아

출력

으아아아

지침

arr[4]와 arr[6]을 제거하고 1 앞에 0을 모두 넣을 수 있습니다.

들어가세요

으아아아

출력

으아아아

지침

주어진 문자열에서 모든 0은 1 앞에 배치되었으므로 주어진 문자열에서 어떤 문자도 제거할 필요가 없습니다.

방법 1

첫 번째 방법에서는 두 개의 배열을 사용합니다. 첫 번째 배열은 왼쪽에 모두 1을 저장하고 다른 배열은 오른쪽에 모두 0을 저장합니다. 그런 다음 두 배열의 i번째 인덱스에 요소를 추가하고 최소 합계를 찾을 수 있습니다.

알고리즘

• 1단계 - 길이가 n인 0과 1의 명명된 목록을 정의합니다. 여기서 n은 size() 메서드를 사용하여 얻을 수 있는 문자열의 길이입니다.

• 2단계 - 주어진 문자열의 첫 번째 문자가 "1"이면 "ones" 배열의 0번째 인덱스에 1을 저장하고, 그렇지 않으면 0을 저장합니다.

• 3단계 - for 루프를 사용하여 문자열의 두 번째 요소에서 반복합니다. for 루프에서 Ones[i]는 인덱스 i에 있는 문자열의 문자를 기준으로 Ones[i-1]을 1 또는 0에 추가하여 얻은 값으로 초기화됩니다.

• 4단계 - 주어진 문자열의 마지막 문자에 따라 Zeros[n-1]에 1 또는 0을 저장합니다.

• 5단계 - for 루프를 사용하여 마지막 두 번째 문자부터 시작하는 문자열을 반복하고 문자열 문자를 기반으로 0 목록의 값을 업데이트합니다.

• 6단계 - "min_zeros_to_remove" 변수를 정의하고 최대 정수 값으로 초기화합니다.

• 7단계 - 이제 "0" 및 "1" 목록을 반복합니다. 0 목록의 "i+1" 인덱스와 "1" 목록의 "I" 인덱스에서 값에 액세스합니다. 그런 다음 이 두 요소를 추가합니다.

• 8단계 - "min_zeros_to_remove" 값이 "min_zeros_to_remove" 변수의 현재 값보다 작은 경우 해당 값을 두 배열 요소의 합으로 변경합니다.

• 9단계 - 결과 값을 반환합니다.

예

으아아아

출력

으아아아

• 시간 복잡도 - 크기가 N인 문자열과 목록을 반복하려면 루프가 필요하기 때문에 O(N)입니다.

• Space Complexity - O(N) 1과 0의 개수를 저장하기 위해 두 개의 목록을 사용하기 때문입니다.

방법 2

이 방법은 첫 번째 방법의 최적화된 버전입니다. 여기서는 목록 대신 두 개의 변수를 사용하여 1과 0의 개수를 저장합니다.

알고리즘

• 1단계 - "zeros_right" 변수를 정의하고 0으로 초기화합니다.

• 2단계 - 문자열을 반복하면서 주어진 문자열의 총 "0" 문자 수를 세고 이에 따라 "zero_right" 변수의 값을 업데이트합니다.

• 3단계 - "ones_left" 변수를 정의하고 0으로 초기화합니다.

• 4단계 - for 루프를 사용하여 문자열을 반복합니다. 문자열의 인덱스 i에 있는 문자가 "1"이면 "ones_left" 변수의 값을 1만큼 늘립니다. 그렇지 않으면 "zeros_right" 변수의 값을 1로 줄입니다.

• 5단계 - "zeros_right + Ones_left"가 "res" 변수의 현재 값보다 작은 경우 "res" 변수의 값을 업데이트합니다.

예

으아아아

출력

으아아아

• Time Complexity - O(N), 문자열을 반복할 때.

• Space Complexity - 일정한 공간만 사용하므로 O(1)입니다.

결론

사용자는 주어진 바이너리 문자열에서 최소 문자 수를 제거하는 두 가지 방법을 배웠습니다. 두 번째 접근 방식의 코드는 목록을 사용하는 대신 변수를 사용하여 0과 1의 개수를 저장하기 때문에 더 읽기 쉽습니다.

위 내용은 이진 문자열에서 1 앞에 0을 모두 배치하는 데 필요한 최소 이동 횟수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!