문자열을 반전시키는 데 필요한 인접 스왑의 최소 수

문자열 str이 주어지면 인접한 문자를 바꾸는 것만으로 문자열을 뒤집을 수 있습니다. 인접한 문자를 바꾸는 것만으로 문자열을 뒤집는 데 필요한 최소 이동 횟수를 찾아야 합니다. 필요한 솔루션을 찾기 위해 두 가지 방법을 구현하고 코드에 대한 설명과 구현을 제공합니다.

예제 예

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

먼저 마지막 문자를 첫 번째 위치로 이동합니다. 이를 위해서는 4번의 교체가 필요합니다. 그런 다음 문자열은 "jshke"가 됩니다. 그런 다음 'e'를 두 번째 위치로 이동합니다. 이를 위해서는 3번의 교체가 필요합니다. 마찬가지로 'k'의 경우 두 개의 스왑이 필요하고 'h'의 경우 1개의 스왑만 필요하며 최종 답은 10입니다.

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

먼저 두 번째 인덱스의 문자를 교체하고 마지막 인덱스로 이동합니다. 2번의 교체가 필요하며 문자열은 "abcea"가 됩니다. 그런 다음 'b'를 'e'로 바꾸면 2번의 교환이 필요하고 문자열은 "aceba"가 됩니다. 그런 다음 2번 더 교환을 수행하여 최종 역방향 문자열을 얻으려면 총 6번의 교환이 필요합니다.

Naive Approach

의 중국어 번역은

Naive Approach

입니다.

위의 예를 살펴봤으니 이제 올바른 코드를 구현하는 데 필요한 단계를 살펴보겠습니다.

• 먼저, 주어진 문자열을 매개 변수로 사용하고 필요한 최소 단계 수를 반환 값으로 반환하는 함수를 만듭니다.

• 이 함수에서는 문자열의 복사본을 만든 다음 이를 뒤집어 원래 문자열과 비교합니다.

• 세 개의 변수를 생성하겠습니다. 처음 두 개는 문자열을 반복하는 데 사용되고 마지막 변수는 필요한 단계 수를 저장하는 데 사용됩니다.

• while 루프를 사용하여 주어진 문자열을 반복하고 현재 인덱스 값과 동일한 반복 횟수를 계속 건너뛰어 문자열을 반전시킵니다.

• 그런 다음 'j'가 'i'에 도달할 때까지 while 루프를 사용하여 인접한 문자를 바꾸고 각 교환의 수를 증가시킵니다.

• 마지막으로 카운트 값을 반환하고 이를 메인 함수에서 출력해보겠습니다.

예

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(N^2)입니다. 여기서 N은 주어진 문자열의 길이입니다. 반복하는 동안 N의 인수를 제공하기 위해 중첩된 while 루프를 사용합니다.

위 코드의 공간 복잡도는 O(N)입니다. 주어진 문자열의 반전을 저장하기 위해 추가 문자열을 생성하기 때문입니다.

NOTE - 여기에서는 대체 접근 방식이 가능하지만 매우 고급 데이터 구조를 사용해야 합니다. 이 방법의 개념은 마지막 문자부터 시작하여 첫 번째 문자가 조건을 충족할 때까지 확인할 수 있다는 것입니다. 그런 다음 이론적으로는 해당 캐릭터를 마지막 위치로 이동하고 해당 위치를 완료된 것으로 표시하고 해당 값을 상위 수준 데이터 구조에 저장할 수 있습니다.

그런 다음 각 캐릭터에 대해 아직 태그가 지정되지 않은 뒤에서 오는 동일한 캐릭터를 찾은 다음 그 뒤의 총 요소 수에서 태그가 지정된 요소 수를 뺀 수로 개수를 늘립니다.

결론

이 튜토리얼에서는 인접한 문자만 바꿔서 주어진 문자열을 뒤집는 데 필요한 최소 단계 수를 찾는 코드를 구현했습니다. 우리는 중첩된 while 루프를 사용하고 주어진 문자열의 복사본을 역전하여 해결책을 찾았습니다. 위 코드의 시간 복잡도는 O(N^2)입니다. 여기서 N은 문자열의 크기이고 공간 복잡도는 O(N)입니다.

위 내용은 문자열을 반전시키는 데 필요한 인접 스왑의 최소 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!