前言

开始正式读研生涯，每天与莲花斗智斗勇也不要忘记刷题哦~
这一次主要以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)

1
2
3

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打卡

2025.9.18打卡

2025.9.19打卡

2025.9.20打卡

2025.9.25-9.28打卡

三角形专场

三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

解析：
三角形应该是左对齐的数组，本质上是dp问题
2
3 4
6 5 7
4 1 8 3

状态方程dfs(i,j)=min(dfs(i+1,j),dfs(i+1,j+1))+triangle[i][j]

前言