C++ 프로그램: 왼쪽과 오른쪽 회전이 동일한 숫자의 가장 긴 부분 수열을 찾습니다.

이 문제에서는 왼쪽과 오른쪽 회전이 동일한 부분 수열의 최대 길이를 구해야 합니다. 왼쪽 회전은 문자열의 모든 문자를 왼쪽으로 이동하고 끝의 첫 번째 문자를 이동하는 것을 의미합니다. 오른쪽 회전은 모든 문자열 문자를 오른쪽으로 이동하고 마지막 문자를 시작 부분으로 이동하는 것을 의미합니다.

문제 설명 – 숫자가 포함된 문자열 str이 주어지고 동일한 왼쪽 및 오른쪽 회전으로 최대 길이의 하위 시퀀스를 찾아야 합니다.

예

Enter -str="323232",

출력– 6

설명 – 왼쪽과 오른쪽 회전이 동일한 가장 긴 부분 수열은 “323232”입니다. 왼쪽으로 회전하면 '232323', 오른쪽으로 회전하면 '232323'이 됩니다.

Enter -str = '00010100'

출력– 6

설명 - 왼쪽과 오른쪽 회전이 동일한 가장 긴 부분 수열은 "000000"입니다.

Enter -str = '092312110431010'

출력– 6

설명 – 왼쪽과 오른쪽 회전이 동일한 길이 6의 하위 수열이 2개 있습니다. 첫 번째는 "010101"이고 두 번째는 "101010"입니다.

방법 1

이 방법에서는 주어진 문자열의 가능한 모든 하위 시퀀스를 찾습니다. 그런 다음 문자열의 왼쪽 회전과 오른쪽 회전이 동일한지 확인합니다. 가능한 모든 하위 수열을 찾기 위해 재귀적 방법을 사용할 것입니다.

알고리즘

• 왼쪽 및 오른쪽 회전에 대해 동일한 가장 긴 부분 시퀀스의 길이를 저장하려면 "maxLen" 전역 변수를 0으로 초기화하세요.

• 문자열의 왼쪽 회전과 오른쪽 회전이 동일한지 확인하려면 isRightSameLeft() 함수를 정의하세요.

• 함수 내에서 substr() 메서드를 사용하여 문자열을 왼쪽과 오른쪽으로 회전합니다.

• getAllSubSeq() 함수는 주어진 문자열의 가능한 모든 하위 시퀀스를 찾는 데 사용됩니다.

• 기본 사례를 정의합니다. str이 비어 있으면 하위 시퀀스를 가져오고 isRightSameLeft() 함수를 실행하여 하위 시퀀스의 왼쪽 및 오른쪽 회전이 동일한지 확인합니다. 그렇다면 길이가 "maxLen"의 현재 값보다 크면 "maxLen" 변수의 값을 업데이트하십시오.

• "str"에서 첫 번째 문자를 제거하고 "out" 문자열을 추가한 후 재귀 호출을 수행합니다.

• 첫 번째 문자를 제거하고 "out" 문자열을 변경하지 않은 후 또 다른 재귀 함수 호출을 수행합니다. 이 재귀 호출에서는 "str"의 첫 번째 문자를 제외합니다.

예

으아악

출력

으아악

시간 복잡도 - O(N*2N). 여기서는 왼쪽과 오른쪽 회전을 비교하기 위한 O(N)과 가능한 모든 하위 시퀀스를 찾기 위한 O(2N)입니다.

공간 복잡도 - 추가 공간을 사용하지 않으므로 O(1)입니다.

방법 2

여기에서는 위의 방법을 최적화했습니다. 샘플 입력의 해를 관찰할 수 있습니다. 하위 시퀀스의 왼쪽 및 오른쪽 회전은 하위 시퀀스에 동일한 문자가 포함되거나 교대로 두 개의 다른 문자가 포함되고 길이가 짝수인 경우에만 동일합니다.

알고리즘

• 두 개의 중첩 루프를 사용하여 두 숫자를 결합하세요.

• 두 개의 숫자가 교대로 포함된 부분 수열의 길이를 구하려면 'cnt' 변수를 정의하고 0으로 초기화하세요.

• 다음 문자가 i번째 문자인지 j번째 문자인지 추적하는 부울 "first" 변수를 정의합니다.

• 루프를 사용하여 문자열을 탐색하세요.

• first == true이고 str[k] - '0' == I인 경우 'first' 값을 대체하고 'cnt'를 1씩 증가시킵니다.

• first == false이고 str[k] - '0' == j인 경우 'first' 값을 다시 대체하고 'cnt'를 1씩 증가시킵니다.

• i와 j가 같지 않고 "cnt" 값이 홀수이면 1씩 감소합니다.

• cnt 값이 "res"보다 큰 경우 "res" 변수의 값을 업데이트하세요.

예

으아악

출력

으아악

시간 복잡도 - O(10*10*N) 숫자 조합을 포함하는 문자열에서 하위 시퀀스를 찾기 때문입니다.

공간 복잡성 - 동적 공간을 사용하지 않기 때문에 O(1)입니다.

이 튜토리얼에서는 동일한 왼쪽 및 오른쪽 회전을 포함하는 가장 긴 부분 수열을 찾는 두 가지 방법을 알려줍니다. 첫 번째 방법은 시간이 많이 걸리고 큰 입력에는 사용할 수 없는 간단한 방법입니다.

두 번째 방법은 최적화되었으며 시간 복잡도는 O(N)과 거의 같습니다.

위 내용은 C++ 프로그램: 왼쪽과 오른쪽 회전이 동일한 숫자의 가장 긴 부분 수열을 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!