유효한 쌍 배열

2097. 유효한 쌍 배열

난이도:어려움

주제: 깊이 우선 탐색, 그래프, 오일러 회로

쌍[i] = [starti, end_i]인 _0-인덱스 2D 정수 배열 쌍이 제공됩니다. 쌍의 배열은 모든 인덱스 i에 대해 1 <= i < pair.length, 끝i-1 == 시작_i.

모든 유효한 쌍 배열을 반환합니다.

참고

: 유효한 쌍 배열이 존재하도록 입력이 생성됩니다.

예 1:

입력:
• 쌍 = [[5,1],[4,5],[11,9],[9,4]]
출력:
• [[11,9],[9,4],[4,5],[5,1]]
설명:
• 이것은 endi-1가 항상 start_i와 같기 때문에 유효한 배열입니다. 끝
  0
  • = 9 == 9 = 시작₁ 끝
  1
  • = 4 == 4 = 시작₂ 끝
  2
  • = 5 == 5 = 시작₃

예 2:

입력:
• 쌍 = [[1,3],[3,2],[2,1]]
출력:
• [[1,3],[3,2],[2,1]]
설명:
• 이것은 endi-1가 항상 start_i와 같기 때문에 유효한 배열입니다. 종료
  0
  • = 3 == 3 = 시작₁ 끝
  1
  • = 2 == 2 = 시작₂ [[2,1],[1,3],[3,2]] 및 [[3,2],[2,1],[1,3]] 배열도 유효합니다.

예 3:

입력:
• 쌍 = [[1,2],[1,3],[2,1]]
출력:
• [[1,2],[2,1],[1,3]]
설명:
• 이것은 endi-1가 항상 start_i와 같기 때문에 유효한 배열입니다. 종료
  0
  • = 2 == 2 = 시작₁ 끝
  1
  • = 1 == 1 = 시작₂

제약조건:

1 <= 쌍.길이 <= 10

5
• 쌍[i].length == 2
• 0 <= 시작
i
• , 종료_i <= 10₉ 시작
i
• != end_i 완전히 똑같은 쌍은 없습니다.
• 유효한 쌍 배열이
존재합니다
• .

힌트:

이것을 그래프 문제로 변환해 주실 수 있나요?

1. 쌍을 모서리로, 각 숫자를 노드로 간주하세요.
2. 이 그래프의 오일러 경로를 찾아야 합니다. Hierholzer의 알고리즘을 사용할 수 있습니다.

해결책:

그래프 이론에서는 오일러 경로 문제로 접근할 수 있습니다. 이 경우 쌍은 간선으로 처리될 수 있으며 쌍 내의 값(시작 및 끝)은 노드로 처리될 수 있습니다. 모든 모서리를 정확히 한 번씩 사용하는 경로인 오일러 경로를 찾아야 하며, 한 모서리의 끝은 다음 모서리의 시작과 일치해야 합니다.

주요 단계:

1. 그래프 표현: 쌍의 각 고유 번호는 노드가 되고, 각 쌍은 시작[i]에서 끝[i]까지의 가장자리가 됩니다.
2. 오일러 경로 기준:
   • 홀수 차수를 갖는 노드가 정확히 두 개 있고 나머지는 짝수 차수를 가져야 하는 경우 오일러 경로가 존재합니다.
   • 그래프가 연결되어 있는지 확인해야 합니다(문제 설명에서 이를 보장하지만).
3. Hierholzer의 알고리즘: 이 알고리즘은 오일러 경로를 찾는 데 사용할 수 있습니다. 여기에는 다음이 포함됩니다.
   • 홀수 차수(있는 경우)의 노드에서 시작합니다.
   • 가장자리를 탐색하여 방문한 것으로 표시합니다.
   • 사용되지 않은 가장자리가 있는 노드에 도달하면 모든 가장자리가 사용될 때까지 계속 순회합니다.

계획:

• 인접 목록(각 노드와 연결된 노드)을 저장하기 위해 해시 맵을 사용하여 그래프를 작성합니다.
• 각 노드의 차수(내차 및 외차)를 추적합니다.
• Hierholzer의 알고리즘을 사용하여 오일러 경로를 찾습니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2097. 유효한 쌍 배열

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

// Example usage:
$pairs1 = [[5, 1], [4, 5], [11, 9], [9, 4]];
$pairs2 = [[1, 3], [3, 2], [2, 1]];
$pairs3 = [[1, 2], [1, 3], [2, 1]];

print_r(validArrangement($pairs1)); // Output: [[11, 9], [9, 4], [4, 5], [5, 1]]
print_r(validArrangement($pairs2)); // Output: [[1, 3], [3, 2], [2, 1]]
print_r(validArrangement($pairs3)); // Output: [[1, 2], [2, 1], [1, 3]]
?>




</p>
<h3>
  
  
  설명:
</h3>

<ol>
<li>
<p><strong>그래프 구성</strong>:</p>

<ul>
<li>각 키가 시작 노드이고 값이 끝 노드 목록인 인접 목록을 사용하여 그래프를 작성합니다.</li>
<li>또한 각 노드의 진출 차수와 진입 차수를 유지하여 오일러 경로의 시작 노드를 찾는 데 도움이 됩니다.</li>
</ul>
</li>
<li>
<p><strong>시작 노드 찾기</strong>:</p>

<ul>
<li>오일러 경로는 진출 차수가 진입 차수보다 1만큼 큰 노드에서 시작합니다(해당 노드가 있는 경우).</li>
<li>그러한 노드가 존재하지 않으면 그래프는 균형을 이루며 어떤 노드에서든 시작할 수 있습니다.</li>
</ul>
</li>
<li>
<p><strong>Hierholzer의 알고리즘</strong>:</p>

<ul>
<li>startNode에서 시작하여 가장자리를 반복적으로 따라가며 인접 목록에서 제거하여 방문한 것으로 표시합니다.</li>
<li>더 이상 나가는 에지가 없는 노드에 도달하면 역추적하여 결과를 작성합니다.</li>
</ul>
</li>
<li>
<p><strong>결과 반환</strong>:</p>
<ul>
<li>역추적 방식 때문에 결과가 역순으로 구성되어 있어서 마지막에 역순으로 진행합니다.</li>
</ul>
</li>
</ol>

<h3>
  
  
  예제 출력:
</h3>



<pre class="brush:php;toolbar:false"><?php
/**
 * @param Integer[][] $pairs
 * @return Integer[][]
 */
function validArrangement($pairs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$pairs1 = [[5, 1], [4, 5], [11, 9], [9, 4]];
$pairs2 = [[1, 3], [3, 2], [2, 1]];
$pairs3 = [[1, 2], [1, 3], [2, 1]];

print_r(validArrangement($pairs1)); // Output: [[11, 9], [9, 4], [4, 5], [5, 1]]
print_r(validArrangement($pairs2)); // Output: [[1, 3], [3, 2], [2, 1]]
print_r(validArrangement($pairs3)); // Output: [[1, 2], [2, 1], [1, 3]]
?>

시간 복잡도:

• 그래프 작성: O(n), 여기서 n은 쌍의 수입니다.
• Hierholzer의 알고리즘: O(n), 각 모서리가 한 번 방문되기 때문입니다.
• 전체 시간 복잡도: O(n).

이 접근 방식은 유향 그래프에서 문제를 오일러 경로 문제로 처리하여 유효한 쌍 배열을 효율적으로 찾습니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 유효한 쌍 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!