스트링의 균형을 맞추기 위한 최소 스왑 수

1963년. 스트링의 균형을 맞추는 데 필요한 최소 스왑 횟수

난이도:중

주제: 두 포인터, 문자열, 스택, 탐욕

길이 n이 짝수인 인덱스가 0인 문자열 s가 제공됩니다. 문자열은 정확히 n/2개의 여는 괄호 '['와 n/2개의 닫는 괄호 ']'로 구성됩니다.

다음과 같은 경우에만 문자열을 균형이라고 합니다.

• 빈 문자열이거나
• A와 B가 모두 균형 문자열인 AB로 작성하거나
• [C]로 쓸 수 있습니다. 여기서 C는 균형 문자열입니다.

대괄호는 아무 두 개의 인덱스 임의 횟수만큼 바꿀 수 있습니다.

균형을 만들기 위한 최소 스왑 횟수를 반환합니다.

예 1:

• 입력: s = "][]["
• 출력: 1
• 설명: 인덱스 0을 인덱스 3으로 교체하여 문자열 균형을 맞출 수 있습니다.
  • 결과 문자열은 "[[]]"입니다.

예 2:

• 입력: s = "]]][[["
• 출력: 2
• 설명: 문자열 균형을 맞추려면 다음을 수행할 수 있습니다.
  • 인덱스 0을 인덱스 4로 바꿉니다. s = "[]][][".
  • 인덱스 1을 인덱스 5로 바꿉니다. s = "[[][]]".
  • 결과 문자열은 "[[][]]"입니다.

예 3:

• 입력: s = "[]"
• 출력: 0
• 설명: 문자열이 이미 균형을 이루고 있습니다.

제약조건:

• n == s.길이
• 2 6
• n은 짝수입니다.
• s[i]는 '[' 또는 ']'입니다.
• 여는 괄호 '['의 개수는 n/2이고, 닫는 괄호 ']'의 개수는 n/2입니다.

힌트:

1. 문자열을 반복하면서 각 단계에서 여는 괄호와 닫는 괄호의 수를 추적하세요.
2. 닫는 괄호의 개수가 더 많아지면 바꿔야 합니다.
3. s 끝에 가장 가까운 여는 괄호로 바꿉니다.

해결책:

제약 조건을 고려할 때 효율적인 두 포인터 접근 방식을 사용할 수 있습니다.

접근하다:

1. 트랙 균형: 문자열을 반복하면서 여는 괄호와 닫는 괄호 사이의 균형을 추적할 수 있습니다.

   • '['을 만나면 잔액을 늘립니다.
   • ']'가 나타나면 잔액을 줄입니다.

2. 불균형 식별: 잔액이 음수가 되면 문자열의 해당 지점에 여는 괄호 '['보다 닫는 괄호 ']'가 더 많다는 것을 나타냅니다. 여기서 문자열의 균형을 맞추기 위해 괄호를 바꿔야 합니다.

3. 카운트 스왑: 불균형을 수정하려면:

   • 반복 중에 관찰된 최대 불균형을 추적하려면 max_imbalance 카운터를 유지하세요.
   • 필요한 스왑 수는 (max_imbalance 1) / 2와 동일하며, 이는 문자열 균형을 맞추는 데 필요한 최소 스왑 수를 효과적으로 제공합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 1963. 스트링 균형을 맞추기 위한 최소 스왑 횟수

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

// Example usage:
$s1 = "][][";
echo minSwaps($s1); // Output: 1

$s2 = "]]][[[";
echo minSwaps($s2); // Output: 2

$s3 = "[]";
echo minSwaps($s3); // Output: 0
?>

설명:

1. 잔액 추적:

   • Balance는 '['와 ']' 개수의 차이를 추적합니다.
   • 잔액이 마이너스가 되면 그 시점에서 '['보다 ']'가 더 많다는 의미입니다.

2. 최대 불균형 계산:

   • max_imbalance는 반복 중에 발생한 가장 큰 불균형을 저장합니다.
   • balance가 음수가 되면 max_imbalance 또는 -balance 중 더 큰 값으로 max_imbalance를 업데이트하세요.

3. 스왑 계산:

   • 불균형을 해결하기 위해 필요한 최소 스왑은 (max_imbalance 1) / 2입니다.

시간 복잡도:

• 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. max_imbalance를 결정하기 위해 문자열을 한 번 반복합니다.
• 균형과 최대 불균형을 추적하기 위해 몇 가지 변수를 사용하므로 공간 복잡도는 O(1)입니다.

이 솔루션을 사용하면 대규모 입력에도 제약 조건을 충족할 수 있습니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 스트링의 균형을 맞추기 위한 최소 스왑 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!