모든 요소를 ​​표시한 후 배열의 점수 찾기

2593. 모든 요소를 ​​표시한 후 배열의 점수 찾기

난이도:중

주제: 힙(우선순위 큐), 정렬, 배열, 시뮬레이션, 해시 테이블, Ordered Set, Ordered Map, Greedy, Monotonic Stack, 슬라이딩 윈도우, 두 포인터, 스택, 큐, 비트 조작, 분할 정복, 동적 프로그래밍, 이중 연결 목록, 데이터 스트림, 기수 정렬, 역추적, 비트마스크, 트리, 디자인, 해시 함수, 문자열, 반복자, 계산 정렬, 연결 목록

양의 정수로 구성된 배열 num이 제공됩니다.

점수 = 0부터 시작하여 다음 알고리즘을 적용합니다.

• 표시되지 않은 배열 중 가장 작은 정수를 선택하세요. 동점인 경우 지수가 가장 작은 것을 선택하세요.
• 선택한 정수 값을 점수에 추가하세요.
• 선택한 요소와 인접한 두 요소(존재하는 경우)를 표시합니다.
• 모든 배열 요소가 표시될 때까지 반복합니다.

위 알고리즘을 적용하여 얻은 점수를 반환합니다.

예 1:

• 입력: 숫자 = [2,1,3,4,5,2]
• 출력: 7
• 설명: 요소를 다음과 같이 표시합니다.
  • 1은 표시되지 않은 가장 작은 요소이므로 이 요소와 인접한 두 요소인 [2,1,3,4,5,2]로 표시합니다.
  • 2는 표시되지 않은 가장 작은 요소이므로 이 요소와 왼쪽 인접 요소인 [2,1,3,4,5,2]로 표시합니다.
  • 4는 표시되지 않은 유일한 요소이므로 [2,1,3,4,5,2]로 표시합니다.
  • 저희 점수는 1 2 4 = 7입니다.

예 2:

• 입력: 숫자 = [2,3,5,1,3,2]
• 출력: 5
• 설명: 요소를 다음과 같이 표시합니다.
  • 1은 표시되지 않은 가장 작은 요소이므로 이 요소와 인접한 두 요소인 [2,3,5,1,3,2]로 표시합니다.
  • 2는 표시되지 않은 가장 작은 요소입니다. 두 개가 있으므로 가장 왼쪽에 있는 것을 선택하여 인덱스 0에 있는 것을 표시하고 오른쪽에 인접한 요소인 [2,3,5,1,3, 2].
  • 2는 표시되지 않은 유일한 요소이므로 [2,3,5,1,3,2]로 표시합니다.
  • 저희 점수는 1 2 2 = 5입니다.

제약조건:

• 1 5
• 1 6

힌트:

1. 요소와 인접 요소를 표시하는 과정을 시뮬레이션해 보세요.
2. 이미 표시된 요소가 있으면 건너뛰세요.

해결책:

정렬된 배열이나 우선순위 큐를 사용하여 표시되지 않은 가장 작은 요소를 추적함으로써 표시 프로세스를 효율적으로 시뮬레이션할 수 있습니다. 따라서 다음 접근 방식을 사용할 수 있습니다.

계획:

1. 입력 구문 분석: 배열 번호를 읽고 점수 및 채점 상태에 대한 변수를 초기화합니다.
2. 힙(우선순위 대기열):
   • 최소 힙을 사용하여 각 단계에서 표시되지 않은 가장 작은 요소를 효율적으로 추출합니다.
   • 각 요소를 인덱스(값, 인덱스)와 함께 힙에 삽입하여 가장 작은 인덱스를 기준으로 연결을 관리합니다.
3. 마킹 요소:
   • 표시된 배열을 유지하여 요소와 인접한 요소가 표시되었는지 추적합니다.
   • 힙의 요소를 처리할 때 이미 표시된 요소는 건너뜁니다.
   • 현재 요소와 두 개의 인접 요소(존재하는 경우)를 표시합니다.
   • 현재 요소의 값을 점수에 추가합니다.
4. 반복: 모든 요소가 표시될 때까지 계속합니다.
5. 출력: 누적 점수를 반환합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2593. 모든 요소를 ​​표시한 후 배열의 점수 찾기

<?php /**
 * @param Integer[] $nums
 * @return Integer
 */
function findScore($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [2, 1, 3, 4, 5, 2];
$nums2 = [2, 3, 5, 1, 3, 2];

echo findScore($nums1) . "\n"; // Output: 7
echo findScore($nums2) . "\n"; // Output: 5
?>

설명:

1. 힙 구성:

   • usort 함수는 값을 기준으로 배열을 정렬하고 값이 묶인 경우 인덱스를 기준으로 정렬합니다.
   • 이렇게 하면 항상 가장 작은 인덱스로 표시되지 않은 가장 작은 요소를 처리할 수 있습니다.

2. 마킹 로직:

   • 표시되지 않은 각 요소에 대해 표시된 배열을 사용하여 해당 요소와 인접 요소를 표시합니다.
   • 이렇게 하면 이전에 표시된 요소를 효율적으로 건너뛸 수 있습니다.

3. 시간 복잡성:

   • 힙 정렬: O(n log n)
   • 힙 처리: O(n)
   • 전체: O(n log n), 이는 주어진 제약 조건에 효율적입니다.

4. 공간 복잡성:

   • 표시된 배열: O(n)
   • 힙: O(n)
   • 합계: O(n)

이 솔루션은 제약 조건을 충족하며 대규모 입력에 효율적으로 작동합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 모든 요소를 ​​표시한 후 배열의 점수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!