字节跳动 笔试

时间：120min
题型：编程*4（20‘+25’+25‘+30’）ACM模式
通过了大概80分左右，已约面

1、有一个长为n的只有0、1组成的字符串s。需要对s执行k次转置操作。要想使得s的字典序最小，求出最小字典序s。 任意一个位置的0变成1或者1变成0称为一次转置。字典序的比较方法：比较第一个不同的字符。输入第一行为s的长度n和转置操作次数k，第二行为只有'0'和'1'组成的字符串s，输出为k次操作后字典序最小的字符串s

2、有一个n个点、n-1条边的树。如果树上存在一个点w，使得原始的树上存在边(u,w)和(w,v)，那么可以添加一条边(u,v)。求最多可以添加多少条边。树是指一张任意两个点都连通、且不存在环的一张图。 输入第一行为树上的点数n，之后n-1行，第i行为树上第i条边的节点ui和vi。输出为最多可以添加的边数。

3、有一个长度为n的数组a1,a2,...,an，每次询问一个空间[l,r]，计算数组a的所有长度大于等于l且小于等于r的子数组之和的最大值是多少。 输入第一行为数组中元素数量n和询问次数q，第二行为数组元素a1,a2,...,an，之后q行每行输入l和r表示询问区间。 输出q行，表示对于每次询问的答案。（对时间复杂度要求比较高）

4、有一个长度为n的数组a1,a2,...,an，求出有多少个严格单调递减的子序列。结果可能很大，对10^9+7取模后再输出。

【如果对你有帮助能给我送个花花吗】
#字节求职进展汇总#