문자 위치와 주파수 패리티가 동일한 문자 수의 패리티

이 질문에서는 빈도와 위치가 동일한 패리티를 갖는 문자 수를 계산하고 해당 숫자의 수를 홀수 또는 짝수로 인쇄합니다.

이 문제를 해결하기 위해 문자열에서 각 문자의 빈도를 찾고 빈도와 위치에서 동일한 패리티를 갖는 문자의 총 개수를 계산할 수 있습니다. 그런 다음 개수에 따라 홀수 또는 짝수 답변을 인쇄할 수 있습니다.

문제 설명 - 영어 소문자만 포함하는 문자열 알파가 제공됩니다. 문자 위치와 빈도가 동일한 문자의 개수가 홀수인지 짝수인지 확인해야 합니다.

다음 조건 중 하나라도 충족하는 문자가 있으면 해당 문자는 동일한 빈도 및 문자 위치 패리티를 갖습니다.

• 문자열의 문자 빈도가 홀수이고 문자 위치도 홀수인 경우.

• 문자열의 문자 빈도가 짝수이고 문자 위치도 짝수인 경우.

예

들어가세요

으아아아

출력

으아아아

지침

• a의 빈도는 1이고 위치는 1이므로 패리티는 동일하고 카운트가 1이 됩니다.

• d의 빈도는 2이고 위치는 4입니다. 따라서 패리티 비트가 동일하므로 개수는 2가 됩니다.

카운트 값은 짝수인 2입니다.

들어가세요

으아아아

출력

으아아아

설명 – 'p'의 패리티만 동일합니다. 따라서 개수는 1이고 답은 홀수입니다.

들어가세요

으아아아

출력

으아아아

Notes - 패리티는 모든 캐릭터에 동일하지 않습니다. 따라서 count 값이 0이므로 "Even"을 인쇄합니다.

방법 1

이 방법에서는 맵 데이터 구조를 사용하여 각 문자열 문자의 빈도를 저장합니다. 그런 다음 문자 위치와 빈도가 동일한 패리티를 갖는 문자 수를 계산합니다.

알고리즘

1단계 - 길이가 27인 count[] 배열을 정의하고 0으로 초기화합니다. 또한 "패리티"를 0으로 초기화합니다.

2단계 - 문자 빈도를 count[] 배열에 저장합니다.

3단계 - 각 소문자 알파벳 문자를 26번 반복합니다.

4단계 - count[p]가 0보다 큰 경우 문자 빈도와 위치가 동일한 패리티를 갖는지 확인하세요. 그렇다면 패리티 값을 1씩 늘립니다.

5단계 - 마지막으로 패리티가 2로 나누어지면 "Even"을 반환합니다. 그렇지 않으면 "홀수"를 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - 문자의 빈도를 계산하는 O(N)입니다.

공간 복잡도 - O(26) ~ O(1)은 알파벳 문자의 빈도를 저장합니다.

방법 2

이 방법에서는 주어진 문자열을 정렬합니다. 그 후, 인접한 다른 문자를 얻을 때마다 이전 문자의 빈도와 위치 패리티를 확인합니다.

알고리즘

1단계 - "패리티"를 0으로 초기화합니다.

2단계 - sort() 메소드를 사용하여 주어진 문자열을 정렬합니다.

3단계 - 문자열 탐색을 시작하고 'charCnt'를 0으로 초기화하여 현재 문자의 빈도를 저장합니다.

4단계 - 현재 문자가 다음 문자와 다른 경우 "charCnt"의 패리티와 문자 위치가 일치하는지 확인하세요. 그렇다면 패리티를 1만큼 늘립니다.

5단계 - 현재 문자가 이전 문자와 동일하면 "charCnt"를 1 늘립니다.

6단계 - 마지막으로 "Parity" 값이 짝수이면 "Even"을 반환합니다. 그렇지 않으면 "홀수"를 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - 문자열 정렬을 위한 O(NlogN)입니다.

공간 복잡성 - 문자열을 정렬하는 O(N)입니다.

첫 번째 방법은 일정한 공간을 사용하는 반면, 두 번째 방법은 주어진 문자열을 정렬하기 위해 동적 공간을 사용합니다. 또한 두 번째 방법은 시간 비용이 많이 들기 때문에 더 나은 성능을 위해서는 첫 번째 방법을 사용하는 것이 좋습니다.

위 내용은 문자 위치와 주파수 패리티가 동일한 문자 수의 패리티의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!