문자열 분할 후 최대 점수

1422. 문자열 분할 후 최대 점수

난이도: 쉬움

주제: 문자열, 접두사 합계

0과 1로 구성된 문자열 s가 주어지면 문자열을 두 개의 비어 있지 않은 하위 문자열으로 분할한 후의 최대 점수를 반환합니다(예: 왼쪽 하위 문자열 및 오른쪽 하위 문자열).

문자열을 분할한 후의 점수는 왼쪽 하위 문자열의 0 수와 오른쪽의 1 수를 더한 값입니다. 하위 문자열.

예 1:

• 입력: s = "011101"
• 출력: 5
• 설명: s를 비어 있지 않은 두 개의 하위 문자열로 분할하는 가능한 모든 방법은 다음과 같습니다.
  • 왼쪽 = "0", 오른쪽 = "11101", 점수 = 1 4 = 5
  • 왼쪽 = "01", 오른쪽 = "1101", 점수 = 1 3 = 4
  • 왼쪽 = "011", 오른쪽 = "101", 점수 = 1 2 = 3
  • 왼쪽 = "0111", 오른쪽 = "01", 점수 = 1 1 = 2
  • 왼쪽 = "01110", 오른쪽 = "1", 점수 = 2 1 = 3

예 2:

• 입력: s = "00111"
• 출력: 5
• 설명: 왼쪽 = "00", 오른쪽 = "111"일 때 최대 점수 = 2 3 = 5를 얻습니다

예 3:

• 입력: s = "1111"
• 출력: 3

제약조건:

• 2
• 문자열 s는 문자 '0'과 '1'로만 구성됩니다.

힌트:

1. 1의 접두어 합('1')을 미리 계산합니다.
2. 왼쪽에서 오른쪽으로 0의 개수('0')를 세는 것을 반복한 다음 1의 개수('1')를 위해 미리 계산된 접두어 합계를 사용합니다. 답변을 업데이트하세요.

해결책:

문자열에서 1의 접두사 합('1')을 미리 계산하여 제공되는 힌트를 활용할 수 있습니다. 솔루션을 분석하는 방법은 다음과 같습니다.

단계:

1. 1의 접두사 합: 인덱스 i의 각 요소가 문자열에서 인덱스 i까지의 1의 개수('1')를 포함하는 배열을 미리 계산합니다.
2. 문자열 반복: 각 위치 i에 대해 0부터 i까지의 하위 문자열을 "왼쪽" 하위 문자열로 처리하고, i 1부터 문자열 끝까지를 "오른쪽" 하위 문자열로 처리합니다.
   • 반복하면서 간단히 숫자를 세어 왼쪽 하위 문자열의 0을 셉니다.
   • 접두사 합계를 사용하여 오른쪽 하위 문자열의 개수를 계산합니다(문자열의 총 개수에서 분할 지점의 접두사 합계를 빼는 방식).
3. 점수 계산: 가능한 각 분할에 대해 왼쪽 하위 문자열의 0 개수와 오른쪽 하위 문자열의 1 개수로 점수를 계산합니다.
4. 최대 점수를 반환.

PHP에서 이 솔루션을 구현해 보겠습니다. 1422. 문자열 분할 후 최대 점수

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

// Test cases
$s1 = "011101";
$s2 = "00111";
$s3 = "1111";

echo "Input: $s1, Output: " . maxScore($s1) . PHP_EOL; // Output: 5
echo "Input: $s2, Output: " . maxScore($s2) . PHP_EOL; // Output: 5
echo "Input: $s3, Output: " . maxScore($s3) . PHP_EOL; // Output: 3
?>

설명:

1. 접두사 합계 계산: $prefixOneCount 배열에서 1의 접두사 합계를 계산합니다. 여기서 각 인덱스는 해당 지점까지의 1의 누적 개수를 보유합니다.

2. 가능한 분할 반복: 각 인덱스 i(0에서 n-2)를 통해 반복을 시작합니다. 여기서 문자열은 왼쪽 부분(0에서 i)과 오른쪽 부분( i 1부터 n-1까지).

   • 각 분할에 대해 왼쪽 하위 문자열($zeroCountLeft)에서 0의 개수를 셉니다.
   • 미리 계산된 $prefixOneCount를 사용하여 올바른 하위 문자열에 몇 개가 있는지 계산하세요.

3. 점수 계산: 각 분할의 점수는 왼쪽 부분의 0과 오른쪽 부분의 1의 합으로 계산됩니다. 이번 반복 중에 발생하는 최대 점수를 업데이트합니다.

4. 최종 결과: 이 함수는 모든 분할 중에 발견된 최대 점수를 반환합니다.

복잡성:

• 시간 복잡도: O(n)

  • 접두사 합계를 미리 계산하고 문자열을 반복하는 데는 모두 O(n).
  이 소요됩니다.
  • 점수를 계산하기 위해 문자열을 반복하는 데에도 O(n)이 필요합니다.
  • 따라서 총 시간 복잡도는 O(n)이며, 이는 주어진 입력 크기(n ≤ 500)에 효율적입니다.

• 공간 복잡도: O(n)

  • 접두사 합계 배열에는 O(n) 추가 공간이 필요합니다.

예:

echo maxScore("011101"); // Output: 5
echo maxScore("00111");  // Output: 5
echo maxScore("1111");   // Output: 3

이 솔루션은 최적이며 제약 조건 내에서 문제를 처리합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 문자열 분할 후 최대 점수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!