O(1) 추가 공간을 사용하여 단어를 뒤집음

문자열은 여러 단어로 구성될 수 있습니다. C++ 문자열의 각 단어에는 문자, 숫자 또는 특수 기호가 포함될 수 있습니다. 문자열은 이러한 문자의 저장 요소로 간주됩니다. 각 단어는 공백 문자로 구분됩니다. 각 단어는 또한 한 문자의 문자열을 형성합니다. C++에서 문자열의 반대는 −

뒤에 오는 문자열입니다.

• 끝부터 시작 부분까지 문자를 가져와서 구성됩니다.

• 원래 문자열의 길이는 변경되지 않습니다.

문자열에 나타나는 문자의 순서는 단어의 시작과 끝의 문자를 바꾸면 쉽게 바꿀 수 있습니다.

일정한 보조 공간은 O(1)로 표현되는데, 이는 프로그램 실행 중에 추가 공간이 필요하지 않음을 의미합니다.

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

예제 예

예 1 - str:Abc def

출력: cbA 공급

설명: 문자열을 반전할 때 문자의 상태는 변경되지 않습니다.

예 2 - str: 안녕하세요 spe%32

출력: yeH 23%eps

문제 설명은 각 단어를 추출하고 각 단어에 대한 시작 및 끝 포인터 쌍을 유지한 다음 이를 반전시켜 해결할 수 있습니다.

알고리즘

• 1단계−for 루프를 사용하여 제공된 입력 문자열을 반복합니다.

• 2단계 - 변수 st를 사용하여 첫 번째 단어의 시작 문자를 캡처합니다.

• 3단계 − 첫 번째 공백이 발견되면 lst 변수는 이전 문자에 고정되어 단어의 시작 문자와 끝 문자를 표시합니다.

• 4단계 − 이 두 포인터와 while 루프를 사용하여 단어의 문자를 반대로 바꿉니다. while 루프가 반복될 때마다 포인터가 이동하여 문자열을 모두 소모합니다.

• 5단계 − 값이 업데이트되어 포인터가 다음 후속 단어로 이동하는 식으로 st는 공백 뒤의 다음 문자로 다시 초기화됩니다.

• 6단계 - 전체 문자열이 반복되고 해당 단어가 반전됩니다.

예

다음 C++ 코드 조각은 문자열을 입력으로 사용하고 그 안에 포함된 단어를 반대로 바꿉니다. -

으아아아

출력

으아아아

공간 복잡성

모든 유형의 변수를 새로 초기화하지 않으므로 위 방법에 필요한 공간은 일정합니다. 단어를 교환하는 데 외부 공간 저장 장치가 필요하지 않습니다. 모든 수정은 사용 가능한 저장 변수에서 이루어집니다.

결론

문자열은 간단한 반복을 통해 임의의 순서로 정렬하거나 역순으로 정렬할 수 있는 문자로 구성됩니다. 알고리즘은 저장된 전체 문자 범위에 대해 단일 반복을 수행하므로 필요한 총 시간은 O(n)입니다. 여기서 n은 문자열 길이입니다.

위 내용은 O(1) 추가 공간을 사용하여 단어를 뒤집음의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!