算法刷题常用方法

📑前言

本文主要是【java】——算法刷题常用方法的文章，如果有什么需要改进的地方还请大佬指出??

🎬作者简介：大家好，我是听风与他🥇
??博客首页：CSDN主页听风与他
🌄每日一句：狠狠沉淀，顶峰相见

1.最大公约数gcd

package 蓝桥杯练习;

import java.util.Scanner;

public class 最大公约数 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		System.out.println(gcd(a, b));
		System.out.println(a*b/gcd(a, b));
	}
	
	public static int gcd(int a,int b) {
		return b==0?a:gcd(b, a%b);
	}

}

2.唯一分解定理

package 蓝桥杯练习;

import java.util.Scanner;

public class 唯一分解定理 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println(syz(n));
		}
		
	}
	
	public static int syz(int n) {
		int cnt = 1;
		int bak = n;
		for(int i=2;i*i<=n;i++) {
			int num = 0;
			while(bak%i==0) {
				num++;
				bak/=i;
			}
			cnt = cnt*(num+1);
		}
		if (bak > 1) {
			cnt++;
		}
		return cnt;
	}

}

3.欧拉筛

package 蓝桥杯练习;

public class 欧拉筛 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int N = 1000;
		int prime[] = new int[N];
		boolean isp[] = new boolean[N+5];
		int count = 0;
		for(int i=2;i<=N;i++) {
			if(isp[i]==false) prime[count++]=i;
			for(int j=0;j<count&&prime[j]*i<=N;j++) {
				isp[i*prime[j]]=true;//素数的i倍一定是合数
				if(i%prime[j]==0) break;
			}
		}
		for(int i=0;i<count;i++) {
			System.out.println(prime[i]);
		}
		System.out.println("共有"+count+"个素数");
	}

}

4.单调队列实现滑动窗口

package 蓝桥杯练习;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class 单调队列实现滑动窗口1 {
	
/*
8 3
1 3 4 7 6 2 5 1
 */

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		/*
		 * 长度为n的数组 长度为m的窗口，求数组中每个长度为m的窗口中的最大值
		 * 
		 * n=8 m = 3
		 * 1 3 4 7 6 2 5 1
		 */
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int a[] = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = sc.nextInt();
		}
		Deque<Integer> q = new ArrayDeque<>();
		for(int i=0;i<n;i++) {
			//保证队头元素一定是在窗口的 i-3+1
			while(!q.isEmpty()&&q.peekFirst()<i-m+1) q.pollFirst();
			while(!q.isEmpty()&&a[q.peekLast()]<a[i]) q.pollLast();
			q.addLast(i);
			if (i>=m-1) {
				System.out.println(a[q.peekFirst()]);
			}
		}
	}

}

5.数组前缀和

package 蓝桥杯练习;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class 数组前缀和 {
/*
5
1 2 3 4 5
 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		sc.nextToken();
		int n = (int)sc.nval;
		int a[] = new int[n+1];
		long sum[] = new long[n+1];
		for(int i=1;i<=n;i++) {
			sc.nextToken();
			a[i] = (int)sc.nval;
		}
		for(int i=1;i<=n;i++) {
			sum[i]=a[i]+sum[i-1];
		}
		for(int i=1;i<=n;i++) {
			System.out.println(sum[i]);
		}
	}

}

📑文章末尾