前言

开始正式读研生涯，每天与莲花斗智斗勇也不要忘记刷题哦~
这一次主要以Java为主啦~
简单题不记录，只记录中等和困难题或者特殊题目~
https://zhuanlan.zhihu.com/p/681511368

---

2025.9.15打卡

2025.9.16打卡 替换数组中的非互质数

今天AAAI出分，虽然被reject是意料之中，但是还是不能耽误刷题，毕竟我是科研混子，只想找一份工作
今天是hard题，但是其实没那么难，主要是回顾一下gcd最小公因数的公式

给你一个整数数组nums。请你对数组执行下述操作：
从nums中找出 任意两个相邻的非互质数。
如果不存在这样的数，终止这一过程。
否则，删除这两个数，并替换为它们的最小公倍数（Least Common Multiple，LCM）。
只要还能找出两个相邻的非互质数就继续 重复这一过程。
返回修改后得到的最终数组。可以证明的是，以任意顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的最大公约数。

---

解析：
主要是gcd公式,gcd(a,b)=gcd(b,a%b)

public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

针对大整数，更相减损术,gcd(a,b)=gcd(a-b,b)
最小公倍数（Least Common Multiple, LCM）同理
axb=gcd(a,b)xlcm(a,b)

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> ans=new ArrayList<>();
        for(int x:nums){
            while(!ans.isEmpty()&&gcd(x,ans.get(ans.size()-1))>1){
                x=x/gcd(x,ans.get(ans.size()-1))*ans.get(ans.size()-1);
                ans.remove(ans.size()-1);
            }
            ans.add(x);
        }
        return ans;
    }
    private int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}

2025.9.17打卡