연결리스트에 최대 공약수 삽입

2807. 연결리스트에 최대공약수 삽입

난이도:중

주제: 연결리스트, 수학, 정수론

각 노드가 정수 값을 포함하는 연결 목록 헤드의 헤드가 있다고 가정합니다.

인접한 노드의 모든 쌍 사이에 최대 공약수와 동일한 값을 가진 새 노드를 삽입합니다.

삽입 후 연결 리스트를 반환합니다.

두 숫자의 최대 공약수는 두 숫자를 균등하게 나누는 가장 큰 양의 정수입니다.

예 1:

• 입력: head = [18,6,10,3]
• 출력: [18,6,6,2,10,1,3]
• 설명: 첫 번째^st 다이어그램은 초기 연결 목록을 나타내고 두 번째^nd 다이어그램은 새 노드를 삽입한 후의 연결 목록을 나타냅니다(파란색 노드는 삽입된 노드입니다). 노드).
  • 첫 번째^번째 노드와 두 번째^번째 노드 사이에 18과 6 = 6의 최대 공약수를 삽입합니다.
  • 두 번째^번째 노드와 세 번째^번째 노드 사이에 6과 10 = 2의 최대 공약수를 삽입합니다.
  • 3^번째 노드와 4^번째 노드 사이에 10과 3 = 1의 최대공약수를 삽입합니다. 더 이상 인접한 노드가 없으므로 연결리스트를 반환합니다.

예 2:

• 입력: head = [7]
• 출력: [7]
• 설명: 첫 번째^st 다이어그램은 초기 연결 목록을 나타내고 두 번째 ^nd 다이어그램은 새 노드를 삽입한 후의 연결 목록을 나타냅니다. 인접한 노드 쌍이 없으므로 초기 연결리스트를 반환합니다.

예 3:

• 입력: 비용 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• 출력: 10

제약조건:

• 목록의 노드 수는 [1, 5000] 범위에 있습니다.
• 1 <= Node.val <= 1000

힌트:

1. 왼쪽의 각 점은 이미 왼쪽 노드에 연결된 정확한 점에 연결되거나 어떤 노드에도 연결되지 않은 오른쪽 노드의 하위 집합에 연결됩니다.
2. 비트마스킹과 함께 동적 프로그래밍을 사용합니다. 여기서 상태는 (첫 번째 그룹에 할당된 포인트 수, 두 번째 그룹에 할당된 포인트의 비트마스크)입니다.

해결책:

연결된 목록의 모든 인접한 노드 쌍 사이에 노드를 삽입해야 합니다. 삽입된 노드의 값은 인접한 두 노드 값의 최대 공약수(GCD)여야 합니다. 연결된 목록을 탐색하고 모든 인접 노드 쌍에 대한 GCD를 계산한 다음 그에 따라 새 노드를 삽입합니다.

이 문제에 접근하는 방법은 다음과 같습니다.

1. ListNode 클래스 정의: 이 클래스는 연결된 목록의 각 노드를 나타냅니다.
2. 목록 탐색: 목록을 반복하여 인접한 노드의 각 쌍을 찾습니다.
3. GCD 노드 삽입: 인접한 노드의 각 쌍에 대해 값이 인접한 두 노드의 GCD인 새 노드를 삽입합니다.
4. 수정된 목록을 반환.

이 솔루션을 PHP: 2807로 구현해 보겠습니다. 연결리스트에 최대공약수 삽입

<?php
// Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

/**
 * Function to calculate the GCD of two numbers.
 *
 * @param $a
 * @param $b
 * @return mixed
 */
function gcd($a, $b) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

/**
 * @param ListNode $head
 * @return ListNode
 */
function insertGreatestCommonDivisors($head) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to print the linked list for testing purposes.
 * 
 * @param $head
 * @return void
 */
function printList($head) {
    $current = $head;
    while ($current != null) {
        echo $current->val . " ";
        $current = $current->next;
    }
    echo "\n";
}

// Example usage:

// Create the linked list: 18 -> 6 -> 10 -> 3
$head = new ListNode(18);
$head->next = new ListNode(6);
$head->next->next = new ListNode(10);
$head->next->next->next = new ListNode(3);

// Insert GCD nodes.
$modifiedHead = insertGreatestCommonDivisors($head);

// Print the modified linked list.
printList($modifiedHead);

// Output should be: 18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li><p><strong>ListNode 클래스</strong>: 이 클래스는 값($val)과 다음 노드($next)에 대한 속성을 사용하여 연결된 목록의 노드 구조를 나타냅니다.</p></li>
<li><p><strong>GCD 계산</strong>: gcd 함수는 유클리드 알고리즘을 사용하여 두 정수의 최대 공약수를 계산합니다.</p></li>
<li>
<p><strong>메인 로직(insertGreatestCommonDivisors)</strong>:</p>

<ul>
<li>마지막에서 두 번째 노드에 도달할 때까지 연결 목록을 반복합니다.</li>
<li>인접 노드의 각 쌍에 대해 해당 값의 GCD를 계산합니다.</li>
<li>이 GCD 값으로 새 노드를 생성하고 현재 노드와 다음 노드 사이에 삽입합니다.</li>
</ul>
</li>
<li><p><strong>Edge Case</strong>: 리스트에 노드가 하나만 있는 경우 인접한 노드가 없으므로 변경하지 않고 그대로 반환합니다.</p></li>
<li><p><strong>테스트</strong>: printList 함수는 확인을 위해 연결된 목록의 값을 출력하는 데 사용되는 도우미 함수입니다.</p></li>
</ol>

<h3>
  
  
  Time Complexity:
</h3>

<ul>
<li>The time complexity of this solution is (O(n)), where (n) is the number of nodes in the linked list. Calculating the GCD for each adjacent pair takes constant time on average, and we perform a linear traversal of the list.</li>
</ul>

<h3>
  
  
  Example:
</h3>

<p>For the input list [18, 6, 10, 3], the output is:<br>
</p>

<pre class="brush:php;toolbar:false">18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

위 내용은 연결리스트에 최대 공약수 삽입의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!