腾讯音乐笔试复盘：四道算法题考点与代码详解

腾讯音乐娱乐TME2023暑期实习的技术类笔试我参加的是II卷也就是下午场。整体流程和大部分大厂差不多牛客网在线笔试2小时4道编程题自选语言ACM模式自己处理输入输出。说实话这套卷子的难度分布比上午场I卷要明显一些前两题属于热身和基础巩固后两题直接上强度特别是第三题和第四题很大程度上决定了你能不能被捞去面试。这篇不聊别的就把这四道题从题目到思路再到完整代码全部复盘一遍顺便把笔试里容易踩的坑拉出来单独说给后面准备TME或者其他大厂暑期实习的同学做一个参考。1. 笔试基本信息与整体难度判断1.1 笔试模式和流程先交代一下环境。TME这套笔试是在牛客网平台上完成的题型是纯编程题没有选择题、问答题。进入笔试之后会先看到考试须知然后是答题页面左侧是题目列表右侧是代码编辑器编辑器里已经给出了函数框架或者main函数的读入骨架你需要选一门语言把代码补全点运行之后自己准备测试数据。需要注意不管是牛客还是赛码这类笔试基本都是ACM模式。意思是输入输出全都要自己处理用cin、scanf或者input()自己读用cout、printf自己输出。这和LeetCode那种只需要补函数核心代码的模式不一样很多同学第一次上机就栽在这上面函数写对了但输入输出格式不对或者多输出了一个空格照样判错。语言方面我建议能用C就用C。原因很简单TME的题量虽然不大但第二题、第三题对时间复杂度的要求比较严格Python写起来方便遇到大数据量容易TLE而C的标准库在堆、栈、vector这些数据结构上效率更稳。当然如果你平时主要用Java或者Go也不是不行关键是你要对常用数据结构的API足够熟不能现场查文档。1.2 四道题的难度排布这套卷子的四道题我用一个表来概括题号考点方向难度预估用时是否送分第一题字符串重排、贪心、堆低15分钟是第二题单调栈、子数组贡献计算中25分钟是但容易错第三题树形DP、树上距离统计高40分钟否第四题多重背包、二进制优化中高30分钟否看到这个排序你就明白了出题人不太会按花活但很会按梯度。前两题是在筛“基本功是否熟练”后两题是在筛“算法思维能不能上线”。特别是第三题很多人连树的存储都写得费劲别说再做树形DP了。第四题表面上是背包但如果不掌握二进制拆分直接用三层循环暴力数据一大基本就卡死。1.3 为什么说前两题不能丢分第一题和第二题是整张卷子的核心分。如果这两题都AC了第四题哪怕只过一半用例总排名也不会太难看。但如果第一题第二题里有任何一个卡住后面心态很容易崩第三题第四题就别想静下心写。我在考场上的策略是先把四道题全部扫一遍判断每道题属于哪个模板然后优先保前两题第三题写出主思路第四题能写多少写多少。下面我把每道题的完整复盘写出来。2. 四道编程题的解法复盘2.1 第一题字符串重排保证相邻字符不同题目大概意思输入一个只包含小写字母的字符串s长度在1到2e5之间。要求把字符串重新排列使得任意两个相邻位置的字符不一样。如果存在这样的重排方案输出任意一个如果不存在输出-1。这道题其实就是LeetCode 767的变体考察的是贪心优先队列。解决思路分两步。第一步判断是否有解。统计每个字符出现的次数找到最大出现次数maxCnt。因为要让同一个字符不相邻它必须被其他字符隔开所以最极限的情况是maxCnt (n 1) / 2其中n是字符串长度。比如aaamaxCnt 3(31)/2 23大于2无解。aaba出现2次(31)/2 2有解输出aba。第二步构造方案。最稳妥的做法是用一个最大堆每次取出出现次数最多的两个字符拼到结果字符串末尾然后把它们的次数减一再放回堆里。为什么每次取两个而不是一个因为只取一个的话可能出现连续两次拿到同一个字符的情况取两个可以保证相邻位置一定不同。如果最后堆里还剩一个字符且它的剩余次数是1可以拼在末尾如果剩余次数大于1说明无解。我提交的参考代码#include bits/stdc.h using namespace std; int main() { string s; cin s; int cnt[26] {0}; for (char c : s) cnt[c - a]; priority_queuepairint, char pq; for (int i 0; i 26; i) { if (cnt[i] 0) pq.push({cnt[i], char(a i)}); } string res ; pairint, char pre {0, #}; while (!pq.empty()) { auto cur pq.top(); pq.pop(); res cur.second; cur.first--; if (pre.first 0) pq.push(pre); pre cur; } if ((int)res.size() ! (int)s.size() || res.size() 1 res[res.size() - 1] res[res.size() - 2]) { cout -1 \n; } else { cout res \n; } return 0; }这里的核心细节是把上一次用过的字符pre先暂存等这次取出的字符用完再把它放回堆里避免同一个字符连续出现。代码最后加了一个校验原因是如果堆里某个字符剩余次数太多最终结果长度不会等于原始长度直接判定无解。这道题的时间复杂度是O(n log 26)也就是O(n)空间复杂度O(26)。放第一题的位置完全合理它考察的是你对基础数据结构和边界条件的熟练程度不存在思维难度只看你写得够不够快。2.2 第二题所有连续子数组的最小值之和题目大概意思给定一个长度为n的整数数组an最大1e5a[i]的范围在1到1e9。求所有连续子数组的最小值之和结果对1e97取模。说白了数组里每个元素都可能成为某个子数组的最小值你要把所有这些“最小值”加起来。如果把所有子数组暴力枚举出来总数是n(n1)/2n1e5的时候根本算不完。所以要用到单调栈的经典套路每个子数组的最小值只归属于这个子数组里“最靠左的那个最小值”通过这个归属关系把每个元素的贡献独立计算出来。具体来说对每个位置i我们需要找到left[i]左边第一个比a[i]小的位置如果不存在就是-1right[i]右边第一个小于等于a[i]的位置如果不存在就是n。为什么左边用“小于”右边用“小于等于”因为如果左右都用“小于”遇到相等元素时同一个子数组会被两个相等的最小值各算一次造成重复左右一个开一个闭就能让相等元素只归属其中一方保证不重不漏。拿到left[i]和right[i]之后以a[i]为最小值的子数组数量等于(i - left[i]) * (right[i] - i)它对答案的贡献就是a[i] * 这个数量。参考代码#include bits/stdc.h using namespace std; const int MOD 1e9 7; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint left(n), right(n); stackint st; for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) st.pop(); left[i] st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i n - 1; i 0; --i) { while (!st.empty() a[st.top()] a[i]) st.pop(); right[i] st.empty() ? n : st.top(); st.push(i); } long long ans 0; for (int i 0; i n; i) { long long cnt (long long)(i - left[i]) * (right[i] - i) % MOD; ans (ans (long long)a[i] * cnt) % MOD; } cout ans \n; return 0; }第一次写这道题的时候我非常容易在单调栈的比较符号上翻车。左边用弹出右边用弹出这个设计不是拍脑袋来的就是为了处理重复元素。记住一句话左闭右开或左开右闭总之不要让相等的元素既在左边作为严格小、又在右边作为严格小出现。对称性在这里非常关键。2.3 第三题树上距离等于k的点对数量题目大概意思给一棵n个节点的无根树n最大1e5k最大100。求树上任意两个点之间距离恰好等于k的无序点对数量。第一反应可能是Floyd或者DFS全源但n是1e5完全不现实。这道题标准做法是树形DP。思路是这样的对每个节点u统计以u为根时u的子树中到u距离为d的节点个数记为dp[u][d]。然后当我们处理到某个节点u需要把它的每一个孩子v的子树依次合并进u里。在合并某一个孩子v之前dp[u]里已经保存了u本身和之前已经处理过的所有孩子子树的信息。此时从u的旧子树里取一个点从v的新子树里取一个点这两个点在树上的最短路径一定经过u路径长度就等于两个点到u的距离之和。有了这个思路代码其实不难写。关键在于组合的细节v子树里的点如果到v的距离是j那么到u的距离是j1。所以对于旧子树里一个到u距离为i的点和新子树里一个到v距离为j的点它们的距离是i j 1。只要这个值等于k就把两边的方案数相乘累加到答案里。#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint g[MAXN]; int n, k; long long ans; int dp[MAXN][105]; void dfs(int u, int fa) { dp[u][0] 1; for (int v : g[u]) { if (v fa) continue; dfs(v, u