설명된 작업을 수행한 후 길이가 1부터 N까지인 각 접두사의 각 소문자 수
- WBOY앞으로
- 2023-09-15 09:05:02592검색
이 문제에서는 각 문자열 접두사에 대해 주어진 작업을 수행해야 합니다. 마지막으로 각 문자의 빈도를 계산해야 합니다.
그리디 알고리즘을 사용하여 이 문제를 해결할 수 있습니다. 길이가 K인 각 접두사를 가져와서 주어진 조건에 따라 해당 문자를 업데이트해야 합니다. map을 사용하여 최종 문자열의 문자 빈도를 계산할 수 있습니다.
문제 설명 - N개의 소문자 알파벳 문자를 포함하는 문자열 tr이 제공됩니다. 또한 총 26개의 요소를 포함하는 매핑 목록이 제공됩니다. 각 요소는 해당 값에 따라 소문자로 매핑됩니다. 예를 들어, 매핑[0]은 "a"에 매핑되고, 매핑[1]은 "b"에 매핑되며, 매핑[25]는 "z"에 매핑됩니다. 또한 매핑된 배열에는 1 또는 -1이 포함됩니다.
다음을 수행해야 합니다.
길이가 K인 접두사에서 최대 문자를 가져오고 '매핑' 배열에서 매핑 값을 가져옵니다.
매핑된 값이 1이면 모든 접두사 요소를 1씩 늘립니다.
매핑된 값이 -1이면 모든 접두사 요소를 1씩 감소시킵니다.
여기서 요소를 추가한다는 것은 'a' −> 'b', 'b' −> 'c',… 'z' −>
요소 감소는 'a'->'z', 'b'->'a',…를 의미합니다. 'z'->'y'.
길이가 1
예제 예
들어가세요
으아아아출력
으아아아지침
길이가 1인 접두사에서 가장 큰 문자는 'p'이며 이는 -1에 매핑됩니다. 따라서 업데이트된 문자열은 'orogress'가 됩니다.
길이 2인 접두사에서 최대 문자는 'r'이고 매핑은 -1입니다. 따라서 업데이트된 문자열은 "nqogress"가 됩니다.
길이가 3인 접두사에서 가장 큰 문자는 'q'이고 매핑 값은 1입니다. 따라서 업데이트된 문자열은 'orpgress'입니다.
모든 작업이 끝나면 최종 문자열은 'f' 1개, 'p' 2개, 'q' 2개, 'm' 1개, 'd' 1개, 'd' 'r 1개를 포함하는 'pqmfpdqr'이 됩니다. '. 출력에서는 결과 문자열의 각 문자의 빈도를 인쇄합니다.
들어가세요
으아아아출력
으아아아설명− 모든 작업을 수행한 후 최종 문자열은 'ac'이고 각 문자의 빈도를 인쇄합니다.
방법 1
이 방법에서는 문자열을 반복하고 인덱스 P와 동일한 K 값을 사용합니다. 그런 다음 길이가 P와 같은 접두사를 가져와 가장 큰 문자를 찾고 매핑된 값을 가져와 그에 따라 모든 접두사 문자를 업데이트합니다.
알고리즘
1단계 − 'max_char' 변수를 정의하여 주어진 접두사의 최대 문자를 저장합니다.
2단계 − 마찬가지로, 최종 문자열에 각 문자의 빈도를 저장하기 위해 길이가 26인 목록을 0으로 초기화합니다.
3단계 - 문자열을 통해 루프를 시작하고 루프 내부에서 "max_char" 변수를 96으로 초기화합니다.
4단계 - 중첩 루프를 사용하여 길이가 p인 접두사에서 최대 문자를 찾습니다.
5단계 - max_char의 매핑된 값을 추가하여 접두사의 각 문자를 업데이트합니다.
7단계 - 업데이트된 문자가 "a"보다 작으면 "z"로 업데이트하세요.
8단계 - 업데이트된 문자가 "z"보다 크면 "a"로 업데이트하세요.
9단계− 마지막으로 업데이트된 문자열을 반복하여 각 문자의 빈도를 목록에 저장합니다.
10단계- 문자의 빈도를 인쇄합니다.
예
으아아아출력
으아아아시간 복잡도− O(N*N). 문자열을 탐색하기 위해 두 개의 중첩 루프를 사용하기 때문입니다.
공간 복잡성− O(1)은 문자의 빈도를 저장하기 위해 일정한 공간을 사용하기 때문입니다.
결론
입력 문자열에 대해 주어진 작업을 수행하고 업데이트된 문자열의 문자 빈도를 출력에 인쇄했습니다. 프로그래머는 목록을 사용하는 대신 C++에서 맵을 사용하여 문자 빈도를 저장할 수도 있습니다. 더 많은 연습을 위해 프로그래머는 업데이트된 문자열에서 각 문자의 누적 빈도를 인쇄해 볼 수 있습니다.
위 내용은 설명된 작업을 수행한 후 길이가 1부터 N까지인 각 접두사의 각 소문자 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!