목차
방법 1
알고리즘
출력
백엔드 개발 C++ 문자가 하위 문자열과 동일하고 빈도 차이가 최대 K인 가장 긴 하위 시퀀스

문자가 하위 문자열과 동일하고 빈도 차이가 최대 K인 가장 긴 하위 시퀀스

Sep 09, 2023 am 09:09 AM
성격 빈도 하위 순서

문자가 하위 문자열과 동일하고 빈도 차이가 최대 K인 가장 긴 하위 시퀀스

이 문제에서는 연속된 문자를 포함하고 모든 문자의 빈도 차이가 K를 초과하지 않는 부분 수열의 최대 길이를 구합니다.

주어진 문자열의 가능한 모든 하위 시퀀스를 찾아 출력을 얻으려면 각 문자가 연속적으로 포함되어 있는지 그리고 최대 빈도 차이가 있는지 확인해야 합니다.

문제 설명- 알파벳 소문자를 포함하는 문자열 알파가 제공됩니다. 추가적으로 양의 정수 K가 주어졌습니다. 다음 규칙을 따르도록 주어진 문자열의 하위 시퀀스의 최대 길이를 찾아야 합니다.

  • 특정 문자는 모두 연속되어야 합니다.

  • 문자 빈도의 차이는 K보다 클 수 없습니다.

들어가세요

으아아아

출력

으아아아

설명 - "pppqrs" 하위 시퀀스를 사용할 수 있습니다. 최대 문자 빈도는 3이고 최소 문자 빈도는 1입니다. 따라서 차이는 2입니다. 그리고 모든 문자가 연속적으로 포함됩니다.

들어가세요

으아아아

출력

으아아아

설명 - "abbbc" 부분 수열을 사용할 수 있습니다.

들어가세요

으아아아

출력

으아아아

설명 - "nnnnnnn" 하위 시퀀스를 사용할 수 있습니다.

방법 1

이 방법에서는 재귀 함수를 사용하여 주어진 길이의 모든 하위 시퀀스를 찾습니다. 또한 하위 시퀀스에 모든 문자가 연속적으로 포함되어 있는지 확인하는 함수를 정의합니다. 최대 및 최소 주파수 차이를 계산하기 위해 맵 데이터 구조를 사용합니다.

알고리즘

1단계 - "f" 맵을 정의하여 문자의 빈도를 저장합니다.

2단계 - 시작이 임시 문자열의 길이와 같고 문자열 길이가 0보다 큰 경우 다음 단계를 따르세요.

3단계 - "minf" 및 "maxf" 변수를 초기화하여 최소 및 최대 주파수를 저장합니다.

4단계 - 지도를 지우고 지도에 있는 각 캐릭터의 빈도를 저장하세요.

5단계 - 지도 값을 반복하면서 최대 및 최소 빈도 값을 찾습니다.

6단계 - 최대 및 최소 주파수 차이가 K보다 작거나 같은 경우 문자열에 연속된 문자가 포함되어 있는지 확인하세요.

6.1단계 - checkForContinously() 함수에서 "pos" 맵을 정의하여 특정 문자의 마지막 위치를 저장합니다.

6.2단계 - 문자열을 반복합니다. 현재 캐릭터가 맵에 존재하고 캐릭터의 현재 위치와 마지막 위치의 차이가 1 미만인 경우 마지막 위치를 업데이트합니다. 그렇지 않으면 false를 반환합니다.

6.3단계 - 캐릭터가 존재하지 않으면 지도에 캐릭터를 추가하세요.

6.4단계 - 마지막으로 true를 반환합니다.

7단계 - 문자열에 연속 문자가 포함되어 있고 빈도 차이가 K보다 작은 경우 'maxi' 값이 현재 하위 시퀀스의 길이보다 작으면 'maxi' 값을 업데이트합니다. p>

8단계 - 현재 문자를 제외하고 재귀 호출을 합니다.

9단계 - 현재 문자를 임시 문자열 끝에 추가합니다. 또한 업데이트된 "tmp" 문자열을 사용하여 재귀 호출을 수행합니다.

으아아아

출력

으아아아

시간 복잡도 - O(N*2N), 여기서 O(N)은 연속 문자를 확인하고 O(2N)은 모든 하위 시퀀스를 찾습니다.

공간 복잡도 - 임시 하위 시퀀스를 저장하는 O(N)입니다.

우리는 주어진 문자열의 모든 하위 시퀀스를 찾기 위해 간단한 방법을 사용합니다. 그러나 이는 시간이 많이 소요됩니다. 큰 문자열 문제를 해결하기 위해 이 방법을 사용하지 않는 것이 좋습니다.

위 내용은 문자가 하위 문자열과 동일하고 빈도 차이가 최대 K인 가장 긴 하위 시퀀스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

성능, 메모리 빈도 또는 타이밍에 더 큰 영향을 미치는 것은 무엇입니까? 성능, 메모리 빈도 또는 타이밍에 더 큰 영향을 미치는 것은 무엇입니까? Feb 19, 2024 am 08:58 AM

메모리는 컴퓨터에서 가장 중요한 구성 요소 중 하나이며 컴퓨터의 성능과 안정성에 큰 영향을 미칩니다. 메모리를 선택할 때 사람들은 타이밍과 빈도라는 두 가지 중요한 매개변수에 초점을 맞추는 경향이 있습니다. 그렇다면 메모리 성능에 있어 타이밍과 빈도 중 어느 것이 더 중요한가요? 먼저 타이밍(Timing)과 주파수(Frequency)의 개념을 이해해보자. 타이밍이란 메모리 칩이 데이터를 수신하고 처리하는 데 필요한 시간 간격을 의미합니다. 일반적으로 CL 값(CASLatency)으로 표시됩니다. CL 값이 작을수록 메모리 처리 속도가 빨라집니다. 주파수는 이내

java의 Character.isDigit() 함수를 사용하여 문자가 숫자인지 확인합니다. java의 Character.isDigit() 함수를 사용하여 문자가 숫자인지 확인합니다. Jul 27, 2023 am 09:32 AM

Java의 Character.isDigit() 함수를 사용하여 문자가 숫자인지 확인합니다. 문자는 컴퓨터 내부에서 ASCII 코드 형식으로 표시됩니다. 그 중 숫자 0~9에 해당하는 아스키코드 값은 각각 48~57이다. 문자가 숫자인지 확인하려면 Java의 Character 클래스에서 제공하는 isDigit() 메서드를 사용할 수 있습니다. isDigit() 메소드는 Character 클래스에 속합니다.

Word에서 화살표를 입력하는 방법 Word에서 화살표를 입력하는 방법 Apr 16, 2023 pm 11:37 PM

자동 고침을 사용하여 Word에서 화살표를 입력하는 방법 Word에서 화살표를 입력하는 가장 빠른 방법 중 하나는 미리 정의된 자동 고침 바로 가기를 사용하는 것입니다. 특정 문자 시퀀스를 입력하면 Word에서는 자동으로 해당 문자를 화살표 기호로 변환합니다. 이 방법을 사용하면 다양한 화살표 스타일을 그릴 수 있습니다. 자동 고침을 사용하여 Word에서 화살표를 입력하려면 문서에서 화살표를 표시할 위치로 커서를 이동합니다. 다음 문자 조합 중 하나를 입력하십시오. 입력한 내용을 화살표 기호로 수정하지 않으려면 키보드의 백스페이스 키를 눌러

Microsoft Excel에서 위 첨자 및 아래 첨자 서식 옵션을 적용하는 방법 Microsoft Excel에서 위 첨자 및 아래 첨자 서식 옵션을 적용하는 방법 Apr 14, 2023 pm 12:07 PM

위 첨자는 일반 텍스트 줄보다 약간 위에 설정해야 하는 문자 또는 숫자입니다. 예를 들어, 1st를 써야 한다면 문자 st는 문자 1보다 약간 높아야 합니다. 마찬가지로 아래 첨자는 문자 그룹 또는 단일 문자이므로 일반 텍스트 수준보다 약간 낮게 설정해야 합니다. 예를 들어, 화학식을 작성할 때 일반 문자 줄 아래에 숫자를 배치해야 합니다. 다음 스크린샷은 위 첨자 및 아래 첨자 형식의 몇 가지 예를 보여줍니다. 어려운 작업처럼 보일 수도 있지만 텍스트에 위 첨자 및 아래 첨자 서식을 적용하는 것은 실제로 매우 간단합니다. 이 기사에서는 위 첨자 또는 아래 첨자를 사용하여 텍스트 서식을 쉽게 지정하는 방법을 몇 가지 간단한 단계로 설명합니다. 이 기사를 재미있게 읽으셨기를 바랍니다. Excel에서 위 첨자를 적용하는 방법

iPhone 및 Mac에서 도 기호와 같은 확장 문자를 어떻게 입력합니까? iPhone 및 Mac에서 도 기호와 같은 확장 문자를 어떻게 입력합니까? Apr 22, 2023 pm 02:01 PM

실제 또는 숫자 키보드는 표면에 제한된 수의 문자 옵션을 제공합니다. 하지만 iPhone, iPad, Mac에서는 여러 가지 방법으로 악센트 부호가 있는 문자, 특수 문자 등에 접근할 수 있습니다. 표준 iOS 키보드를 사용하면 대문자와 소문자, 표준 숫자, 구두점 및 문자에 빠르게 액세스할 수 있습니다. 물론 그 외에도 많은 캐릭터들이 있습니다. 발음 구별 부호가 있는 문자부터 거꾸로 된 물음표까지 선택할 수 있습니다. 숨겨진 특별한 캐릭터를 우연히 발견했을 수도 있습니다. 그렇지 않은 경우 iPhone, iPad 및 Mac에서 액세스하는 방법은 다음과 같습니다. iPhone 및 iPad에서 확장 문자에 액세스하는 방법 iPhone 또는 iPad에서 확장 문자를 얻는 방법은 매우 간단합니다. "정보"에서는 "

ASUS TUF Z790 Plus는 ASUS MCP79 메모리 주파수와 호환됩니다. ASUS TUF Z790 Plus는 ASUS MCP79 메모리 주파수와 호환됩니다. Jan 03, 2024 pm 04:18 PM

ASUS tufz790plus는 메모리 주파수를 지원합니다. ASUS TUFZ790-PLUS 마더보드는 듀얼 채널 DDR4 메모리를 지원하고 최대 64GB의 메모리를 지원하는 고성능 마더보드입니다. 메모리 주파수는 최대 4800MHz로 매우 강력합니다. 지원되는 특정 메모리 주파수에는 2133MHz, 2400MHz, 2666MHz, 2800MHz, 3000MHz, 3200MHz, 3600MHz, 3733MHz, 3866MHz, 4000MHz, 4133MHz, 4266MHz, 4400MHz, 4533MHz, 4600MHz, 4733MHz 및 . 일상적인 사용이든 고성능 요구이든

matplotlib에서 한자를 표시하는 올바른 방법 matplotlib에서 한자를 표시하는 올바른 방법 Jan 13, 2024 am 11:03 AM

matplotlib에서 한자를 올바르게 표시하는 것은 많은 중국 사용자가 자주 겪는 문제입니다. 기본적으로 matplotlib는 영어 글꼴을 사용하므로 중국어 문자를 올바르게 표시할 수 없습니다. 이 문제를 해결하려면 올바른 중국어 글꼴을 설정하고 이를 matplotlib에 적용해야 합니다. 다음은 matplotlib에서 중국어 문자를 올바르게 표시하는 데 도움이 되는 몇 가지 특정 코드 예제입니다. 먼저 필수 라이브러리를 가져와야 합니다. importmatplot

ddr4의 주파수를 확인하는 방법 ddr4의 주파수를 확인하는 방법 Feb 01, 2024 am 09:42 AM

ddr4 메모리 스틱이 컴퓨터에 미치는 가장 큰 영향은 주파수이며, 많은 사용자는 주파수를 확인하는 방법을 모릅니다. 실제로 CPU 소프트웨어를 통해 확인할 수 있으며 모든 측면의 정보가 매우 자세하게 표시됩니다. ddr4의 주파수를 확인하는 방법: 1. 먼저 소프트웨어를 통해 확인해야 합니다. CPU-z를 사용하여 확인할 수 있습니다. 2. 완료되면 열고 "메모리"를 클릭하세요. 3. 이때, 아래와 같이 "주파수"를 확인할 수 있습니다.

See all articles