小红书算法笔试0423

之前小红书一志愿挂了今天再做次笔试，不知道能不能捞起来
第一题 对一个数组a可以进行两种操作：1. a[0]==0，删除a[0]；2. a[0]!=0，a[0]减一并在数组a末尾添加a[0]个a[0]-1
求让输入的数组a变为空的操作数，答案模10^9+7
思路：对于a[0]==x，设消除它的操作次数为f(x)，则f(x)=x+1+x*f(x-1)+...+1*f(0)，求sum([f(x) for x in a])即可；要注意两点：计算过程中取模；不要用递归要用循环，否则爆栈（而且循环的时候加粗部分不用重复计算）。最后时间复杂度是O(max(a)+len(a))
第二题 给一个树，每个节点是红色或者白色，求第k大红色连通块节点数
思路：dfs+染色找所有连通块大小，排序返回第k大的值，时间负复杂度O(N+ClogC)，N是节点数，C是红色连通块数
第三题 定义一个字符串s的A值为：包含的"red"子序列数量，定义一个字符串s的B值为：s所有连续字串的A值之和
给一个数字n，输出长度为n且仅由"r" "e" "d"三种字符构成的所有字符串的B值之和，答案模10^9+7
思路：先求所有长度为i的字符串的A值之和 (3<=i<=n)，得到数组T，再求所有长度为n的字符串的B值之和。做起来很像概率论的题。。
桀桀，又是0offer的一天 #offer都去哪了#
#小红书信息集散地#