用友1027秋招笔试

用友1027秋招笔试

也是第一次在牛客上看到这公司，听说给的薪资还算可以。刚好找来秋招题目练练手，感觉还算不错，第二题思考量有点大，其余的还好~

​

1027.T1

1. 题目说明

给定一个字符串数组names，和一个由互不相同的正整数组成的数组 scores。

两个数组的长度均为n。

对于每个下标i，names［i］和scores［i］表示第i个人的名字和成绩。

请按成绩 降序 顺序返回对应的名字数组names。

示例1

输入

[“Mary”,“John”,“Emma”],[180,165,170]

输出

[“Mary”,“Emma”,“John”]

示例2

输入

["Alice","Bob","Bob"],[155,185,150]

输出

["Bob","Alice","Bob"]

备注

ames.length==scores.length==names.length
1<=n<=500
1<=scores[i]<=1000
names［i］由大小写英文字母组成
scores 中的所有值互不相同

​

2. 分析解答

• 需要创建一个类，利用规则进行排序即可

• 注意输入的格式：

  • 输入字符串，将字符串的首尾[]进行去除，并且以，进行分割

  • 读入字符数组

  • 对数组进行排序、根据成绩降序排列

    ​

具体代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class title1 {
    
    //创建一个类，然后对类进行排序即可/
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);

        //两个字符串的读入：
        String s=in.next().trim();
        String[] names=s.substring(1,s.length()-1).split(",");
        String sc=in.next().trim();
        String[] sc1=sc.substring(1,sc.length()-1).split(",");

        int n=names.length; //给出names的数组长度关系
        int[] scores=new int[n];

        for(int i=0;i< names.length;i++){
            if(!sc1[i].isEmpty())
           scores[i] =Integer.parseInt(sc1[i]);//注意进行类型的转换
        }

        Person[] p=new Person[n];
        for(int i=0;i<n;i++){
            p[i]=new Person(names[i],scores[i]);
        }
        //对persons数组进行排序，根据成绩降序排序，对象、类
        Arrays.sort(p, Comparator.comparingInt(Person::getScore).reversed());
        //提取排序后的名字
        String[] sortedNmaes=new String[n];
        for(int i=0;i<n;i++){
            sortedNmaes[i]=p[i].getName();
//            System.out.print(Arrays.toString(sortedNmaes) +" "); //逐个进行分析，找到最逐步的分析策略
        }
        System.out.println(Arrays.toString(sortedNmaes));

    }
   static class Person{
        private final String name;
        private final int score;
        public Person(String name,int score){
            this.name=name;
            this.score=score;
        }
        public String getName(){
            return name;
        }
        public int getScore(){
            return score;
        }
    }
}

​

• 复杂度分析：

  • 时间复杂度：$O(m+nlog_n)$

    • 对名字和分数的读取需要遍历整个输入字符串，时间复杂度为O(m)，其中m为输入字符串的长度。
    • 创建Person对象数组的时间复杂度是O(n)，其中n为名字的数量（也是分数的数量）。
    • 对Person对象数组进行排序的时间复杂度为O(nlogn)，其中n为Person对象数组的长度。
    • 提取排序后的名字数组的时间复杂度为O(n)，其中n为名字的数量（也是分数的数量）。
    • 总体来说，代码的时间复杂度为O(m + nlogn)，其中m表示输入字符串的长度，n表示名字的数量（也是分数的数量）。

  • 空间复杂度：$O(n)$

    代码的空间复杂度主要由输入的名字数组、分数数组和Person对象数组占用的空间决定，为O(n)，其中n为名字的数量（也是分数的数量）

    ​

1027.T2

1. 题目说明

使用广度优先搜索算法(BFS) ，遍历有向无环图 (DAG) ，并输出遍历的节点的顺序。

输出的节点顺序要求稳定，需要避免使用随机顺序，导致验证失败。

如上图所示，当输入:“A->B”,"A->C,D”,"C->E”,"E->F”,"D->G”,"G->E"(注意:->和前后的空格的存在是不确定的,Key也可能出现多次)

BFS输出为:“A”,"B”,"C”,"D”,"E”,"G","F”(注意: 输出需要稳定，需要按照传入字 符串的顺序构建图)

建议:

1.优先解析原始数据为图的节点结构，如采用定义内部类的方式: 2.需要注意构建结构时，不要遗漏“B’"F这种只有入度，没有出度的节点

示例1

输入

["A->B","A->C,D","C->E","E->F","D->G","G->E"],"A"

输出

"A B,C,D.E.G,F"

说明

输出结果格式化时，不要有多余的空格，否则结果对比可能失败

​

2. 解答分析

• 代码实现了对有向无环图的广度优先搜索（BFS）遍历

• 并将遍历结果以字符串形式返回。该遍历从指定的起始节点开始，按照广度优先的顺序遍历图中的节点，并将遍历结果按照逗号分隔的形式返回。

• 注意引入队列的数据结构方法

  ​

3. 具体代码

• 代码的功能作用如下：

  1. 根据输入的节点数组和起始节点构建一个有向图的邻接表表示，使用Map<String, List<String>>来表示每个节点与其邻居节点的关系。

  2. 使用广度优先搜索算法进行遍历，将起始节点加入结果列表res，并标记为已访问。

  3. 使用队列Deque<String> q来存储待访问的节点。

  4. 循环直到队列为空：从队列中取出当前节点cur，获取其邻居节点集合neighbors，遍历邻居节点集合并判断是否已经访问过，若未访问过，则将该邻居节点加入结果列表res、标记为已访问，并加入队列q中。

  5. 将结果列表res转换为字符串形式，并返回。

     ​

public static String dagBfsTraversal(String[] nodes,String startNode){
        int len = nodes.length;
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            String node = nodes[i];
            String[] s1 = node.split("->");
            if(s1.length<2){
                continue;
            }
            String f = s1[0].trim();
            String[] s2 = s1[1].split(",");
            String[] ts = new String[s2.length];
            for (int j = 0; j < s2.length; j++) {
                ts[j] = s2[j].trim();
            }
            List<String> ls = map.getOrDefault(f, new ArrayList<>());
            for (String t : ts) {
                ls.add(t);
            }
            map.put(f, ls);
        }
        List<String> res = new ArrayList<>();
        Set<String> set = new HashSet<>();
        Deque<String> q = new ArrayDeque<>();
        res.add(startNode);
        set.add(startNode);
        q.add(startNode);
        while (!q.isEmpty()) {
            String cur = q.poll();
            List<String> neighbors = map.getOrDefault(cur,new ArrayList<>());
            for (String neighbor : neighbors) {
                if (set.add(neighbor)){
                    res.add(neighbor);
                    q.add(neighbor);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (String s : res) {
            sb.append(s).append(",");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

​

• 复杂度分析：

  • 时间复杂度：$O(n+m)$

    • 广度优先搜索的过程中，每个节点最多被访问一次，每个边最多被访问一次，因此时间复杂度为O(n+m)，其中n为节点数，m为边数。

  • 空间复杂度：$O(n)$

    • 引入了队列的数据结构，长度是n.

    ​

1027.T3

1. 题目说明

给定一个正整数 n，如果n 恰好有三个(不同)正除数，返回 true; 否则，返 false。

示例1

输入

2

输出

false

说明

2 只有两个正除数:1和2

​

2. 解答分析

• 唯手熟尔，直接暴力分解因式，注意因子需要唯一确定。需要用到的是：HashSet的数据结构，举例说明：

  • 1. 输入9；输出`true``

       • 9只能分为1,3,9这三个因子

    2. 输入8；输出false

       • 8的分解因子有：1,2,4,84个

         ​

3. 具体代码

import java.util.HashSet;
import java.util.Scanner;

public class title3 {
    // 给定一个正整数n，如果此时恰好存在三个正除数，返回true;
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        boolean flag=isThree(n);
        if(flag){
            System.out.println("True");
        }
        else System.out.println("false");

    }
    public static boolean isThree(int n){
        HashSet<Integer>set=new HashSet<>(); //去掉重复的字符
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                set.add(i);
                set.add(n/i);
            }
        }
        if(set.size()==3){
            return true;
        }
        return false;
    }
}

​

• 复杂度分析：

  • 时间复杂度：$O(1)$

    1. 输入：从标准输入中读取一个整数n，时间复杂度为O(1)。
    2. isThree函数：判断n是否存在恰好三个正约数的方法。其核心思路是通过枚举n的所有因子，将因子添加到HashSet中去重，然后判断HashSet的大小是否为3。时间复杂度主要取决于枚举n的因子，即在1到sqrt(n)之间的所有正整数，时间复杂度为O(sqrt(n))。而HashSet的add操作的平均时间复杂度为O(1)，因此最终isThree函数的时间复杂度为O(sqrt(n))。
    3. 输出：最终输出结果到标准输出，时间复杂度为O(1)。

  • 空间复杂度：$O(n)$，引入了HashSet

    ​

加油😘