>  기사  >  백엔드 개발  >  두 개의 연속된 0을 하나의 1로 반복적으로 대체하여 주어진 이진 문자열을 동일하게 만듭니다.

두 개의 연속된 0을 하나의 1로 반복적으로 대체하여 주어진 이진 문자열을 동일하게 만듭니다.

WBOY
WBOY앞으로
2023-09-01 15:13:06794검색

두 개의 연속된 0을 하나의 1로 반복적으로 대체하여 주어진 이진 문자열을 동일하게 만듭니다.

모든 프로그래밍 언어에서 이진 문자열은 문자 0과 1의 모음입니다. 각 단계에서 이진 문자열은 문자열에 이 두 문자만 포함될 수 있다는 접근 방식을 따릅니다.

연속된 문자열의 문자는 인덱스가 1씩 다른 문자입니다. 두 개의 인덱스 i와 j를 고려해 보겠습니다. |j-i| = 1이면 연속이라고 합니다.

C++에서 두 문자열이 동일하면 다음을 의미합니다.

  • 두 문자열의 해당 문자는 동일합니다.

  • 문자열은 길이가 같고 해당 인덱스의 문자가 일치합니다.

문제 설명을 설명하는 몇 가지 예는 다음과 같습니다. -

예제 예

str1 - "10001"

str2 - "101"

솔루션-

str1을 str2로 변환할 수 없습니다. 왜냐하면 str1을 변환하여 동등한 문자열 str2를 생성하는 과정에서 str1을 "1011"로, str2를 "101"로 얻게 되기 때문입니다.

예 2 - 다음 입력을 고려해 보겠습니다 −

str1 - "001"

str2 - "11"

솔루션-

str1은 처음 두 개의 0을 1로 변경하여 str2로 변환할 수 있습니다.

C++에서 문자 일치 및 문자열 탐색을 사용하여 다음 문제를 해결하세요.

알고리즘

  • 1단계 - 두 개의 포인터 i와 j는 문자열 s1과 s2를 동시에 반복하는 데 사용됩니다.

  • 2단계 - 두 인덱스의 문자가 일치하면 i 및 j 포인터를 증가시킵니다.

  • 3단계 − 문자가 같지 않으면 i번째와 (i+1)번째 인덱스의 문자가 '0'인지, j번째 인덱스의 문자가 '1'인지 확인합니다. '.

  • 4단계 - 이러한 상황이 발생하면 변환을 수행할 수 있습니다. i 포인터는 두 위치만큼 증가하고 j는 두 개의 0이 1로 변환되므로 한 인덱스 위치만큼 증가합니다.

  • 5단계 - 문자가 동일하지 않고 위의 상황이 존재하지 않는 경우 변환을 수행할 수 없습니다.

  • 6단계 − 포인터 i와 j가 모두 끝 위치에 성공적으로 도달하면 s1을 s2로 변환할 수 있습니다.

다음 코드 조각은 두 개의 이진 문자열을 입력으로 사용하고 지정된 조건에 따라 간단한 문자 대체를 통해 두 문자열이 동일할 수 있는지 확인합니다

으아악

출력

으아악

결론

이 방법은 입력 문자열을 문자별로 효율적으로 비교할 수 있으므로 시간 복잡도는 O(최소(문자열 길이))입니다. 문자열 순회는 문자열 문제를 해결하는 데 중요한 측면입니다.

위 내용은 두 개의 연속된 0을 하나의 1로 반복적으로 대체하여 주어진 이진 문자열을 동일하게 만듭니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 tutorialspoint.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제