🎒 6.迷宫与陷阱（BFS）
题目链接：迷宫与陷阱http://lx.lanqiao.cn/problem.page?gpid=T2760
这道题目也是考察BFS广度优先搜索，有点类似前面的大胖子走迷宫，对于我而言会比大胖子更难一些，因为会容易有失分情况。
首先这道题同样要像大胖子一样思考，每一次有多少种选择？有时候从陷阱过去可能会更快，所以会有吃了无敌点再倒回去从陷阱过去的情况，所以这道题移动时如果我们具有无敌步数，是可以走回头路的。
但提交以后会发现是这样：
为什么在大数据会超时甚至爆内存呢？
这就是这道题比大胖子那题更难的原因，因为我们前面的做法是当你的无敌步数不为0的时候，就可以往任何你走过的地方走。如果无敌点太多，就会导致大量被走过的位置疯狂重新入队，不仅会导致超时还会爆内存。
所以我们应该如何解决呢？我们可以这样想，如果此时我们走到一个位置(x,y)。此时无敌步数剩m。如果我们后面从其他无敌点再次走回这个位置，无敌步数仍然是m，那我们还有必要走下去吗？答案肯定是没有必要的！因为BFS搜索是不会搜索重复的，我们以往BFS判断已走过的标准只是坐标而已，而这题我们需要对剩余无敌步数也进行记忆。当在同一个位置，但剩余的无敌步数不同时，这是属于两种情况，否则视为一种需要进行去重！因此我们的标记数组要从普通的二维变成三维，多一维用来记录剩余无敌步数。
代码转换：
import java.util.LinkedList; import java.util.Queue; import java.io.*; public class Main { static int N = 1010; static char[][] arr = new char[N][N]; static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, -1}; //因为无敌步数做多只有10，所以第三维开11就行了 //不然太大肯定爆掉了，三维太大了 static int[][][] visit = new int[N][N][11]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { String[] s1=br.readLine().split(" "); int n = Integer.parseInt(s1[0]); int k = Integer.parseInt(s1[1]); for (int i = 0; i < n; i++) { arr[i] = br.readLine().toCharArray(); } Queue<PII> queue = new LinkedList<>(); queue.offer(new PII(0, 0, 0)); visit[0][0][0]=1; int tmp = 0; while (!queue.isEmpty()) { int size = queue.size(); while (size-- > 0) { PII curr = queue.poll(); int x = curr.x; int y = curr.y; int z = curr.z; //找到答案 if (x == n - 1 && y == n - 1) { System.out.println(tmp); return; } for (int i = 0; i < 4; i++) { int a = x + dx[i]; int b = y + dy[i]; int c = z; //越界 if ((!(a >= 0 && a < n && b >= 0 && b < n))||arr[a][b]=='#'||visit[a][b][c]==1) continue; if (arr[a][b]=='X'){ if (c>0){ queue.offer(new PII(a,b,c-1)); visit[a][b][c-1]=1; } }else if (arr[a][b]=='%'){ queue.offer(new PII(a,b,k)); visit[a][b][c]=1; arr[a][b]='.'; }else{ visit[a][b][c]=1; queue.offer(new PII(a,b,c>0?c-1:0)); } } } tmp++; } System.out.println(-1); } } //x，y记录的是坐标 //z记录的是剩余的无敌步数 class PII{ int x,y,z; public PII(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } }
🎎7.蓝肽子序列（线性DP）
题目链接：蓝肽子序列 http://lx.lanqiao.cn/problem.page?gpid=T2885
题目表达的确实很让人头疼，但如果做过最长公共子序列模型的题目，大家应该还是能看出来的。本质上就是求最长公共子序列，但恶心你一点就是需要先根据大写字母去进行切割。像LCS(最长公共子序列)和LIS（最长递增子序列）还是比较基础的线性DP题目，大家一定要去学习掌握一下，这几年蓝桥杯考的也是挺多的。
代码转换:
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static int N=1010; static int[][] f=new int[N][N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); List<String> A = new ArrayList<>(); List<String> B = new ArrayList<>(); int n = s1.length(); int m = s2.length(); int i = 0; while (i <n) { int j = i + 1; while (j != n && s1.charAt(j) > 'Z') j++; A.add(s1.substring(i, j)); i = j; } i=0; while (i<m){ int j=i+1; while (j != m && s2.charAt(j) > 'Z') j++; B.add(s2.substring(i, j)); i = j; } //以上均为切割步骤 for (int j = 1; j <=A.size(); j++) { for (int k = 1; k <=B.size(); k++) { f[j][k]=Math.max(f[j-1][k],f[j][k-1]); if (A.get(j-1).equals(B.get(k-1))) f[j][k]=Math.max(f[j][k],f[j-1][k-1]+1); } } System.out.println(f[A.size()][B.size()]); } }
🎍8.日志统计（滑动窗口）
题目链接：日志统计http://lx.lanqiao.cn/problem.page?gpid=T2730
这道题我觉得还是有一定难度的，至少在考场上如果第一次见，还是需要一定细心的能力的。因为做法确实很多，但有些细节处理起来很复杂。这里我才用的是滑动窗口的思想。
为什么会想到用滑动窗口来做呢？（理解此做法需要一定滑动窗口的思想）
因为一篇日志在长度为D的时间段内点赞达到k则为热帖。那我的想法则是维护一个长度为D的时间窗口，统计这个窗口内所有文章的被点赞数。用一个Map<Integer,List>来存储时间和这个时间里被点赞的日志，每次窗口移动一格时，先减去左边界的被点赞的文章，再加上被点赞的文章，如果判断此时它的点赞数达到k了，则将它标记为成为过热帖的日志。
代码转换：
import java.util.*; public class Main { static int N=100010; //记录文章区间出现次数 static int[] cut=new int[N]; //这个数组用来标记文章是否成为过热帖 static boolean[] isOK=new boolean[N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int d=sc.nextInt(); int k=sc.nextInt(); Map<Integer, List<Integer>> map=new HashMap<>(); for(int i=0;i<n;++i) { int a=sc.nextInt(); int b=sc.nextInt(); //全部存入到map中 if(map.containsKey(a)) map.get(a).add(b); else { ArrayList<Integer> list=new ArrayList<>(); list.add(b); map.put(a, list); } } //计算初始窗口内的值 int l=0; int r=d; for(int i=l;i<r;++i) { if(map.containsKey(i)) { for(int index:map.get(i)) { cut[index]++; //热度够了 if(cut[index]>=k) isOK[index]=true; } } } //滑动窗口枚举时间 while (r<N) { if(map.containsKey(l)) { for(int index:map.get(l)) cut[index]--; } l++; r++; if(map.containsKey(r)) { for(int index:map.get(r)) { cut[index]++; if(cut[index]>=k) isOK[index]=true; } } } for(int i=0;i<isOK.length;++i) { if(isOK[i]) System.out.println(i); } } }
