携程3.29后端笔试全AC分享（Java实现）

第一题，遍历。

import java.util.*;

public class Main {
    private static int cntCircle(String str) {
        int res = 0;
        for (int i = 0; i < str.length(); ++i) {
            char ch = str.charAt(i);
            if (ch == '0' || ch == '6' || ch == '9') ++res;
            else if (ch == '8') res += 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        System.out.println(cntCircle(str));
    }
}

第二题，贪心。让下标为0, 2, 4, ...(共k个)的位置递增地放最大的k个数，其余下标位置递增地放剩余n-k个数。

import java.util.*;

public class Main {
    private static int[] find(int n, int k) {
        int ok = n - k + 1, no = 1;
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0 && i < 2 * k) res[i] = ok++;
            else res[i] = no++;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] res = find(n, k);
        for (int i = 0; i < n; ++i) {
            System.out.print(res[i]);
            if (i != n - 1) System.out.print(' ');
            else System.out.println();
        }
    }
}

第三题，查找，找一组x、y，使得(x!-1)*y和n离得尽可能近。用一个Map保存(x!-1)，注意用Long（x保存到13就够了，判断标准是x=12时结果不超过n，留一个超过n的备用hhh）。然后遍历x，看与n/(x!-1)相近的两个y（注意排除2）和x算出来的结果，哪个离n更近。

import java.util.*;

public class Main {
    private static int[] getRes(long n) {
        int x = 1, y = 1, i;
        Map<Integer, Long> dp = new HashMap<>();
        dp.put(1, 1L);
        for (i = 2; dp.get(i - 1) * i <= n; ++i) dp.put(i, dp.get(i - 1) * i);
        dp.put(i, dp.get(i - 1) * i);
        for (i = 1; dp.containsKey(i); ++i) dp.put(i, dp.get(i) - 1);
        for (i = 3; dp.containsKey(i); ++i) {
            int j = (int) (n / dp.get(i));
            if (getDist(dp.get(i), j, n) < getDist(dp.get(x), y, n)) {
                x = i;
                y = j;
            }
            if (j + 1 != 2 && getDist(dp.get(i), j + 1, n) < getDist(dp.get(x), y, n)) {
                x = i;
                y = j + 1;
            }
            if (getDist(dp.get(i), j + 2, n) < getDist(dp.get(x), y, n)) {
                x = i;
                y = j + 2;
            }
        }
        return new int[]{x, y};
    }

    private static long getDist(long a, long b, long n) {
        return Math.abs(a * b - n);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        int[] res = getRes(n);
        System.out.println(res[0] + " " + res[1]);
    }
}

第四题，树（我用图保存的，然后用任意度为1的节点当root）+动态规划+深搜。

在dfs中，传入father代表调用dfs的节点作为父亲，则其余邻接节点是孩子。

dpOn[i]代表下标为i的节点选一条和孩子连接的边涂上颜色以后，以该节点为根的子树得到的权重最大值；

dpOff[i]代表下标为i的节点和所有孩子连接的边均不涂色的情况下，以该节点为根的子树得到的权重最大值。

则状态转移如下思考：

dpOn[i]的状态就是选一个孩子，把连接的边涂色，贡献的权重为边的权重和该孩子不选边涂色的权重最大值w+dpOff[child]，其余孩子贡献的权重为选边涂色和不选边涂色的权重最大值；

dpOff[i]的状态就是所有孩子选边涂色和不选边涂色的权重最大值之和。

import java.util.*;

public class Main {
    private static long[] dpOn;
    private static long[] dpOff;

    private static long getMaxWeight(int n, List<Map<Integer, Long>> G) {
        if (n == 1) return 0;
        int root = 0;
        while (G.get(root).size() != 1) ++root;
        dpOn = new long[n];
        dpOff = new long[n];
        dfs(G, root, -1);
        return Math.max(dpOn[root], dpOff[root]);
    }

    private static void dfs(List<Map<Integer, Long>> G, int t, int father) {
        if (G.get(t).size() == 1 && G.get(t).containsKey(father)) {
            dpOn[t] = 0L;
            dpOff[t] = 0L;
        } else {
            dpOn[t] = 0L;
            dpOff[t] = 0L;
            long tmp = 0;
            for (int v : G.get(t).keySet()) {
                if (v == father) continue;
                dfs(G, v, t);
                tmp += Math.max(dpOn[v], dpOff[v]);
                dpOff[t] += Math.max(dpOn[v], dpOff[v]);
            }
            for (int v : G.get(t).keySet()) {
                if (v == father) continue;
                dpOn[t] = Math.max(dpOn[t], tmp - Math.max(dpOn[v], dpOff[v]) + dpOff[v] + G.get(t).get(v));
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Map<Integer, Long>> G = new ArrayList<>();
        for (int i = 0; i < n; ++i) G.add(new HashMap<>());
        for (int i = 0; i < n - 1; ++i) {
            int a = in.nextInt() - 1, b = in.nextInt() - 1;
            long w = in.nextLong();
            G.get(a).put(b, w);
            G.get(b).put(a, w);
        }
        System.out.println(getMaxWeight(n, G));
    }
}