蓝桥杯常用算法合集（JAVA)_蓝桥杯算法java

目录

1 判断闰年

2 计数月、日或者分钟

3 筛选素数

 4 求组合数C(n,m)模板

5 全排列

6 并查集

1 判断闰年

我们知道，(1)如果是整百的年份，能被400整除的，是闰年；(2)如果不是整百的年份，能被4整除的，也是闰年。每400年，有97个闰年。鉴于此，程序可以作以下设计：

第一步，判断年份是否被400整除，能的话，就是闰年。比如1600、2000、2400年是闰年。

第二步，在第一步不成立的基础上，判断年份能否被100整除，如果是，则不是闰年。比如1900、2100、2200年不是闰年。

第三步，在第二步不成立的基础上，判断年份能否被4整除，如果是，则是闰年。比如1996、2004、2008年是闰年。

第四步，在第三步不成立的基础上，则不是闰年。比如1997、2001、2002年不是闰年。
 

import java.util.Scanner;//插入扫描仪
 
public class runnian
 
{
public static void main(String[] args)//Sting[] args别忘了写进来
 
{
Scanner s=new Scanner(System.in);//声明扫描仪变量
 
System.out.println("请输入年份");//系统提示输入年份
 
int nianfen=s.nextInt();//取得下一行输入的年份值
 
if(nianfen%400==0){System.out.println(nianfen+"年是闰年");}//判断能否被400整除
 
else if(nianfen%100==0){System.out.println(nianfen+"年不是闰年");}//判断能否被100整除
 
else if(nianfen%4==0){System.out.println(nianfen+"年是闰年");}//判断能否被4整除
 
else{System.out.println(nianfen+"年不是闰年");}
 
}
 
}

2 计数月、日或者分钟

计算日的算法如下，小时分钟和秒就是在此基础上乘以相应的进制即可，月份就是在模板里面month++的时候顺便计数即可。

 
int syear,smonth,sday; //分别为结束年，月，日
int countday(int year,int month,int day){  //分别为开始的年月日
  int ans=0;
  int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  while(1){
    if(year==syear&&month==smonth&&day==sday){
      break;
    }
    day++;
    if(isleaf(year)&&month==2){
      if(day>mon[month]+1){
        month++;
        day=1;
      }
    }else{
      if(day>mon[month]){
        month++;
        day=1;
      }
    }
    if(month>12){
      month=1;
      year++;
    }
    ans++;
  }
  return ans;
}

3 筛选素数

筛选素数有许多种方法，首先是最简单的O(n^(3/2))的算法

import java.util.Scanner;
 
public class ScannerPrimeNumber {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		boolean[] bs = new boolean[n];
		for (int i = 2; i < bs.length; i++) {// 从2开始
			for (int j = i + 1; j < bs.length; j++) {//j=i+1 因为i与j必能除尽，从i+1循环就行。
				if (j % i == 0) {
					bs[j] = true;// 因为boolean默认为false，因此在这里不再全赋值为true再把符合条件的值赋值为false
									// 而直接把符合条件的值赋值为true
				}
			}
		}
		for (int i = 2; i < bs.length; i++) {// 0和1不是质数，因此从2开始循环
			if (bs[i] == false) {
				System.out.println(i);
			}
		}
	}
}

 4 求组合数C(n,m)模板

 
long long C(int n,int m){
  if(m==0)return1;
  long long ans=1;
  for(int i=n;i>n-m;i--)ans*=i;
  for(int i=m;i>1;i--)ans/=i;
  return ans;
}

5 全排列

vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        do{
            ret.emplace_back(nums);
        }while(next_permutation(nums.begin(),nums.end()));
        return ret;
 }

6 并查集

 
int n,m,cnt=0;
int f[10005];
int find(int x){
  if(f[x]==x)return x;
  return f[x]=find(f[x]);
}
void union(int x,int y){
  int a=find(x);
  int b=find(y);
  if(a!=b){
    f[a]=b;
    cnt++;
  }
}