随笔，这学期最后一天的算法学习

最近没写什么笔记，并不是因为懒了。而是和我上一次大片时间咕了笔记一样：备战蓝桥杯。

这种时候我一般都会力扣上刷刷题：距今为止，力扣一共刷了142道题，一大半的中等题和一部分简单题以及一点点困难题。

在备战的最后一天，我又通过历年卷（其实只有去年）学习了快速幂求逆元，最小生成树以及单调队列三个问题。希望明天能有涉及，希望这次能够拿个奖吧，最低的就行，希望不枉我最近的努力。明天去参赛不仅要比早八起得还早而且还要自己打车去。。。主要是拿奖了明年学校还会发钱，狠赚笔！

明天结束了我也要赶紧收收心继续面向开发了，战场在即！

贴一下上述三个java实现的代码

1.快速幂求逆元（小费马定理）

long qmi(long base,long e,long p) {
        long res=1;
        base%=p;
        while(e>0) {
            if((e&1)==1)
                res=res*base%p;
            base=base*base%p;
            e>>=1;
        }
        return res;
    }
    long niyuan(long a,long b) {
        return qmi(a, b-2, b);
    }

2.最小生成树（克鲁斯卡尔算法）

    static class Edge{
        int from;
        int to;
        int weight;
        public Edge(int from,int to,int weight) {
            // TODO 自动生成的构造函数存根
            this.from=from;
            this.to=to;
            this.weight=weight;
        }
    }
    static void kruskal(Edge[]edges,int n) {
        int parent[]=new int[n];
        for(int i=0;i<n;i++) {
            parent[i]=i;
        }
        Arrays.sort(edges,Comparator.comparing(e->e.weight));
        for(Edge edge:edges) {
            int x=edge.from;
            int y=edge.to;
            int xRoot=isParent(parent, x);
            int yRoot=isParent(parent, y);
            if(xRoot!=yRoot) {
                parent[xRoot]=yRoot;
                System.out.println(edge.from+"-"+edge.to+"-"+edge.weight);
            }
        }
        
    }
    static int isParent(int[]parent,int i) {
        if(i!=parent[i])
            parent[i]=isParent(parent, parent[i]);
        return parent[i];
    }
    public static void main(String args[]) {
        Edge[]edges= {
                new Edge(0, 1, 2),
                new Edge(0, 3, 6),
                new Edge(1, 2, 5),
                new Edge(1, 4, 3),
                new Edge(2, 4, 6),
                new Edge(3, 4, 1),
        };
        kruskal(edges,5);
    }

3.单调队列（一维滑动窗口求最大值）

public int[] maxSlidingWindow(int[] nums, int k) {
        int length=nums.length;
        Deque<Integer>deque=new ArrayDeque<>();
        
        for(int i=0;i<k;i++) {
            while(!deque.isEmpty()&&nums[i]>nums[deque.peek()]) {
                deque.poll();
            }
            deque.offer(i);
        }
        int ans[]=new int[length-k+1];
        ans[0]=nums[deque.peek()];
        for(int i=k;i<length;i++) {
            while(!deque.isEmpty()&&nums[i]>nums[deque.peekLast()])
                deque.poll();
            deque.offer(i);
            while(deque.peek()<=i-k){
                deque.poll();
            }
            ans[i-k+1]=nums[deque.peek()];
        }
        
        
        return ans;
    }