주어진 이진 문자열을 다른 이진 문자열로 변환합니다. 최소 피연산자는 하나를 제외한 모든 비트를 뒤집습니다.

이 문제에서는 문자열의 문자를 뒤집어 하나의 이진 문자열을 다른 이진 문자열로 변환해야 합니다. 설정된 비트를 저장하고 다른 비트를 뒤집을 수 있으며, 이를 통해 다른 문자열을 구현하기 위한 전체 작업을 계산해야 합니다.

주어진 문자열에서 "01"과 "10" 쌍의 총 개수를 기반으로 문제를 풀 수 있습니다.

문제 설명- 이진 문자열을 나타내는 "0"과 "1" 문자를 포함하는 str1 및 str2라는 이름의 동일한 길이의 두 문자열이 제공됩니다. 다음을 수행하여 문자열 str1을 str2로 변환해야 합니다.

• 설정된 비트를 선택하고 다른 모든 비트를 뒤집을 수 있습니다. 비트 뒤집기는 "0"을 "1"로, "1"을 "0"으로 변환하는 것을 의미합니다.

• str1을 str2로 변환할 수 없으면 -1을 인쇄하세요.

예

들어가세요

출력

설명−

• 첫 번째 작업에서는 두 번째 인덱스의 "1"을 변경하지 않고 유지하고 str1의 다른 모든 문자를 뒤집습니다. 따라서 str1은 111110000이 됩니다.

• 두 번째 작업에서는 0번째 인덱스의 "1"을 변경하지 않고 유지하고 다른 모든 문자를 뒤집습니다. 따라서 str1은 100001111이 됩니다.

• 마지막 작업에서는 5번째 인덱스에 "1"을 저장합니다. 따라서 str1은 011111000이 됩니다.

들어가세요

출력

설명- str1에 저장할 "1" 문자가 포함되어 있지 않기 때문에 str1을 str2로 변환할 수 없습니다.

들어가세요

출력

Explanation- str1을 str2로 변환할 수 없습니다.

방법 1

우리는 관찰을 통해 문제를 해결할 수 있습니다. 단일 세트 비트를 보유하고 2개의 작업을 수행하면 동일한 문자열을 얻을 수 있다는 것이 관찰되었습니다. 따라서 문자열을 변경하려면 다른 1 인덱스를 선택해야 합니다.

또한 01 쌍을 10으로 변환하려면 2번의 작업을 수행해야 합니다. 예를 들어 "01"은 "1"로 둡니다. 그래서 우리는 "11"을 얻습니다. 그런 다음 "11"의 0번째 인덱스에 "1"을 유지하여 "10"을 얻습니다.

답을 얻으려면 01(0 -> str1, 1 -> str2)과 10(1 -> str1, 0 -> str2)이 동일해야 합니다. 그렇지 않으면 답이 존재하지 않는다고 말할 수 있습니다.

우리의 주요 목표는 "01"과 "10" 쌍을 최소화하는 것입니다. 두 번의 작업으로 "01"을 "10"으로 변환할 수 있기 때문입니다.

알고리즘

1단계 - str1을 str2로 변환하는 데 필요한 작업 수를 계산하는 totalOperatrions() 함수를 정의합니다.

1.2단계 - count10 및 count01 변수를 초기화하여 "01" 및 "10" 쌍을 문자열에 저장합니다.

1.3단계 - 문자열을 반복하고 두 문자열 모두에서 01과 10의 쌍을 셉니다.

1.4단계− count10과 count01이 동일하면 2*count10을 반환합니다. 그렇지 않으면 -1이 반환됩니다.

2단계 - 최소 작업() 함수를 정의하여 str1을 str2로 변환하는 데 필요한 최소 작업을 계산합니다.

3단계 - "ans"를 최대값으로 초기화합니다.

4단계 - 원래 문자열을 사용하여 totalOperations() 함수를 호출하고 결과를 "Operation1" 변수에 저장합니다. 반환 값이 -1이 아닌 경우 ans 및 작업 1의 최소값이 ans에 저장됩니다.

5단계 - 이제 문자열을 수정하여 01과 10의 쌍을 최소화하겠습니다. 따라서 stringModification() 함수를 정의하십시오.

5.1단계 - 함수에서 문자열에서 "1ch"의 첫 번째 쌍을 찾고 "ch"를 매개변수로 전달합니다("0" 또는 "1"일 수 있음). 따라서 쌍은 1 -> str1 및 ch -> str과 같아야 합니다.

5.2단계 - "1ch" 쌍이 없으면 false를 반환합니다.

5.3단계 − "1ch" 쌍이 발견되면 해당 쌍을 변경하지 않고 그대로 두고 str1의 다른 문자를 뒤집습니다.

6단계 - stringModification 함수를 실행하여 "11" 쌍을 변경하지 않고 다른 문자를 뒤집습니다. 그런 다음 str1을 str2로 변환하는 데 필요한 작업을 찾기 위해 totalOperations() 함수가 다시 호출됩니다.

7단계− 연산 2가 -1이 아닌 경우 "ans"에 최소값을 저장하거나 "ans"에 "1 + 연산 2"를 저장합니다. 여기서는 한 번의 연산으로 문자열을 수정했기 때문에 1을 추가했습니다.

8단계 - 첫 번째 "10" 쌍을 변경하지 않고 그대로 두고 문자열을 수정하고 피연산자를 계산합니다. 다시 "ans"에 최소값을 할당합니다.

9단계− "ans"가 INT_MAX와 같으면 -1을 반환합니다. 그렇지 않으면 ans를 반환합니다.

예

출력

시간 복잡도− O(N) 왜냐하면 stringModification() 및 totalOperations() 함수에서 문자열을 반복하기 때문입니다.

공간 복잡성− O(1) 추가 공간을 사용하지 않고 동일한 문자열을 수정하기 때문입니다.

코드에서 우리의 주요 목적은 문자열을 수정한 후 주어진 문자열에서 01과 10의 쌍 수를 줄여 작업을 최소화하는 것입니다. 프로그래머는 다양한 입력을 사용하여 답을 이해하려고 노력할 수 있습니다.

위 내용은 주어진 이진 문자열을 다른 이진 문자열로 변환합니다. 최소 피연산자는 하나를 제외한 모든 비트를 뒤집습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!