动易网站内容管理系统,电视剧排行榜,装潢设计与制作专业,咖啡网站建设的优势Problem: 2807. 在链表中插入最大公约数 文章目录 题目思路注意点Code 题目思路
模拟插入流程#xff1a;
检测当前节点是否有后置结点#xff1b;将当前结点与后置结点的值做最大公约数处理得到新结点的值#xff0c;然后插入到当前结点之后#xff1b;再将检测结点向后… Problem: 2807. 在链表中插入最大公约数 文章目录 题目思路注意点Code 题目思路
模拟插入流程
检测当前节点是否有后置结点将当前结点与后置结点的值做最大公约数处理得到新结点的值然后插入到当前结点之后再将检测结点向后移动两个位置循环123即可
注意点
计算最大公约数其实有C自带的__gcd()来实现不过为了巩固知识也可以选择手写 同时本题的val值在1到1000之间所以可以这样写一个计算两个整数最大公约数的函数。
int GreatestCommonDivisors(int a, int b) // 1000val1{if (b 0) {return a;} else {return GreatestCommonDivisors(b, a % b);}}这段代码是一个计算两个整数最大公约数的函数使用了欧几里得算法。
函数的参数是两个整数 a 和 b。如果 b 是0那么返回 a因为任何数和0的最大公约数都是它自己。如果 b 不是0那么递归地调用 GreatestCommonDivisors(b, a % b)。这个函数使用了欧几里得算法的思想递归地计算最大公约数。算法的基本思想是gcd(a,b)gcd(b,amod b)。这个过程会持续到b等于0此时a就是最大公约数。需要注意的是因为题目的val范围设计在1-1000所以这个函数没有处理负数的情况如果输入的 a 和 b 是负数可能会导致不正确的结果。另外如果函数被频繁调用可能会导致栈溢出因为这是一个递归函数。
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) // 1000val1{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;}
};
