P9242 [蓝桥杯 2023 省 B] 接龙数列JAVA,边权为1的最短路问题,洛谷P9242 [蓝桥杯 2023 省 B] 接龙数列​编辑力扣1926.迷宫离入口最近的出口力扣433.

简介: P9242 [蓝桥杯 2023 省 B] 接龙数列JAVA,边权为1的最短路问题,洛谷P9242 [蓝桥杯 2023 省 B] 接龙数列​编辑力扣1926.迷宫离入口最近的出口力扣433.

洛谷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;
    }
}

相关文章
|
21天前
|
Java
2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
28 4
|
21天前
|
Java
蓝桥杯Java组暴力递归搜图
蓝桥杯Java组暴力递归搜图
19 4
|
21天前
|
Java
2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
21 3
|
21天前
|
Java
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
22 2
|
21天前
|
Java
2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
12 1
|
21天前
|
Java
2023蓝桥杯大赛软件类省赛Java大学B组G题 买二增一 队列的简单应用
2023蓝桥杯大赛软件类省赛Java大学B组G题 买二增一 队列的简单应用
14 1
|
21天前
|
存储 前端开发 算法
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
11 0
|
23天前
|
算法 Java 编译器
第十五届蓝桥杯Java软件开发大学B组自我经验小结
第十五届蓝桥杯Java软件开发大学B组自我经验小结
13 0
|
23天前
|
Java API
备战第十五届蓝桥杯Java软件开发大学B组常见API记录
备战第十五届蓝桥杯Java软件开发大学B组常见API记录
12 0
|
23天前
|
Java
2023蓝桥杯大赛省赛Java大学B组 矩形总面积
2023蓝桥杯大赛省赛Java大学B组 矩形总面积
11 0