2019蓝桥杯校赛总结

1 - 2 计算器计算内存(手动忽略)

3.统计1-2019中带’9’的数字有多少个

public class C {
	public static void main(String[] args) {
		int res = 0;
		for(int i=1;i<=2019;i++){
			if(func(String.valueOf(i))) res++;
		}
		System.out.println(res);
	}
	public static boolean func(String n) {
		for(char c:n.toCharArray()){
			if(c == '9') return true;
		}
		return false;
	}
}

思路很简单,要么用字符串要么用取模判断是不是含有’9’

4.统计8*8的图里有多少种走对角线的方式

这个题有点东西是在给了很多限制，其实最后发现都是没啥用的，加不加也是那么多 (只能往右或者往下走) 直接dfs即可。

public class D {
	static int res = 0;
	public static void main(String[] args) {
		dfs(0,0,0);
		System.out.println(res);
	}
	public static void dfs(int i,int j,int count){
		if(i<0||i>=8||j<0||j>=8||count>14) return;
		if(i==7&&j==7&&count==14){
			res++;
			return;
		}
		dfs(i+1,j,count+1);
		dfs(i,j+1,count+1);
	}
}

5.和第三题有点类似,只不过是求1-n直接有多少(由不同数字组成的数字)

多加一个vis数组判断该数,是否在这个数字里出现过复杂度应该是(数字的位数*n)

public class E {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int res = n;
		for(int i=1;i<=n;i++){
			if(func(i)) res--;
		}
		System.out.println(res);
	}
	public static boolean func(int num){
		boolean[] vis = new boolean[11];		//这里有点费空间
		while(num != 0){
			int n = num%10;
			if(vis[n]) return true;
			else vis[n] = true;
			num /= 10;
		}
		return false;
	}
}

6.求最长上升子序列的长度

直接遍历 (n的时间复杂度) 统计最长的序列长度

public class F {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] nums = new int[n+1];
		for(int i=0;i<n;i++){
			nums[i] = sc.nextInt();
		}
		int max = 1;
		int len = 1;
		int num = nums[0];
		for(int i=1;i<n;i++){
			if(num<nums[i]) len++;
			else len = 1;
			num = nums[i];
			if(len > max ) max = len;
		}
		System.out.println(max);
	}
}

7.本来是一道送分题,求逆序对

写过的题，结果活生生会被自己玩成了丢分题，思路很简单直接两层for暴力也能过，但是使用归并排序理论上是能过10w的测试集的。关键一步没写出来，难受，不想说话…..

public class G {
	static int res = 0;
	static int[] nums;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		nums = new int[n+1];
		for(int i=0;i<n;i++){
			nums[i] = sc.nextInt();
		}
		merge_sort(nums,0,n-1);
		System.out.println(res);
	}

	public static void merge_sort(int[] nums,int l,int r){
		if(l>=r) return;
		int mid = l+r>>1;
		merge_sort(nums,l,mid);
		merge_sort(nums,mid+1,r);
		int[] tmp = new int[r-l+1];
		int k=0,left=l,right=mid+1;
		while(left<=mid && right<=r){
			if(nums[left]<=nums[right]) tmp[k++] = nums[left++];
			else {
				tmp[k++] = nums[right++];
				res+=mid-left+1;            // 核心: 逆序对 应该是后面的数去前面的路程之和
			}
		}
		while(left<=mid){
			tmp[k++] = nums[left++];
		}
		while(right<=r) tmp[k++] = nums[right++];
		for(int n:tmp) nums[l++] = n;
	}

}

8.求1-n之间取n个数且满足奇数位大于前一项,偶数位小于前一项

相当标准的搜索,但是好像拿不了多少分

思路: 第一个数随便取,后面的按奇偶位分策略搜索

public class H {
	static int res = 0;
	static int n,m;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		for(int i=1;i<=n;i++){
			dfs(2,i);
		}
		System.out.println(res);
	}
	
	public static void dfs(int index,int pre){
		if(index == m+1){
			res++;
			return;
		}
		if(index % 2 == 0){
			for(int i=1;i<pre;i++){
				dfs(index+1,i);
			}
		}else{
			for(int i=pre+1;i<=n;i++){
				dfs(index+1,i);
			}
		}
	}
}

9.加上步长,求最短路径

也是dfs搜索最短路径,不过是搜索的路线有所限制,必须是满足路径之长小于步长(使用dp数组保存该点的最短路径,用空间换时间)

public class I {
	static boolean[][] vis;
	static int[][] dp;
	static int n,m;
	static double size; 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		size = sc.nextDouble();
		vis = new boolean[n+1][m+1];
		dp = new int[n+1][m+1];
		System.out.println(dfs(1,1));
	}
	public static int dfs(int i,int j){
		if(i==n&&j==m) return 0;
		if(dp[i][j] != 0) return dp[i][j];
		int min = Integer.MAX_VALUE;
		for(int x=0;x<=n-i;x++){        // 搜索策略
			for(int y=0;y<=m-j;y++){
				if(Math.sqrt((x*x) + (y*y)) > size) break;
				if(!vis[i+x][j+y]) {
					vis[i+x][j+y] = true;
					min = Math.min(min, dfs(i+x,j+y));
					vis[i+x][j+y] = false;
				}	
			}
		}
		dp[i][j] = min+1;       // 保存最短路径
		return min + 1;
	}
}

但是好像还是过不了1000*1000的矩阵

10.按原顺序输出前n大的数字

前n大可以直接sort或者用优先队列
后面按顺序输出,可以用map记录前n大的数据,再回原数组中按位置输出

使用map可以用key记录数字,value记录出现次数,处理具有重复数据的情况

public class J {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] nums = new int[n+1];
		PriorityQueue<Integer> q = new PriorityQueue<>(m);
		for(int i=0;i<n;i++){
			int num = sc.nextInt();
			nums[i] = num;
			if(q.size() <m) q.add(num);
			else if(q.peek() < num){
				q.poll();
				q.add(num);
			}
		}
		Map<Integer,Integer> map = new HashMap<>();
		for(int i=0;i<m;i++){
			int key = q.poll();
			if(map.containsKey(key)){
				map.put(key,map.get(key)+1);
			}else{
				map.put(key,1);
			}			
		}
		for(int i=0;i<n;i++){
			if(map.containsKey(nums[i])){
				System.out.print(nums[i] + " ");
				if(map.get(nums[i]) == 1) map.remove(nums[i]);
				else map.put(nums[i], map.get(nums[i])-1);
			}
		}
	}
}

O(nlogn)的复杂度,应该能过,只是最后太着急,忘了加上判断,value为0时删除该元素….