하위 문자열의 모든 문자를 증가시켜 문자열 회문을 만드는 데 필요한 최소 이동 횟수

컴퓨터 과학 및 프로그래밍 분야에서는 문제 해결을 위한 효율적인 알고리즘을 찾는 것이 매우 중요합니다. 흥미로운 문제는 하위 문자열의 모든 문자를 추가하여 문자열을 회문으로 변환하는 데 필요한 최소 작업 수를 식별하는 것입니다. 이 기사에서는 C++ 프로그래밍 언어를 사용하여 이 문제에 접근하는 두 가지 방법을 살펴봅니다.

문법

이 메서드를 살펴보기 전에 사용할 함수의 구문을 정의해 보겠습니다. −

으아아아

알고리즘

• 우리의 목표는 문자열을 회문으로 변환할 때 이동 횟수를 최소화하는 것입니다. 이 문제는 다음 주요 단계를 통해 알고리즘으로 해결됩니다 −

• 먼저 문자열 양쪽에서 두 개의 포인터 변수를 만듭니다. 왼쪽 포인터는 문자열의 시작 부분에서 시작하고 오른쪽 포인터는 문자열의 끝 부분에서 시작합니다.

• 구성 제한이 허용하는 한 프로세스를 계속합니다. 즉, 두 포인터 중 하나가 다른 포인터를 초과하면 중지됩니다. −

• 문자 값이 동일할 때마다 두 포인터를 서로 더 가깝게 이동하세요. 문자 값이 다를 때마다 추가 작업을 수행하기 전에 오른쪽의 문자 값이 차이에 따라 증가됩니다. 이 증가는 'a'와 'c' 사이의 차이에 비례합니다. 따라서 str[right]가 'c'와 같고 str[left]가 'a'와 같으면 str[right]를 2만큼 증가시킵니다('a'- 'c'=2). 이에 따라 이동 횟수를 업데이트합니다.

• 왼쪽 변이 오른쪽 변보다 크면 문자열은 회문이 됩니다.

방법 1: 무차별 크래킹

이 방법에서는 가능한 모든 하위 문자열을 고려하고 각 하위 문자열에 필요한 최소 이동 횟수를 계산합니다. 마지막으로 계산된 모든 이동의 최소값을 반환합니다.

예

으아아아

출력

으아아아

Explanation

은 다음과 같이 번역됩니다.

Explanation

입력 문자열 str을 필요한 최소 이동 횟수로 회문으로 변환하는 minMovesToMakePalindrome이라는 함수가 생성되었습니다. 몇 가지 단계별 지침을 통해 작동 방식을 설명합니다.

필요한 총 이동 횟수를 추적하는 이동 변수를 0으로 초기화합니다. - 길이 변수는 입력 문자열 str의 길이를 기록하므로 다음 단계는 대칭 위치가 겹치지 않도록 for 루프를 사용하여 문자열의 절반을 반복하는 것입니다. - 마지막으로 이 루프 내에서 abs(str[i] - str[length - i - 1]) 은 두 끝 문자 간의 절대 차이를 계산합니다.

계산된 차이는 해당 위치의 캐릭터를 동일하게 만드는 데 필요한 이동 횟수를 나타냅니다. 이 차이를 이동 횟수에 추가합니다.

필요한 모든 위치를 반복한 후 필요한 총 최소 이동 수를 이동 변수에 저장합니다. 우리는 이 값을 반환합니다.

main 함수에서는 "abcde" 값으로 문자열 str을 초기화합니다. 그런 다음 str을 매개변수로 전달하여 minMovesToMakePalindrome 함수를 호출합니다. 반환된 최소 이동 횟수는 minMoves 변수에 저장됩니다. 마지막으로 결과를 콘솔에 인쇄합니다.

방법 2: 최적의 이중 포인터 방법

이 방법은 두 개의 포인터를 사용하여 문자열의 양쪽 끝에서 동시에 탐색합니다. 효율성을 염두에 두고 우리는 문자열을 회문으로 변환하는 기술을 사용했습니다. 여기에는 입력의 양쪽 끝에서 문자를 점진적으로 추가하고 일치시키는 작업이 포함됩니다. 이 접근 방식은 불필요한 작업을 최소화하고 정확성이나 기능을 저하시키지 않으면서 더 빠른 변환을 가능하게 합니다.

예

으아아아

출력

으아아아

Explanation

은 다음과 같이 번역됩니다.

Explanation

아래 코드 예제의 목표는 최적의 두 포인터 접근 방식을 활용하여 주어진 문자열을 회문으로 변환하는 데 필요한 최소 이동 횟수를 결정하는 것입니다.

이를 달성하기 위해 minMovesToMakePalindrome이라는 함수를 만들었습니다. 이 함수는 문자열 인수를 받아들이고 필요한 총 이동 횟수를 반환합니다. 먼저 이동 횟수를 계산하는 데 사용되는 변수를 0으로 설정하고 왼쪽 및 오른쪽 포인터를 초기화합니다. 왼쪽 포인터는 입력 문자열의 시작(인덱스 0)에서 시작하고 오른쪽 포인터는 끝(인덱스 str)에서 시작합니다. 길이() - 1).

while 루프는 문자열의 모든 요소를 ​​포함하기 위해 왼쪽이 오른쪽보다 크거나 같을 때까지 반복합니다. 각 반복에서 우리는 이 두 문자를 동일하게 만드는 데 필요한 이동 횟수를 나타내는 abs(str[right] - str[left])를 사용하여 왼쪽과 오른쪽 위치에 있는 문자 간의 차이를 찾습니다. 이 차이 값을 실행 카운터에 추가하여 총 이동 횟수를 얻습니다.

입력 문자열의 중심으로 이동하면서 왼쪽 포인터를 증가시키고 오른쪽 포인터를 감소시킵니다. 왼쪽 포인터와 오른쪽 포인터 사이에 겹치는 부분이 없으면 문자열을 회문으로 변환합니다.

이 시점에서 'moves'에 저장된 총 이동 횟수를 반환합니다. main()에서는 이전에 새 입력 문자열 'abcde'를 선언한 것과 동일한 단계를 따릅니다. 이 인수를 사용하여 minMovesToMakePalindrome을 호출하면 총 최소 이동 횟수 값이 반환됩니다. 이 값을 콘솔에 인쇄하기 전에 새 변수 'minMoves'에 할당되었습니다.

결론

다음 텍스트에서는 문자 연산을 통해 주어진 문자열을 하위 문자열의 회문으로 변환하는 데 필요한 이동 횟수를 계산하는 장애물에 대한 통찰력과 잠재적 답변을 제공하는 것을 목표로 두 가지 대안이 제시됩니다. 무차별 방식이라고 하는 한 가지 방법은 가능한 모든 하위 문자열을 포함하는 반면, 최적의 2포인터 방법이라고 하는 다른 방법은 필요한 이동 횟수를 크게 줄입니다. 코더는 이러한 메커니즘을 쉽게 적용하여 유사한 장애물을 해결하고 솔루션을 개선할 수 있습니다.

위 내용은 하위 문자열의 모든 문자를 증가시켜 문자열 회문을 만드는 데 필요한 최소 이동 횟수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!