배열 요소에 '+' 및 '*' 연산을 적용하여 얻을 수 있는 가장 작은 수

문제 설명

양의 정수를 포함하는 길이 "N"의 배열이 제공됩니다. 또한 "*" 및 "+" 문자만 포함하는 "N-1" 길이의 문자열이 제공됩니다. 여기서 "*"는 곱셈 연산자이고 "+"는 더하기 연산자입니다. 가장 작은 양의 정수 값을 얻기 위해 배열 요소에 대해 산술 연산을 수행하라는 요청을 받았습니다.

예

들어가세요

으아아아

출력

으아아아

지침

((1*2) + 3)의 결과값입니다.

들어가세요

으아아아

출력

으아아아

지침

9와 동일한 array[0]*array[1]을 수행하고 결과 1을 나타냅니다. 그런 다음 12와 동일한 result1을 array[2]에 추가하고 이를 result2로 나타냅니다. 다음으로 결과2를 배열 [3]에 추가합니다(15).

들어가세요

으아아아

출력

으아아아

지침

((1*3*5) + 6)의 결과값입니다.

방법 1

이 방법의 문제를 해결하기 위해 비트 마스킹을 사용하겠습니다.

두 가지 선택이 있을 때마다 비트 마스크를 사용할 수 있습니다. 여기서는 임의의 순서로 산술 연산을 적용하도록 요청하고 있지만 주어진 문자열에 대해 곱셈과 산술 연산 중에서 선택해야 합니다

따라서 비트 마스크를 사용하면 두 개의 산술 연산자를 배열하는 가능한 모든 방법을 얻을 수 있습니다. 그런 다음 각 방향에서 산술 연산을 수행하고 결과가 최소값인지 확인할 수 있습니다.

예제 입력을 통해 위의 논리를 명확하게 만들어 보겠습니다. 아래 예에서는 배열 = [1.3, 5, 6], 문자열 = "*++"입니다.

여기서 문자열 길이는 3입니다. 따라서 총 8(2^3)개의 비트 마스크, 즉 000, 001, 010, 100, 110, 101, 011, 111을 가질 수 있습니다.

이제 "1"이 "*"이고 "0"이 "+" 연산자라고 가정하면 문자열에 지정된 산술 연산자의 모든 순열을 얻을 수 있습니다.

그러나 "1"의 총 개수가 "*" 연산자의 개수와 같고, "0"의 개수가 "+" 연산자의 개수와 같은 경우에만 순열을 사용해야 합니다.

알고리즘

위 방법을 구현하려면 사용자는 다음 알고리즘을 따라야 합니다.

• 1단계 - "totalMul" 변수를 정의하고 0으로 초기화하여 문자열에 곱셈 산술 연산자의 총 개수를 저장합니다.

• 2단계 - for 루프를 사용하여 주어진 문자열을 반복합니다. 현재 문자가 "*"와 같으면 "totalMul" 변수의 값이 1씩 증가합니다.

• 3단계 - X가 문자열 길이와 같을 때 for 루프를 사용하여 가능한 모든 비트마스크를 가져옵니다. 여기서 'len'은 배열 길이이고 'len - 1'은 문자열 길이입니다.

• 4단계 - "setBitCount" 변수를 정의하여 현재 마스크에 설정된 비트 수를 저장합니다. 또한, 산술 연산의 현재 순서를 저장하기 위해 "순서" 목록이 정의됩니다.

• 5단계 - for 루프 내에서 다른 for 루프를 사용하여 현재 마스크의 총 설정된 비트 수('1')를 가져옵니다. j를 왼쪽으로 1비트만큼 이동시킨 후 I로 & 연산을 수행하여 j번째 비트가 설정되었는지 확인합니다.

• 6단계 - 현재 비트가 설정 비트인 경우 "setBitCount" 변수의 값을 늘리고 "*"를 순차 벡터에 푸시합니다. 그렇지 않으면 "+"를 순차 벡터에 푸시합니다.

• 7단계 - setBitCount의 값이 totalMul의 값과 같으면 현재 마스크를 사용하여 산술 연산을 예약할 수 있음을 의미합니다. 그렇지 않으면 다음 반복으로 이동합니다.

• 8단계 - if 문에서 "deque" 데이터 구조를 사용하여 "currentQueue"를 정의하여 배열 요소를 저장합니다.

• 9단계 - '주문' 목록을 반복합니다. 현재 문자가 '*'인 경우 대기열의 마지막 요소를 팝하고 현재 배열 인덱스의 요소와 곱합니다.

• 10단계 - "orders" 목록의 현재 문자가 "+"인 경우 현재 배열 요소를 "currentQueue"에 푸시합니다.

• 11단계 - while 루프를 사용하여 "currentQueue"에서 모든 요소를 ​​팝하고 모든 요소를 ​​합산합니다.

• 12단계 - min() 함수를 사용하여 "최소" 및 "합계" 변수에서 최소값을 구합니다.

예

으아아아

출력

으아아아

• 시간 복잡도 - O(2N-1*N), 여기서 N은 배열의 길이입니다. for 루프를 사용하여 현재 마스크에 설정된 총 비트 수를 계산하는 모든 비트 마스크를 반복하면 O(2N-1*N)입니다.

• 공간 복잡성 − O(N) 산술 연산자의 순서를 저장하기 위해 목록을 사용하기 때문입니다.

위 내용은 배열 요소에 '+' 및 '*' 연산을 적용하여 얻을 수 있는 가장 작은 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!