在链表中插入最大公约数

2807。在链表中插入最大公约数

难度：中等

主题：链表、数学、数论

给定一个链表头，其中每个节点都包含一个整数值。

在每对相邻节点之间，插入一个新节点，其值等于它们的最大公约数。

返回插入后的链表.

两个数的最大公约数是能整除两个数的最大正整数。

示例1：

• 输入： head = [18,6,10,3]
• 输出： [18,6,6,2,10,1,3]
• 说明：第1^st图表示初始链表，第2^nd图表示插入新节点后的链表（蓝色的节点是插入的节点）节点）。
  • 我们在第 1^st 和 2^nd 节点之间插入 18 和 6 = 6 的最大公约数。
  • 我们在第 2^nd 和第 3^rd 节点之间插入 6 和 10 = 2 的最大公约数。
  • 我们在第 3^rd 和第 4^th 节点之间插入 10 和 3 = 1 的最大公约数。 没有更多的相邻节点，因此我们返回链表。

示例2：

• 输入： head = [7]
• 输出： [7]
• 说明：第1^st图表示初始链表，第2^nd图表示插入新节点后的链表。 没有成对的相邻节点，因此我们返回初始链表。

示例 3：

• 输入： 成本 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• 输出： 10

约束：

• 列表中的节点数量在 [1, 5000] 范围内。
• 1

提示：

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
?>

解释：

1. ListNode 类：该类表示链表中节点的结构，具有值 ($val) 和下一个节点 ($next) 的属性。

2. GCD 计算：gcd 函数使用欧几里德算法计算两个整数的最大公约数。

3. 主要逻辑（插入最大公约数）:

   • 我们循环遍历链表，直到到达倒数第二个节点。
   • 对于每对相邻节点，我们计算它们值的 GCD。
   • 我们使用此 GCD 值创建一个新节点并将其插入当前节点和下一个节点之间。

4. 边缘情况：如果列表只有一个节点，我们将按原样返回它，不做任何更改，因为没有相邻节点。

5. 测试：函数 printList 是一个辅助函数，用于输出链表的值以进行验证。

Time Complexity:

• 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.

Example:

For the input list [18, 6, 10, 3], the output is:

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中文网其他相关文章！