🍃5.回文日期
题目链接:回文日期 http://lx.lanqiao.cn/problem.page?gpid=T2856
一道代码量比较大的模拟题,考察的又是时间的处理,这里我同样套用之前蓝桥真题中讲过的日期模拟模板。模拟能力是一项考察算法能力很基础的一项,一旦代码量一大许多同学就会在各种地方出现问题,而且由于代码量大能以发现问题。如果能AC这题相信对你的模拟能力有很大的提升,我们直接来看代码转换:
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static int[] M={0,31,28,31,30,31,30,31,31,30,31,30,31}; static int a; static int b; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); List<Integer> list=new ArrayList<>(); while(n!=0) { list.add(0,n%10); n/=10; } int y=list.get(0)*1000+list.get(1)*100+list.get(2)*10+list.get(3); int m=list.get(4)*10+list.get(5); int d=list.get(6)*1+list.get(7); boolean flag1=true; boolean flag2=true; String anser1=""; String anser2=""; while(flag1||flag2) { if(y%400==0||(y%4==0&&y%100!=0)) { M[2]=29; }else { M[2]=28; } d++; if(d>M[m]) { d=1; m++; } if(m>12) { m=1; y++; } if(check1(y,m,d)&&flag1) { anser1=test(y,m,d); flag1=false; } if(check2(y,m,d)&&flag2) { anser2=test(y,m,d); flag2=false; } } System.out.println(anser1); System.out.println(anser2); } static boolean check1(int y,int m,int d) { String sb=test(y,m,d); int n=sb.length(); int l=0; int r=n-1; while(l<r) { if(sb.charAt(l++)!=sb.charAt(r--)) return false; } return true; } static boolean check2(int y,int m,int d) { String sb=test(y,m,d); char a1=sb.charAt(0); char b1=sb.charAt(1); char c1=sb.charAt(2); char d1=sb.charAt(3); char e1=sb.charAt(4); char f1=sb.charAt(5); char g1=sb.charAt(6); char h1=sb.charAt(7); return a1!=b1&&a1==c1&&c1==f1&&f1==h1&&b1==d1&&d1==e1&&e1==g1; } static String test(int y,int m,int d) { StringBuilder sb=new StringBuilder(); sb.append(y); if(m<10) { sb.append("0"+m); }else { sb.append(m); } if(d<10) { sb.append("0"+d); }else { sb.append(d); } return sb.toString(); } }
🍂6.全球变暖
你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
题目链接:全球变暖http://lx.lanqiao.cn/problem.page?gpid=T2746
题目可以用深搜和广搜来做,我们套模板即可。深搜和广搜的重要性不言而喻,这道题大家拿来练手是非常合适的。无论是深搜还是广搜,每次我们遍历一个岛屿时,都要判断这个岛屿是否存在上下左右都是陆地的的陆地。这里要注意的是由于深搜会进行栈递归,在最后一个大数据的情况下会爆栈,而广搜就没有这个问题。下面贴上两种代码
深度优先搜索:
import java.util.Scanner; public class Main { static int[] dx= {1,-1,0,0}; static int[] dy= {0,0,1,-1}; static boolean[][] visit; static int ans=0; static boolean flag=false; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); char[][] arr=new char[n][n]; for(int i=0;i<n;++i) { arr[i]=sc.next().toCharArray(); } visit=new boolean[n][n]; for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { if(arr[i][j]=='#'&&!visit[i][j]) { dfs(arr,i,j); if(!flag) ans++; flag=false; } } } System.out.println(ans); } static void dfs(char[][] arr,int a,int b) { if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])) { flag=true; } visit[a][b]=true; for(int i=0;i<4;++i) { int newX=a+dx[i]; int newY=b+dy[i]; if(arr[newX][newY]=='#'&&!visit[newX][newY]) dfs(arr,newX,newY); } } static boolean check(char[][] arr,int i,int j) { return arr[i][j]=='#'; } }
宽度优先搜索:
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int[] dx= {1,-1,0,0}; static int[] dy= {0,0,1,-1}; static boolean[][] visit; static int ans=0; static boolean flag=false; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); char[][] arr=new char[n][n]; for(int i=0;i<n;++i) { arr[i]=sc.next().toCharArray(); } visit=new boolean[n][n]; for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { if(arr[i][j]=='#'&&!visit[i][j]) { Queue<int[]> queue=new LinkedList<>(); queue.offer(new int[] {i,j}); visit[i][j]=true; dfs(arr,queue); if(!flag) ans++; flag=false; } } } System.out.println(ans); } static void dfs(char[][] arr,Queue<int[]> queue) { while(!queue.isEmpty()) { int size=queue.size(); while(size-->0) { int[] curr=queue.poll(); int a=curr[0]; int b=curr[1]; if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])) { flag=true; } for(int i=0;i<4;++i) { int newX=a+dx[i]; int newY=b+dy[i]; if(arr[newX][newY]=='#'&&!visit[newX][newY]){ visit[newX][newY]=true; queue.offer(new int[] {newX,newY}); } } } } } static boolean check(char[][] arr,int i,int j) { return arr[i][j]=='#'; } }