洛谷P9242 [蓝桥杯 2023 省 B] 接龙数列
这道题我觉得对我现在的水平来说很难，尝试了两三种写法，可行，但是时间超时，要不进行优化就不对
（想法一，dp[i][j]:i表示下标，j表示他的尾数（但是我在找是否是接龙序列这个问题花了太多的时间复杂度)
我搜不到java题解，看了三天，决心写完立马自己去写一个题解
首先最基础的 
总结，1的尾巴数=2的头数
因此，我们知道一个数只有第一个和第二个有用，那么我们是否可以进行用字符串，然后去charAt头和尾的操作呢，也当然可以。
他是应该最优秀的解法来吧，我感觉最难的状态表示，这个表示假如表示的好，会事半功倍
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int count=(int)1e9; int []f=new int [12]; for(int i=1;i<=n;i++){ //细节1:1的尾巴=2的头,因为我们的f表存储的是尾数的接龙数列长度 String b=scanner.next(); //细节2:f这个接龙序列一定是连续的吗，不一定，换一句话说，他的含义就是代表尾数，一个尾数的这个=一个头+1 //细节3:他是和他本身进行一个比较，因为有可能他的前面f[2]=2,但是他是12d他和前一个连接不起来，而他又会覆盖这个f[2].假如没有这个max比较，就会出现错误 f[b.charAt(b.length()-1)-'0']=Math.max(f[b.charAt(0)-'0']+1, f[b.charAt(b.length()-1)-'0']); } for(int i=0;i<=9;i++){ count=Math.min(n-f[i],count); } //存储当前值的下标和尾数 System.out.println(count); } }
边权为1的最短路问题
力扣1926.迷宫离入口最近的出口
class Solution { int []dx={0,0,1,-1}; int []dy={1,-1,0,0}; public int nearestExit(char[][] maze, int[] e) { int m=maze.length; int n=maze[0].length; boolean [][]vis=new boolean[m][n]; Queue<int[]>q=new LinkedList<>(); q.add(new int[]{e[0],e[1]}); vis[e[0]][e[1]]=true; int se=0; while(!q.isEmpty()){ se++; int sz=q.size(); for(int i=0;i<sz;i++){ int []m1=q.poll(); int a=m1[0]; int b=m1[1]; for(int j=0;j<4;j++){ int x=a+dx[j]; int y=b+dy[j]; if(x>=0&&x<m&&y>=0&&y<n&&vis[x][y]==false&&maze[x][y]=='.'){ if(x==0||y==0||x==m-1||y==n-1){ return se;} q.add(new int[]{x,y}); vis[x][y]=true; } } } } return -1; } }
力扣433.最小基因变化
边权为1的最短路径问题
一次基因变化就意味着这个基因序列中的一个字符发生了变化。
一步一步走
class Solution { public int minMutation(String startGene, String endGene, String[] bank) { //用来标记已经搜索过的状态 Set<String> vis=new HashSet<>(); //用来统计基因库里面的字符串 Set<String>hash=new HashSet<>(); char[]change={'A','G','C','T'}; for(int i=0;i<bank.length;i++){ hash.add(bank[i]); } Queue<String>q=new LinkedList<>(); if(startGene.equals(endGene))return 0; if(!hash.contains(endGene))return -1; // start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"] //队列中插入 q.offer(startGene); //同时我们做出标记 vis.add(startGene); int count=0; while (!q.isEmpty()){ //从入队列改变一次开始，就已经开始（默认第一回有效，第一回无效，则会最后返回负一） //因为我们要求的是有效的变化，假如他在基因库里面入一次队列，就应该是第二次变化了，因为反正都要去count++计数 count++; int sz=q.size(); while(sz!=0){ String t=q.poll(); //基因的序列是八个 for(int i=0;i<8;i++){ char[]tmp=t.toCharArray(); for(int j=0;j<4;j++){ //改变他的字符 tmp[i]=change[j]; //把他转换成字符串，用来判断，他是否已经被标记过，或者他是否和里面的基因库相等了 String next=new String(tmp); if(hash.contains(next)&&!vis.contains(next)) { //假如他是等于最终结果就会返回count的值，假如不是等于最后结果，那么就会返回-1（是这个结果就会返回最小的变化次数） if(next.equals(endGene)) return count; //倘若它这个并不等于这个最终结果，但是他是基因库里面的，那么就入队列，倘若他一直变化但是变不到最终结果，即使他的count=10000，他也是最后返回的是-1 q.add(next); vis.add(next); } } } sz--; } } return -1; } }
