#携程笔试# 20220830

四题AC（JAVA版）分享给大家

第一题

坑点在于要求不能有前导零 && 所有数字都要参与排列。最开始以为凑成偶数，自动去掉前导零就得了。。。

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        for(int i = 0; i < q; i++){
            int x = sc.nextInt();
            if((x & 1) == 0){
                System.out.println(x);
                continue;
            }
            if (x < 10){
                System.out.println(-1);
                continue;
            }
            String str = String.valueOf(x);
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < str.length(); j++){
                int num = str.charAt(j) - '0';
                if(j + 1 < str.length() && (num & 1) == 0 && str.charAt(j + 1) != '0'){
                    sb.append(str.substring(j + 1));
                    sb.append(num);
                    break;
                }else{
                    sb.append(num);
                }
            }
            if (str.equals(sb.toString())){
                System.out.println(-1);
                continue;
            }
            System.out.println(sb);
        }
    }

第二题

贪心：先计算 you 的个数 * 2，再对剩余的连续 n 个 o，取 n - 1 分。注意对 n < 2 的情况特殊处理。

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < q; i++){
            String[] split = sc.nextLine().split(" ");
            int a = Integer.parseInt(split[0]), b = Integer.parseInt(split[1]), c = Integer.parseInt(split[2]);
            int ans = Math.min(a, Math.min(b, c));
            b -= ans;
            ans *= 2;
            ans += b >= 2 ? b - 1 : 0;
            System.out.println(ans);
        }
    }

第三题

建图，认为当前节点及孩子节点的 r g b 个数大于 0 && 除该子树外的其他节点的 r g b 之和也大于0，则满足两个连通块各恰有三种颜色。

dfs

坑点在于题目未指出根节点，所以需双向建图 && 使用 visit 数组记录已访问节点。而树作为连通图，从任意节点开始遍历都可以了。

    static int ans = 0;
    static int r, g, b;
    static boolean[] vis;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String str = scanner.nextLine();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == 'r') r += 1;
            if (c == 'g') g += 1;
            if (c == 'b') b += 1;
        }

        // build tree
        ArrayList<Integer>[] nodeMap = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            nodeMap[i] = new ArrayList<>();
        }

        for (int i = 1; i < n; i++) {
            int x = scanner.nextInt() - 1;
            int y = scanner.nextInt() - 1;
            nodeMap[x].add(y);
            nodeMap[y].add(x);
        }

        vis = new boolean[n];
        dfs(str, nodeMap, 0);
        System.out.println(ans);
    }

    public static ChildColorNumber dfs(String str, ArrayList<Integer>[] nodeMap, int node) {
        vis[node] = true;
        ArrayList<Integer> children = nodeMap[node];
        ChildColorNumber colorNumber = new ChildColorNumber();

        for (Integer child : children) {
            if (vis[child]) continue;
            ChildColorNumber ccn = dfs(str, nodeMap, child);
            if (ccn.red > 0 && ccn.green > 0 && ccn.blue > 0 && ccn.red < r && ccn.green < g && ccn.blue < b) ans += 1;
            colorNumber.red += ccn.red;
            colorNumber.green += ccn.green;
            colorNumber.blue += ccn.blue;
        }
        if (str.charAt(node) == 'r') colorNumber.red += 1;
        if (str.charAt(node) == 'g') colorNumber.green += 1;
        if (str.charAt(node) == 'b') colorNumber.blue += 1;
        return colorNumber;
    }
}

class ChildColorNumber {
    public int red;
    public int green;
    public int blue;

    public ChildColorNumber() {
        this.red = 0;
        this.blue = 0;
        this.green = 0;
    }
}

第四题

计算包括当前节点之前的任意两相邻数差的绝对值的最大值、再记录包括当前节点之后的任意两相邻数差的绝对值的最大值。

暴力遍历每一个节点，对其作平滑处理：将该节点改成左右两点平均值后的绝对值最大值。再取三者最大值即为修改当前节点所能得到的平滑值。

#携程笔试# 20220830

全站热榜