蚂蚁笔试 研发岗 09.15 AC

第一题

一个字母可以拆分成两个字母表顺序的前一个字母，例如，b可以拆分成aa，c可以拆分成bb。
打印出最短的可以拆分成 K 个 a 的字符串，字母顺序无所谓。
例如，k = 5, 最短字符串为 ca(或ac) = bba = aaaaa.

K = 1, a; K = 2, b; K = 4, c;.....

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while(n > 0){
            if((n&1) == 1){
                sb.append((char)('a'+i));
            }
            i++;
            n = n >> 1;
        }
        System.out.println(sb.toString());
    }

第二题

N个节点的树，根节点编号为1。
最开始，树上所有节点的值都为1。
你可以进行如下操作，选择一个子树，让子树的所有节点的值+1.
问，最少需要多少次操作才可以让每个节点的值等于其编号。

隐藏case，若进行上述操作无法使得节点值等于编号，则打印-1.

输入：
3 // 3个节点
1 3 // 1-3相连
1 2 // 1-2相连
输出：
3
// 2 节点子树，操作一次
// 3 节点子树，操作二次

    static List<List<Integer>> list;
    static boolean vis[];
    static long ret;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        vis = new boolean[n+1];
        ret = 0;
        list = new ArrayList<>();
        for(int i = 0; i <= n; i++){
            list.add(new ArrayList<>());
        }
        for(int i = 1; i < n; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            list.get(a).add(b);
            list.get(b).add(a);
        }
        dfs(1, 1);
        System.out.println(ret);
    }

    public static void dfs(int node, int del) {
        if(node < del || ret == -1) {
            ret = -1;
            return;
        }
        ret += node - del;
        vis[node] = true;
        for(int child : list.get(node)){
            if(!vis[child]){
                dfs(child, node);
            }
        }
    }

第三题

解法：
状态压缩

    public static void main32(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        int n = s.length();

        int arr[]=new int[n+1];
        for(int i = 1; i <= n; i++){
            arr[i] = arr[i-1] ^ (1 << (s.charAt(i-1) - 'a'));
        }

        long ret = 0;
        int cnt[] = new int[1<<26];

        // 可以和上面的for循环合并
        for(int i = 0; i <= n; i++){
            for(int j = 0; j < 26; j++){
                int tmp = arr[i] ^ (1 << j);
                ret += cnt[tmp];
            }
            cnt[arr[i]]++;
        }

        System.out.println(ret);
    }