微软 软开8.19笔试

public int solution(int[] X, int[] Y, int W) {
    int length = X.length;
    // 定义数组记录修复状态
    boolean[] used = new boolean[length];
    // 只需要关注横坐标 对其进行排序
    Arrays.sort(X);
    // 记录结果
    int result = 0;
    // 遍历一次整个数组
    for (int i = 0;i < length;i++) {
        // 如果已经修复 则跳过
        if (used[i]) {
            continue;
        }
        // 修复当前坑
        used[i] = true;
        result++;
        int cover = X[i]+ W;
        // 把在覆盖范围内的坑也修复
        for (int j = i + 1;j < length;j++) {
            if (X[j] <= cover) {
                used[j] = true;
            }else {
                break;
            }
        }
    }
    // 返回结果
    return result;
}

public String solution(String S) {
    // 定义一个map存储数字对应出现的次数
    Map<Character, Integer> countMap = new HashMap<>();
    // 定义一个list存储出现次数大于等于1的数字
    List<Character> countList = new ArrayList<>();
    // 定义一个Set去存储出现过的数字，方便后续取出只出现一次的最大数
    Set<Character> allSet = new HashSet<>();
    // 创建结果集
    StringBuilder sb = new StringBuilder();
    // 遍历一次字符串进行初始化统计
    for (char c : S.toCharArray()) {
        countMap.put(c, countMap.getOrDefault(c, 0) + 1);
        allSet.add(c);
        if (countMap.get(c) >= 2) {
            countList.add(c);
        }
    }
    // 对countList排序
    countList.sort((a, b) -> b - a);
    for (char c : countList) {
        while (countMap.get(c) >= 2) {
            // 使用掉就要减去
            countMap.put(c, countMap.get(c) - 2);
            if (c == '0' && sb.length() == 0) {
                continue;
            }
            sb.append(c);
        }
    }
    String reverse = new StringBuilder(sb.toString()).reverse().toString();
    // 对Set进行排序
    List<Character> set = new ArrayList<>(allSet);
    set.sort((a, b) -> b - a);
    for (Character c : set) {
        if (countMap.get(c) > 0) {
            sb.append(c);
            break;
        }
    }
    sb.append(reverse);
    return sb.toString().equals("") ? "0" : sb.toString();
}

public int solution(int[] A, int[] B) {
    // 找到与0相接的结点
    List<Integer> connectList = find(0, A, B);
    for (int i : connectList) {
        // 分别递归
        dfs(0, i, A, B);
        // 每个节点过来都需要汽油
        fuel++;
    }
    return fuel;
}

public int dfs(int parent, int now, int[] A, int[] B) {
    // 找到当前节点的相接节点
    List<Integer> connectList = find(now, A, B);
    // 默认一个人
    int people = 1;
    for (int i : connectList) {
        // 如果与父节点相同则不需要计算
        if (i == parent) {
            continue;
        }
        // 获取子节点的人数
        int result = dfs(now, i, A, B);
        // 每个节点过来都需要汽油
        fuel++;
        // 人数++
        people += result;
    }
    // 大于5个人的时候需要加汽油
    if (people > 5) {
        fuel += (people / 5) - 1;
    }
    return people;
}

// 用于寻找相接的结点
public List<Integer> find(int target, int[] A, int[] B) {
    List<Integer> list = new ArrayList<>();
    for (int i = 0;i < A.length;i++) {
        if (A[i] == target) {
            list.add(B[i]);
        }
        if (B[i] == target) {
            list.add(A[i]);
        }
    }
    return list;
}