. 괄호를 추가하는 다양한 방법

241. 괄호를 추가하는 다양한 방법

난이도:중

주제: 수학, 문자열, 동적 프로그래밍, 재귀, 메모

숫자와 연산자로 구성된 문자열 표현식이 주어지면 숫자와 연산자를 그룹화하는 다양한 방법을 계산하여 가능한 모든 결과를 반환합니다. 어떤 순서로든 답변을 보내실 수 있습니다.

출력값이 32비트 정수에 맞고, 서로 다른 결과의 개수가 10⁴을 초과하지 않도록 테스트 케이스가 생성되었습니다.

예 1:

• 입력: 식 = "2-1-1"
• 출력: [0,2]
• 설명:

  ((2-1)-1) = 0
  (2-(1-1)) = 2

예 2:

• 입력: 표현식 = "2*3-4*5"
• 출력: [-34,-14,-10,-10,10]
• 설명:

  (2*(3-(4*5))) = -34
  ((2*3)-(4*5)) = -14
  ((2*(3-4))*5) = -10
  (2*((3-4)*5)) = -10
  (((2*3)-4)*5) = 10

제약조건:

• 1 <= 표현식.길이 <= 20
• 표현식은 숫자와 '+', '-', '*' 연산자로 구성됩니다.
• 입력 표현식의 모든 정수 값은 [0, 99] 범위에 있습니다.
• 입력 표현식의 정수 값에는 기호를 나타내는 '-' 또는 '+'가 선행되지 않습니다.

해결책:

memoization과 결합된 재귀를 사용하여 하위 표현식에 대해 이전에 계산된 결과를 저장할 수 있습니다. 이는 중복 계산을 방지하고 솔루션을 최적화하기 때문입니다.

접근하다:

1. 재귀:

   • 문자열(+, -, *)의 각 연산자에 대해 해당 연산자에서 표현식을 분할합니다.
   • 식의 왼쪽과 오른쪽 부분을 재귀적으로 계산합니다.
   • 연산자를 사용하여 두 부분의 결과를 결합합니다.

2. 메모:

   • 동일한 하위 표현식을 여러 번 다시 계산하지 않으려면 하위 표현식의 결과를 연관 배열에 저장하세요.

3. 기본 사례:

   • 식에 숫자만 포함된 경우(즉, 연산자 없음) 해당 숫자를 결과로 반환합니다.

예제 연습:

입력 "2*3-4*5"의 경우:

• *에서 분할 -> 2 및 3-4*5
  • 3-4*5와 2를 재귀적으로 계산한 다음 결합합니다.
• - ->에서 분할 2*3 및 4*5
  • 각각을 재귀적으로 계산하고 결합합니다.
• 다른 분할도 마찬가지입니다.

이 솔루션을 PHP로 구현해 보겠습니다. 241. 괄호를 추가하는 다양한 방법

<?php
class Solution {

    /**
     * @var array
     */
    private $memo = [];

    /**
     * @param String $expression
     * @return Integer[]
     */
    public function diffWaysToCompute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $expression
     * @return array|mixed
     */
    private function compute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
$expression1 = "2-1-1";
$expression2 = "2*3-4*5";
print_r($solution->diffWaysToCompute($expression1)); // Output: [0, 2]
print_r($solution->diffWaysToCompute($expression2)); // Output: [-34, -14, -10, -10, 10]
?>

설명:

1. 메모이제이션: $memo 배열은 중복 계산을 피하기 위해 각 표현식에 대해 계산된 결과를 저장합니다.
2. 기본 사례: 식이 숫자인 경우 정수로 변환되어 결과에 추가됩니다.
3. 재귀적 분할: 표현식의 각 연산자를 왼쪽과 오른쪽 부분으로 분할하고 두 부분의 결과를 재귀적으로 계산한 다음 연산자를 기준으로 결합합니다.
4. 사용 예: diffWaysToCompute 함수는 예제 표현식으로 테스트되어 솔루션을 확인합니다.

이 접근 방식을 사용하면 메모 기능을 활용하여 중복 계산을 방지함으로써 가능한 모든 결과를 효율적으로 계산할 수 있습니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 . 괄호를 추가하는 다양한 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!