9.22 拼多多笔试 服务端
比较简单，按照给定规则排序即可。
2. 有n个数字，从中删除两个数字使得数组的平均值不变，输出方案个数。
计算数组的和sum，需要保证sum * 2 % n == 0，从而删除的数字之和为sum * 2 / n，转换成两数之和问题。
3. 给长度为n的数组ai，判断是否可以构建另一个长度为n的数组bi，使得对任意ai，都存在ai = bj - bk，1<=j,k<=n
数学题。结论是数组a中必须要保证两个不同子序列的和相同，之后暴力遍历a中的子序列，求和，并记录在哈希表中判断即可。O(n2^n)
4. 第i时刻汉堡的价格为pi，所购买的汉堡价格可以对应转换为积分，若积分大于等于100，自动转换为一张汉堡券，时限为3天（若第1天获得汉堡券，可以在第2、3、4天使用），求获得所有汉堡需要花费的最小金额。
考虑dp。将券的状态记为j，剩余积分记为k，其中j为历史三天是否获得优惠券（若j=6=0b110，表示i-1、i-2天获得了优惠券），dp[i][j][k]表示第i天后券为j剩余积分为k所需要花费的最小金额。对于每个dp[i-1][j][k]，判断是否有券可以在下一时刻使用（j!=0），并计算下一时刻是否使用券的情况下，后续的状态，从而能够转移到dp[i][new j][new k]。O(800n)
具体而言：
if (j & 1) dp[i][(j-1)>>1][k] = min(dp[i][(j-1)>>1][k], dp[i-1][j][k])
else if (j & 2) dp[i][(j-2)>>1][k] = min(dp[i][(j-2)>>1][k], dp[i-1][j][k])
else if (j & 4) dp[i][(j-4)>>1][k] = min(dp[i][(j-4)>>1][k], dp[i-1][j][k])
dp[i][j>>1|(k+p[i])/100*4][(k+p[i])%100] = min(dp[i][j>>1|(k+p[i])/100*4][(k+p[i])%100], dp[i-1][j][k] + p[i])
#拼多多#
#软件开发2024笔面经#
#软件开发笔面经#
#拼多多笔试#
类似资料：