2023-09-11 21:34 北京理工大学 Java
关注
9.11 阿里国际笔试（工程岗）
第一题，电影的最大期待值。如果要每天都更新之前的电影到今天还有多少期待值，然后和今天的电影比，那就太麻烦了，可以把所有电影的期待值都推回到第一天，第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<k。
对于确定的i，可能有C(n-1, i)种不同的选择方案，每个不同的字母对可以有25种选择，相同的字母对只能有一种选择，第一个字母有26种选择，因此每个i的总字符串数量应该有26*25^i*C(n-1, i)种，最终结果是前面这个的和。但是这种解法我没写出来，细节上估计有点问题，不知道有没有大佬过了。
第二题，使数组元素相等的最小次数。遍历所有元素，如果%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<k。
对于确定的i，可能有C(n-1, i)种不同的选择方案，每个不同的字母对可以有25种选择，相同的字母对只能有一种选择，第一个字母有26种选择，因此每个i的总字符串数量应该有26*25^i*C(n-1, i)种，最终结果是前面这个的和。但是这种解法我没写出来，细节上估计有点问题，不知道有没有大佬过了。
全部评论
hywo 楼主
楼主 北京理工大学 Java
第三题那个解法是对的，注意快速幂里面要用long，被这个坑了
相关推荐
曼迪匹艾公司福利 145人发布 
查看28道真题和解析 点赞 评论 收藏
分享