用友1027秋招笔试真题解析

前言

较为简单的一场，第一题考察自定义排序，第二题考察bfs，实际上建图才是难点，第三题直接分解因数即可。

第一题

给定一个字符串数组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.lengthn==names.leng
1<=n<=500
1<=scores[i]<=1000
names［i］由大小写英文字母组成
scores 中的所有值互不相同

思路与代码

核心思想非常简单，创建一个类，然后对这个类排序就行。

import java.util.*;
public class Solution {
    public static String[] sortNamesByScores(String[] names, int[] scores) {
        Person[] persons = new Person[names.length];
        for (int i = 0; i < names.length; i++) {
            persons[i] = new Person(names[i], scores[i]);
        }
        // 对 persons 数组进行排序，根据成绩降序排序
        Arrays.sort(persons, Comparator.comparingInt(Person::getScore).reversed());
        // 提取排序后的名字
        String[] sortedNames = new String[names.length];
        for (int i = 0; i < persons.length; i++) {
            sortedNames[i] = persons[i].getName();
        }
        return sortedNames;
    }
    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;
        }
    }
}

第二题

使用广度优先搜索算法(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"

说明

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

思路与代码

代码实现了对有向无环图的广度优先搜索（BFS）遍历，并将遍历结果以字符串形式返回。该遍历从指定的起始节点开始，按照广度优先的顺序遍历图中的节点，并将遍历结果按照逗号分隔的形式返回。

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("->");
            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();
    }

第三题

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

示例1

输入

2

输出

false

说明

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

思路与代码

直接分解因式就行。如果是，返回 true；否则，返回 false。

 public boolean isThree(int n) {
        Set<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;
    }