Leetcode2807. 在链表中插入最大公约数

2024-01-07 18:53:24

Problem: 2807. 在链表中插入最大公约数

题目思路

模拟插入流程:

  1. 检测当前节点是否有后置结点;
  2. 将当前结点与后置结点的值做最大公约数处理得到新结点的值,然后插入到当前结点之后;
  3. 再将检测结点向后移动两个位置;
  4. 循环123即可;

注意点

计算最大公约数其实有C++自带的__gcd()来实现,不过为了巩固知识也可以选择手写
同时本题的val值在1到1000之间
,所以可以这样写一个计算两个整数最大公约数的函数。

int GreatestCommonDivisors(int a, int b) // 1000>=val>=1
    {
        if (b == 0) {
            return a;
        } else {
            return GreatestCommonDivisors(b, a % b);
        }
    }

这段代码是一个计算两个整数最大公约数的函数,使用了欧几里得算法。

  • 函数的参数是两个整数 ab。如果 b 是0,那么返回 a,因为任何数和0的最大公约数都是它自己。如果 b 不是0,那么递归地调用 GreatestCommonDivisors(b, a % b)
  • 这个函数使用了欧几里得算法的思想,递归地计算最大公约数。算法的基本思想是:gcd(a,b)=gcd(b,amod b)。这个过程会持续到b等于0,此时a就是最大公约数。
  • 需要注意的是,因为题目的val范围设计在1-1000,所以这个函数没有处理负数的情况,如果输入的 ab 是负数,可能会导致不正确的结果。另外,如果函数被频繁调用,可能会导致栈溢出,因为这是一个递归函数。

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int GreatestCommonDivisors(int a, int b) // 1000>=val>=1
    {
        if (b == 0) {
            return a;
        } else {
            return GreatestCommonDivisors(b, a % b);
        }
    }
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* node = head;
        while (node->next) {
            node->next = new ListNode(
                GreatestCommonDivisors(node->val, node->next->val), node->next);
            node = node->next->next;
        }
        return head;
    }
};

文章来源:https://blog.csdn.net/qq_44922487/article/details/135429510
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。