📑前言
本文主要是【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]);
}
}
}
📑文章末尾
