腾讯 一面（C/C++ 算法题为主）

《面试题目》

1. 问一下个人信息
2. 做三道算法题（要求 C/C++）： （1）区间合并（力扣原题） （2）镜像二叉树判断（力扣原题） （3）一道 DP：有 n 个位置和 m 种花朵，可以任选一些位置种植花朵，但相邻位置上如果有花朵，品种不能一样，求一共有多少种方案
3. 询问技术栈

《参考解析》

区间合并：先按起点排序，然后遍历并维护当前区间 [l, r]：如果下一个区间的左端点小于等于 r（或 < r+1，取决于是否合并相邻端点），就更新 r = max(r, next_r)；否则把当前区间收进结果、开始新区间。复杂度 O(n log n) 由排序决定。边界要处理：空数组、单区间、完全包含（next_r < r）、以及 touching（端点相接是否合并要按题意）。用 C++ 写时注意排序的比较函数要严格弱序，避免相等时返回 true 造成未定义行为。

镜像二叉树判断：递归比较两棵子树是否互为镜像——isMirror(a, b)：两者都空返回 true；一个空一个非空返回 false；值不等返回 false；否则递归比较 isMirror(a->left, b->right) && isMirror(a->right, b->left)。入口调用 isMirror(root, root)。迭代写法用队列 / 栈成对入队，注意入队顺序也要镜像（左对右）。区分「对称」与「相同」是常见陷阱：相同是比较 a->left 与 b->left，镜像才是交叉比较。

种花计数 DP：这是「相邻位置不能同色」的涂色计数问题，设 dp[i] 为前 i 个位置且第 i 个位置种花的方案数，dp0[i] 为第 i 个位置不种花的方案数。转移：dp0[i] = dp[i-1] + dp0[i-1]（不种花不受任何限制）；dp[i] = (dp0[i-1] + dp[i-1] * (m - 1))——如果前一个位置没花，当前可以种 m 种；如果前一个位置有花，当前只能种剩下 m-1 种。答案是 dp[n] + dp0[n]。这个状态设计比「按位置枚举颜色」更省，复杂度 O(n)、空间可压到 O(1)。面试时要主动说明状态定义与转移依据，并验证小样本（n=1 时答案应为 m+1；n=2 时答案应为不种方案 1 + 只种一朵 2m + 两朵 m(m-1)）。

这一轮的准备建议：腾讯的这道组合更偏向「算法基本功 + 编码规范」，题目本身是力扣原题加一道不算难的 DP，写的速度与边界处理是主要差距点。练习时建议用 C++ 在纸上或纯文本编辑器里写（不加 IDE 补全），并把每题的边界用例先在注释里列出来再动手——面试官看的是过程。