【2022-09-15】蚂蚁金服秋招笔试三道编程题

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经，目前已更新至美团、微软… 作者@TechGuide【全网同名】 点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

第一题： 题目描述

一个字母可以拆分成两个字母表顺序的前一个字母，例如，b可以拆分成aa，c可以拆分成bb。

打印出最短的可以拆分成 K 个 a 的字符串，字母顺序无所谓。

例如，k = 5, 最短字符串为 ca(或ac) = bba = aaaaa.

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

代码 Java版本

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());
}
// vx公众号关注TechGuide 实时题库 闪电速递

第二题： 题目描述

N个节点的树，根节点编号为1。

最开始，树上所有节点的值都为1。

你可以进行如下操作，选择一个子树，让子树的所有节点的值+1.

问，最少需要多少次操作才可以让每个节点的值等于其编号。

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

输入描述

3 // 3个节点 1 3 // 1-3相连 1 2 // 1-2相连

输出描述

3 // 2 节点子树，操作一次 // 3 节点子树，操作二次

思路

建图跑一个dfs就好，对于每个点，如果其子节点的标记值大于它，则把差值累加到答案上，输出即可。

（这里有个坑点，当出现任意一个父节点的标记值小于其子节点的标记值时，很明显是无法实现题目的情况的，也就是没有答案，这里应该输出-1，但是出题人没写，应该是题面漏放了）

代码 Java版本

static List 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 a>>b;
        a--,b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    function f = [&](ull i, ull fa){
        sumo+=i-fa;
        for(auto j:e[i])
            if(j!=fa)
                f(j,i);
    };
    for(auto i:e[0])
        f(i,0);
    cout