2024-1-6

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

思路：模拟

1.调用函数求出要插入的最大公约数

2.插入到cur的后面

3.因为插了一位，所以移动两个位置

public ListNode insertGreatestCommonDivisors(ListNode head) {ListNode cur = head;while (cur.next!=null){int gcdVal = gcd(cur.val,cur.next.val);//调用函数求出要插入的最大公约数cur.next = new ListNode(gcdVal,cur.next);//插入到cur的后面cur = cur.next.next;//因为插了一位，所以移动两个位置}return head;}/*** 求两个结点值的最大公约数* @param a* @param b* @return*/private int gcd(int a,int b){//求最大公约数有多种写法while (a!=0){int temp = a;a = b % a;b = temp;}return b;}

求最大公约数的几种方法：

1.暴力枚举法

    public static int gcd(int a, int b) {int min = a < b ? a : b;//判断并取出两个数中小的数for (int i = min; i >= 1; i--) { //循环,从最小值开始,依次递减,直到i=1if (a%i==0&&b%i==0){    //当i能同时被A和B余尽时,返回ireturn i;}}return 0;}}

2.辗转相除法

 public static int gcd(int a, int b) {// 辗转相除法int c = a % b;   //先将a对b取余while (c != 0) {   //当余数不等于0时,一直进行循环,直到余数等于0,公约数就为ba = b;         //将a对b的余数再对b取余,直到循环结束b = c;c = a % b;}return b;}

3.辗转相除法 —递归调用

    public static int gcd(int a, int b) {// 辗转相除法 改进,调用函数递归int max = a > b ? a : b; //求出大的数int min = a < b ? a : b; //求出小的数if(max%min==0){return min;      //当大数模小数能余尽时,最大公约数就是小的数}return gcd(max%min,min);//递归函数,参数去前两个数的余数,和小的数

4.辗转相除法 —递归调用—简化写法

public static int gcd(int a, int b) {// 辗转相除法 改进,调用函数递归return (a % b == 0) ? b : gcd(b, a%b );// 相同思路,三元运算/简化写法}

1.如果a余b等于0，说明b就是最大公约数

2.否则，进行递归，b代替曾经的a，让a%b产生的余数代替曾经的b。

3.始终确保大数%小数

4.即使b位置上是值大于a, b代替a后，a（小数）%b(大数) = a ，相当于替换位置

5. （b,a%b）的位置不能交换，否则无法跳出递归

5.调用函数递归 更相减损法

 public static int gcd(int a, int b) {//调用函数递归 更相减损法int max = a>b?a:b;int min = a<b?a:b;if(max%min==0){return min;}return gcd(max-min,min);//相同思路,将%改为-,优化速度}

6.调用函数递归 更相减损法–简化

    public static int gcd(int a, int b) {//调用函数递归 更相减损法 简易写法if (a < b) {int tmp = a;a = b;b = tmp;}return (a % b == 0) ? b : gcd(a - b, b);

简化不用找大小数，把大数放到前面

因为小数减大数为负数，所以要把大数替换到前面，

    public static int gcd5(int a, int b) {//调用函数递归 更相减损法 简易写法return (a % b == 0) ? b : a > b ? gcd5(a - b, b) : gcd5(b-a,a);}

压行写法，就是三目嵌套，就是可读性不高

点击移步博客主页，欢迎光临~