반복 제한을 사용하여 문자열 생성

2182. 반복 제한을 사용하여 문자열 생성

난이도:중

주제: 해시 테이블, 문자열, Greedy, 힙(우선순위 대기열), 계산

문자열 s와 정수repeatLimit가 제공됩니다. s의 문자를 사용하여 repeatLimit 횟수한 행에 문자가 이상 나타나지 않도록 새 문자열peatLimitedString을 구성합니다. s의 모든 문자를 사용할 필요는 아닙니다

.

사전순으로 가장 큰repeatLimitedString이 가능한

을 반환합니다.

문자열 a는 a와 b가 다른 첫 번째 위치에 있는 경우 문자열 b보다 사전순으로 더 큽니다

. 문자열 a에는 b의 해당 문자보다 알파벳에서 나중에 나타나는 문자가 있습니다. 첫 번째 min(a.length, b.length) 문자가 다르지 않으면 긴 문자열이 사전순으로 더 큰 문자열입니다.

예 1:

• 입력:
s = "cczazcc",repeatLimit = 3
• 출력:
"zzcccac"
• 설명:
  s의 모든 문자를 사용하여 RepeatLimitedString "zzcccac"를 구성합니다.
  'a' 문자는 최대 1번 연속해서 나타납니다.
  'c' 문자는 최대 3번 연속으로 나타납니다.
  'z' 문자는 최대 2번 연속으로 나타납니다.
  따라서 어떤 문자도 연속해서peatLimit 횟수 이상 나타나지 않으며 문자열은 유효한peatLimitedString입니다.
  문자열은 가능한 한 사전순으로 가장 큰 RepeatLimitedString이므로 "zzcccac"를 반환합니다.
  문자열 "zzcccca"는 사전순으로는 더 크지만 문자 'c'가 연속으로 3번 이상 나타나므로 유효한 RepeatLimitedString이 아닙니다.

예 2:

• 입력:
s = "aababab", RepeatLimit = 2
• 출력:
"bbabaa"
• 설명:
  s의 문자 중 일부만 사용하여 RepeatLimitedString "bbabaa"를 구성합니다.
  'a' 문자는 최대 2번 연속해서 나타납니다.
  'b' 문자는 최대 2번 연속해서 나타납니다.
  따라서 어떤 문자도 연속해서peatLimit 횟수 이상 나타나지 않으며 문자열은 유효한peatLimitedString입니다.
  문자열은 가능한 한 사전순으로 가장 큰 RepeatLimitedString이므로 "bbabaa"를 반환합니다.
  문자열 "bbabaaa"는 사전순으로 더 크지만 문자 'a'가 연속으로 2번 이상 나타나므로 유효한 RepeatLimitedString이 아닙니다.

제약조건:

• ^{1 <= RepeatLimit <= s.length <= 10}5
s는 영문 소문자로 구성됩니다.

힌트:

<🎜>

1. 문자 내림차순으로 문자열 구성을 시작합니다.
2. repeatLimit에 도달하면 다음으로 큰 문자를 선택하세요.

해결책:

저희는 탐욕스러운 접근 방식을 사용하여 사전순으로 더 큰 문자에 우선순위를 두는 동시에 문자가 연속적으로 RepeatLimit을 초과하지 않도록 합니다. 이 접근 방식은 우선순위 대기열(최대 힙)을 사용하여 문자를 사전순으로 내림차순으로 처리하고 문자가 연속적으로 RepeatLimit 횟수 이상 나타나지 않도록 합니다.

해결책 설명

1. 문자 개수: 배열을 사용하여 문자열 s에 있는 각 문자의 빈도를 계산합니다.
2. 최대 힙: 최대 힙(우선순위 큐)을 사용하여 사전순으로 내림차순으로 문자를 정렬하고 추출합니다.
3. 탐욕스러운 건설:
   • 반복 제한 횟수까지 사용할 수 있는 가장 큰 문자를 추가하세요.
   • 현재 문자의 RepeatLimit에 도달하면 다음으로 가장 큰 문자로 전환하여 한 번 삽입한 후 추가 사용을 위해 첫 번째 문자를 힙에 다시 삽입합니다.
4. Edge Handling: 캐릭터를 더 이상 사용할 수 없을 때 적절하게 관리하세요.

이 솔루션을 PHP: 2182로 구현해 보겠습니다. 반복 제한을 사용하여 문자열 생성

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

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li>
<p><strong>빈도수:</strong></p>

<ul>
<li>문자열 s를 반복하여 각 문자의 발생 횟수를 계산합니다.</li>
<li>주파수를 연관 배열 $freq에 저장합니다.</li>
</ul>
</li>
<li>
<p><strong>내림차순 정렬:</strong></p>

<ul>
<li>krsort()를 사용하여 사전순으로 <strong>내림차순</strong>으로 문자를 정렬합니다.</li>
</ul>
</li>
<li>
<p><strong>결과 구축:</strong></p>

<ul>
<li>결과 문자열에 사전순으로 가장 큰 문자($char)를 계속 추가합니다.</li>
<li>문자가 반복 제한에 도달하면 일시적으로 추가를 중지하세요.</li>
<li>아직 남은 개수가 있지만 일시적으로 건너뛴 캐릭터를 보관하려면 임시 대기열을 사용하세요.</li>
</ul>
</li>
<li>
<p><strong>반복 제한 처리:</strong></p>

<ul>
<li>현재 문자가 RepeatLimit에 도달한 경우 대기열에서 사전순으로 가장 큰 다음 문자를 사용합니다.</li>
<li>나중에 계속 처리하려면 이전 문자를 빈도 맵에 다시 삽입하세요.</li>
</ul>
</li>
<li>
<p><strong>특정 케이스:</strong></p>
<ul>
<li>캐릭터는 처음에는 전체 카운트를 사용하지 못할 수 있습니다.</li>
<li>큐에서 백업 캐릭터 처리 후 현재 캐릭터 처리를 재개합니다.</li>
</ul>
</li>
</ol>

<h3>
  
  
  <strong>작동 방식</strong>
</h3>

<ol>
<li>
<strong>문자 수</strong>: $freq는 모든 문자의 발생을 추적합니다.</li>
<li>
<strong>최대 힙</strong>: SplPriorityQueue는 최대 힙으로 사용되며 문자는 ASCII 값(내림차순)에 따라 우선순위가 지정됩니다.</li>
<li>
<strong>문자열 구성</strong>:

<ul>
<li>현재 문자가 RepeatLimit에 도달한 경우 다음으로 가장 큰 문자를 가져옵니다.</li>
<li>다음으로 가장 큰 문자를 한 번 사용하고 나중에 사용할 수 있도록 이전 문자를 힙에 복원합니다.</li>
</ul>
</li>
<li>
<strong>최종 결과</strong>: 결과 문자열은peatLimit 제약 조건을 충족하는 사전순으로 가장 큰 문자열입니다.</li>
</ol>

<h3>
  
  
  <strong>예시 연습</strong>
</h3>

<p><strong>입력:</strong><br><br>
s = "cczazcc",repeatLimit = 3</p>

<p><strong>단계:</strong></p>

<ol>
<li><p>빈도수:<br><br>
['a' => 1, 'c' => 4, 'z' => 2]</p></li>
<li><p>내림차순 정렬:<br><br>
['z' => 2, 'c' => 4, 'a' => 1]</p></li>
<li>
<p>repeatLimit을 준수하면서 문자를 추가하세요.</p>

<ul>
<li>'z' → "zz" 추가(z 개수 = 0)</li>
<li>'c'를 3번 추가 → "zzccc"(c 개수 = 1)</li>
<li>'a' 추가 → "zzccca"(개수 = 0)</li>
<li>나머지 'c' 추가 → "zzcccac"</li>
</ul>
</li>
</ol>

<p><strong>출력:</strong> "zzcccac"</p>

<h3>
  
  
  <strong>시간복잡도</strong>
</h3>

<ul>
<li>
<strong>문자 빈도 계산</strong>: <em><strong>O(n)</strong></em>, 여기서 <em><strong>n</strong></em>은 문자열의 길이입니다.</li>
<li>
<strong>힙 작업</strong>: <em><strong>O(26 log 26)</strong></em>, 힙은 최대 26자를 포함할 수 있습니다.</li>
<li>
<strong>전체 복잡도</strong>: <em><strong>O(n 26 log 26) ≒ O(n)</strong></em>.</li>
</ul>

<h3>
  
  
  <strong>공간 복잡도</strong>
</h3>

<ul>
<li>
주파수 배열의 경우 <em><strong>O(26)</strong></em>입니다.</li>
<li>
<em><strong>O(26)</strong></em> 힙용</li>
</ul>

<h3>
  
  
  <strong>테스트 케이스</strong>
</h3>



<pre class="brush:php;toolbar:false"><?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>

엣지 케이스

1. s에는 하나의 고유 문자만 포함됩니다(예: "aaaaaaa",repeatLimit = 2): 출력에는 연속적으로 허용되는 만큼의 문자만 포함됩니다.
2. RepeatLimit = 1: 사용 가능한 문자 간에 출력이 번갈아 나타납니다.
3. s의 모든 문자는 고유합니다. 출력은 내림차순으로 정렬됩니다.

이 구현은 제약 조건 내에서 효율적으로 작동합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 반복 제한을 사용하여 문자열 생성의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!