[数据结构与算法]【蓝桥杯备考】Acwing周赛 第41场 Java题解

🏠：博客首页： 进击的波吉
📕：今日分享的文章： Acwing周赛 第41场 Java题解
💝：坚持刷Acwing周赛，分享前三题题解🎈
🌱：Boji 还在努力准备蓝桥杯 ，如有疑问、疏漏之处，请多多指点🙏
??：自学成长的路上，感谢大家相伴！No hurry ， No Pause ！💝

?? 距离蓝桥杯大约还有一个月时间，决定开刷 Acwing周赛，y总近几期的周赛难度也是对标蓝桥杯的，吸纳了别人优秀的题解，总结出来Java题解！

4308. 组合字符串

??求最小的组合字符串 ：第二个字符串可以只取第一个，取第一个字符串中比较小的且比第二个字符串首位小的字符！

题解：

import java.util.* ;

public class Main{
    public static  void main(String[] args) {
        Scanner sc = new Scanner(System.in) ;

        char[] a = sc.next().toCharArray() ;
        char[] b = sc.next().toCharArray() ;
         String str = String.valueOf( a[0]);
         String str1 = String.valueOf(b[0]) ;

        for (int i = 1; i< a.length; i++) {
            if (a[i] < str.charAt(i-1)) str += String.valueOf(a[i]) ;
            else if (a[i] < str1.charAt(0)) str += String.valueOf(a[i]) ; 
            else break ;
        }
        String s = str + str1 ;
        System.out.println(s) ;
    }
}

4309. 消灭老鼠

?? 主要难点：

• 斜率表示 ，精读的范围在测试中，就被卡了，因此建议 斜率的问题 用向量表示
• 数据保存，用set方法存储 slope，会默认判重
• 欧几里得公式，求最大公约数公式 （模板熟记）

题解

import java.util.* ;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in) ;
        int n = sc.nextInt() ;
        int x0 = sc.nextInt() ;
        int y0 = sc.nextInt() ;
        Set<String> slopes = new HashSet() ; 
        while(n-- > 0) {
            int a = sc.nextInt() ;
            int b = sc.nextInt() ;
            //计算 横纵坐标的差值
            a -= x0 ;
            b -= y0 ;
            int c = gcd(a, b) ;
            //set可以判重，因此只需要保存 斜率的最简比
            slopes.add(a/c + "/" + b/c ) ;
        }
        System.out.println(slopes.size()) ;
    }
    //欧几里得公式 求最大公约数 
    public static int gcd(int a, int b) {
        return b!=0 ? gcd(b, a%b): a ;
    }
}

4310. 树的DFS

?? 主要难点：

• 邻接表的创建， 用ArrayList
• 坐标的转换与理解，DFS中对应第i个点 以及它的下标
• dfs遍历二叉树的理解

import java.io.* ;
import java.util.* ;

public class Main {
    public static int N = (int)2e5+10 ;
    public static int[] q = new int[N] ; //存储dfs中第i个点是哪个
    public static int[] p = new int[N] ; //存储点i在 dfs中的下标
    public static int[] sz = new int[N] ; //存储点i的根子树大小
    public static int n, m ;
    public static int top = 0 ; //存储当前存储的第几个数
    public static ArrayList<Integer>g[] = new ArrayList[N] ; //存储邻接表
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ") ;
        n = Integer.parseInt(s[0]) ;
        m = Integer.parseInt(s[1]) ;
        //创建邻接表
        for (int i = 0; i < N ;i++) g[i] = new ArrayList<>() ;
        
        
        String[] str = br.readLine().split(" ") ;
        int idx = 0 ;
        for (int i = 2; i<= n; i++) {
            //存储父节点t的邻边， 构建邻接表
            int t = Integer.parseInt(str[idx++]) ;
            g[t].add(i);
        }
        
        dfs(1) ; //遍历树，初始化二叉树的 q[i] 和 p[i]值 
        
        while(m-- >0 ){
            String[] s2 = br.readLine().split(" ") ;
            int u = Integer.parseInt(s2[0]) ;
            int k = Integer.parseInt(s2[1]) ;
            // k 超过u子树的范围, 则返回-1
            if (k > sz[u]) bw.write("-1\n") ;
            else bw.write(q[ p[u] + k-1 ] + "\n" ) ; //在范围中,则去 根节点u的第k-1个数 
        }
        
        bw.flush() ;
        bw.close() ;
        br.close() ;
    }
    
    public static void dfs(int u) {
        sz[u] = 1 ; //一个点对应一个节点数
        q[top] = u ;//dfs 第 top 个数 为 u ;
        p[u] = top ;//dfs中 u 的下标为 top ;
        top++ ; //top +1 
        
        //遍历子树，若邻接表为空，跳过; 若邻接表不为空， 遍历子树
        for (var v : g[u]) {
            dfs(v) ;
            sz[u] += sz[v] ; //记录子树段的大小
        }
    }
}