이진 문자열을 다른 문자열로 변환하는 데 필요한 접두어 뒤집기의 최소 수

이 문제에서는 접두어를 뒤집어 첫 번째 이진 문자열을 두 번째 이진 문자열로 변환해야 합니다. 최소 접두사 뒤집기 횟수를 얻으려면 문자열 끝을 반복해야 하며 두 문자열 모두에서 일치하지 않는 문자가 발견되면 첫 번째 문자열의 접두사를 뒤집어야 합니다.

문제 설명 − 첫 번째와 두 번째라는 두 개의 서로 다른 이진 문자열이 제공됩니다. 두 이진 문자열의 길이는 N입니다. 접두사를 뒤집어 첫 번째 문자열을 두 번째 문자열로 변환해야 합니다. 여기서는 한 문자열을 다른 문자열로 변환하는 데 필요한 총 접두사 뒤집기 수를 계산해야 합니다. Flip은 '0'을 '1'로, '1'을 '0'으로 변환하는 것을 의미합니다.

샘플 예

으아악 으아악

설명

• 먼저 첫 번째 문자열의 길이가 3인 접두사를 뒤집어야 하며 결과 문자열은 110이 됩니다.

• 이후 길이가 2인 접두사를 뒤집어야 하며 결과 문자열은 두 번째 문자열과 동일한 000이 됩니다.

으아악 으아악

설명

길이 2인 접두사를 뒤집어야 하며 결과 문자열은 두 번째 문자열과 동일한 '01'이 됩니다.

으아악 으아악

설명

두 문자열이 동일하므로 뒤집을 필요가 없습니다.

접근법 1

이 방법에서는 문자열 끝부터 반복하고 일치하지 않는 문자를 찾으면 'I + 1' 길이의 접두사에 있는 모든 문자를 뒤집습니다. 이것은 문제를 해결하는 간단한 방법입니다.

알고리즘

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

• 2단계 − 루프를 사용하여 문자열 끝부터 탐색을 시작합니다.

• 3단계 − first[i]와 second[i]가 같지 않으면 길이가 I + 1과 같은 접두사 문자를 모두 뒤집어야 합니다.

• 4단계 − 중첩 for 루프를 사용하여 길이가 I + 1인 접두사를 반복하고, FlipBits() 함수를 실행하여 각 문자를 뒤집습니다.

• 4.1단계 − FlipBits() 함수에서 현재 문자가 '1'이면 '0'을 반환하고, 현재 문자가 '0'이면 '1'을 반환합니다.

• 5단계 − 접두어를 뒤집을 때 'cnt' 변수의 값을 1만큼 늘립니다.

• 6단계 - 'cnt' 변수의 값을 반환합니다.

예

으아악

출력

으아악

접근법 2

이 접근 방식에서는 매번 각 접두사 비트를 뒤집는 대신 'inverted' 변수를 사용하여 현재 비트가 뒤집혔는지 여부를 추적합니다. 또한 이 접근 방식에서 코드의 시간 복잡도를 최적화합니다.

알고리즘

• 1단계 − 'cnt' 변수를 정의하고 '0'으로 초기화합니다. 또한 'inverted' 변수를 정의하고 false 값으로 초기화합니다.

• 2단계 - 끝부터 문자열을 탐색합니다. 첫 번째 [i]와 두 번째 [i] 문자가 일치하지 않는 경우 다음 단계를 따르세요.

• Step 2.1 − 'inverted' 변수의 값이 false인 경우 'cnt' 변수의 값을 1 증가시키고, 'inverted' 변수의 값을 true로 변경합니다.

• 3단계 − 두 문자가 모두 일치하고 'inverted' 값이 true이면 비트를 다시 뒤집어야 합니다. 따라서 'cnt' 값을 1만큼 늘리고 'inverted' 값을 변경합니다. '를 거짓으로.

예

예제를 통해 위 알고리즘을 디버깅해 보겠습니다.

으아악

• 첫 번째 단계에서 첫 번째 [2]와 두 번째 [2]가 일치하지 않으며 'inverted' 값이 false입니다. 따라서 'cnt'의 값은 1이 되고, 'inverted'는 true가 됩니다. 여기서 'inverted' 값을 true로 변경함으로써 접두사를 사실상 반전시켰다고 가정합니다.

• 이후에는 첫 번째[1]과 두 번째[1]이 일치하지만 'inverted' 값은 true이므로 'cnt' 값은 2가 되고 'inverted'는 false가 됩니다.

• 다음으로 첫 번째[0]과 두 번째[0]이 일치하며 'inverted' 값은 false이므로 아무런 연산도 수행할 필요가 없습니다.

• 마지막으로 값이 2인 'cnt'를 반환합니다.

으아악

출력

으아악

결론

한 문자열을 다른 문자열로 변환하는 데 필요한 최소 접두사 뒤집기 수를 찾는 두 가지 방법을 배웠습니다. 논리는 문자열을 끝에서부터 반복하고 일치하지 않는 문자를 찾으면 접두사를 뒤집는 것입니다.

첫 번째 접근 방식처럼 반전된 접두사를 반전시키는 대신 "역전된" 변수를 사용하여 반전된 접두사를 추적함으로써 시간 복잡도 측면에서 두 번째 코드 조각을 최적화했습니다.

위 내용은 이진 문자열을 다른 문자열로 변환하는 데 필요한 접두어 뒤집기의 최소 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!