校招，后端开发美团：到店，实习转正，北京，(n+3)*15.5阿里国际：AI技术部，做AI商业化创新的，杭州，n*16+1.2*12的补贴字节：国际电商供应链，珠海，n815+4*12的补贴南方人，目前倾向于阿里或者字节。到手差不多，两个城市都能接受（回家时间差不多），阿里业务好点，但是不确定后端进去会不会是打杂的。字节感觉在上升期，电商也是重点业务，但是不确定能不能接受国际电商的强度（看好多人都说很卷）。大佬们能不能给点具体意见。

第一题，电影的最大期待值。如果要每天都更新之前的电影到今天还有多少期待值，然后和今天的电影比，那就太麻烦了，可以把所有电影的期待值都推回到第一天，第i天的电影在第一天的期待值为ai+d*(i-1)，然后用大顶堆记录，每次先更新再取堆顶即可，取出堆顶后减去d*(i-1)得到实际的期待值。这里不用考虑减去后小于0的问题，因为今天上映的电影的期待值是一定大于0的，也就是堆里面一定有一个大于0的元素。第二题，使数组元素相等的最小次数。遍历所有元素，如果%x的值不相同（用set记录，判断size!=1），则返回-1；否则所有数除以x，因为除之后可以直接计算操作次数（除之前一次加减x，除之后一次加减1）。这里直接说结论，把所有数组元素除x之后的结果排序，中间位置（第m*n/2个元素）就是要最终变成的数，用for循环计算操作次数即可。具体证明可以看力扣第462题，最小操作次数使数组元素相等 II。第三题，dp+滚动数组优化过了60%。用dp[n+1][k]记录数量，具体来说，dp[i][j]表示长度为i、相邻字符不同的字符串有多少个，显然dp[i][j] = dp[i-1][j] + 25 * dp[i-1][j-1]，最后结果为dp[n]的数组的和，转移过程和最后求和都需要注意取模。又显然dp[i]只与dp[i-1]有关，且n,k都是1e5级别的，所以可以用滚动数组进行优化。这个解法过了60%，超时。正确的解法（感觉对但是没调出来）应该是，长度为n的数组有n-1个相邻字母对，相邻字母对不同的数量不超过k个，则枚举不同的相邻字母对的数量为0对于确定的i，可能有C(n-1, i)种不同的选择方案，每个不同的字母对可以有25种选择，相同的字母对只能有一种选择，第一个字母有26种选择，因此每个i的总字符串数量应该有26*25^i*C(n-1, i)种，最终结果是前面这个的和。但是这种解法我没写出来，细节上估计有点问题，不知道有没有大佬过了。

第一题，记录出现次数然后排序即可。我是用map给每个字符串标号，然后用int数组记录，最后用一个int数组排序。第二题，用map记录数字的出现次数，如果有只出现过一次的数字，或者总共有至少3个不同数字，则返回数组长度。否则为类似"1 2 1 2 1 2 1 2"的情况，返回数组长度/2+1（每次删除触发一次自动删除，长度-2；最后到长度为2的时候可以删除两次）。第三题，用floyd计算最短路，两次for循环遍历枚举，过了一半，不清楚wa在哪了。考虑了距离爆int的情况，但是可能没考虑全，有可能是这个原因。

0offer，自闭了，早知道之前那个就先接了