9.22 字节跳动笔试

#字节求职进展汇总#

1. 给一个树，若存在边(u,w)和(w,v)，则可以添加一条边(u,v)，求最多可以添加多少边
针对每个节点u，计算与其相连的边数sz，则可以添加 sz*(sz-1)/2，O(n)

2. 有一个长为n的数组ai，每次询问[l, r]，求所有长度大于等于l小于等于r的子数组之和最大值（注意快读）
首先暴力求解所有长为x的子数组之和的最大值，然后维护mx[i][j]表示长度大于等于i小于等于j的子数组之和最大值，后续O(1)查找。总的时间复杂度O(n^2+q)

3. 有一个长为n的字符串s，每次可以将si按照字母表的顺序循环右移一位（即a->b, z->a）求使字符串相邻字符都不相等的最小操作数
考虑dp。dp[i][j]表示前i个字符满足条件且第i个字符为j时的最小操作次数，对于第i+1个字符遍历a-z（k=0-26），计算操作次数（v=(k+26-s[i+1]+'a')%26）并进行状态更新dp[i+1][k]。时间复杂度O(26*26n)
优化：对于dp[i]在计算dp[i+1][k]时，只需要记录dp[i]内最小值及对应字符和次小值即可，若k=最小值对应字符，则用次小值更新dp[i+1][k]，否则直接用最小值更新；同时，k也可以只考虑dp[i]内最小值对应字符，以及除此之外s[i+1]右移操作最少的字符，可以将复杂度降到O(2n)

4. 有一个长为n的数组ai，求有多少个严格单调递减的子序列，对10^9+7取余
经典的离散化+树状数组问题。将每个ai按大小映射到1-m（记作bi），用树状数组维护以j结尾的子序列个数的前缀和，总的减掉就是以大于j结尾的子序列个数，类似lc315