왼쪽과 오른쪽에서 각 문자의 K개를 가져옵니다.

2516. 왼쪽과 오른쪽에서 각 문자의 K개를 가져옵니다

난이도:중

주제: 해시 테이블, 문자열, 슬라이딩 윈도우

문자 'a', 'b', 'c'와 음수가 아닌 정수 k로 구성된 문자열 s가 제공됩니다. 매분마다 s의 가장 왼쪽 문자 또는 s의 가장 오른쪽 문자

를 사용할 수 있습니다.

각 문자의 최소k를 가져오는 데 필요한 최소분을 반환하거나, 각각의 k를 가져오는 것이 불가능하면 -1을 반환합니다. 캐릭터.

예 1:

• 입력: s = "aabaaaacaabc", k = 2
• 출력: 8
• 설명: s 왼쪽에서 세 글자를 가져옵니다. 이제 두 개의 'a' 문자와 하나의 'b' 문자가 있습니다.
  • s 오른쪽에서 5자를 가져옵니다. 이제 4개의 'a' 문자, 2개의 'b' 문자, 2개의 'c' 문자가 있습니다.
  • 총 3 5 = 8분이 소요됩니다.
  • 필요한 최소 시간은 8분이라는 것이 입증되었습니다.

예 2:

• 입력: s = "a", k = 1
• 출력: -1
• 설명: 'b' 또는 'c' 중 하나를 취할 수 없으므로 -1을 반환합니다.

제약조건:

• 1 5
• s는 'a', 'b', 'c' 문자로만 구성됩니다.
• 0

힌트:

1. 각 문자의 빈도를 세어보고 가능한지 확인하는 것부터 시작하세요.
2. 왼쪽에서 x자를 가져오려면 오른쪽에서 가져와야 하는 최소 문자 수는 얼마입니까? 0 ≤ x ≤ s.length 범위의 모든 x 값에 대해 이를 찾아보세요.
3. 동일한 정보를 여러 번 계산하지 않으려면 두 포인터 접근 방식을 사용하세요.

해결책:

두 개의 포인터가 있는 슬라이딩 윈도우 기술을 사용하여 왼쪽과 오른쪽 모두에서 각 문자('a', 'b', 'c')의 최소 k개를 가져오는 데 필요한 최소 시간(분)을 찾을 수 있습니다. 문자열입니다.

문제 분석:

• 'a', 'b', 'c'만 포함하는 문자열 s가 제공됩니다.
• 문자열의 가장 왼쪽 또는 가장 오른쪽 문자에서 각 문자를 k개 이상 가져와야 합니다.
• 이를 달성하는 데 필요한 최소 시간을 결정하거나 불가능할 경우 -1을 반환해야 합니다.

접근하다:

1. 초기 점검:

   • k == 0이면 문자가 필요하지 않으므로 0을 직접 반환할 수 있습니다.
   • k가 문자열의 문자 발생 횟수를 초과하는 경우 즉시 -1을 반환합니다.

2. 빈도수:

   • 각 문자의 k개를 수집하는 것이 가능하도록 하려면 문자열 s에 'a', 'b' 및 'c'가 몇 번 나타나는지 세어야 합니다.

3. 슬라이딩 윈도우 기법:

   • 두 개의 포인터(왼쪽 및 오른쪽)를 사용하는 슬라이딩 창 방식을 사용합니다.
   • 두 개의 포인터를 유지하고 문자열 양쪽 끝에서 밀어서 필요한 문자를 수집합니다.
   • 왼쪽에서 가져온 모든 문자 수에 대해 요구 사항을 충족하기 위해 오른쪽에서 가져와야 하는 최소 문자 수를 계산합니다.

4. 최적화:

   • 각 창마다 문자 수를 반복적으로 다시 계산하는 대신 창을 확장하거나 축소할 때 문자 수를 추적할 수 있습니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2516. 왼쪽과 오른쪽에서 각 문자의 K개를 가져옵니다

<?php
/**
 * @param String $s
 * @param Integer $k
 * @return Integer
 */
function takeCharacters($s, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
echo takeCharacters("aabaaaacaabc", 2);  // Output: 8

// Example 2
echo takeCharacters("a", 1);  // Output: -1
?>

설명:

1. 초기 설정:

   • 각 문자 중 k개 이상을 수집할 수 있도록 전체 문자열에서 'a', 'b', 'c'의 발생 횟수를 계산합니다.
   • 문자 수가 k보다 작으면 -1을 반환합니다.

2. 슬라이딩 창:

   • 두 개의 포인터(왼쪽과 오른쪽)를 사용하여 양쪽 끝에서 슬라이딩 창을 만듭니다.
   • 오른쪽 포인터를 움직여 창을 확장하고 만나는 문자 수를 늘립니다.
   • 현재 창에 k개 이상의 문자가 있으면 창을 왼쪽에서 축소하여 분(사용되는 문자)을 최소화하려고 합니다.

3. 시간 최소화:

   • 모든 유형의 k자를 수집할 때마다 창 크기를 비교하여 필요한 최소 시간(분)을 추적합니다.

시간 복잡도:

• 초기 문자 수 계산에는 O(n)이 소요됩니다.
• 왼쪽 및 오른쪽 포인터가 모두 문자열을 가로질러 한 번 이동하므로 슬라이딩 창 작업에는 O(n)이 소요됩니다.
• 전체 시간 복잡도는 O(n)입니다.

엣지 케이스:

• k == 0이면 0을 반환합니다.
• 각 문자의 k개를 가져오는 것이 불가능하면 -1을 반환합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 왼쪽과 오른쪽에서 각 문자의 K개를 가져옵니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!