腾讯校招2016编程题解析：格雷码、摩尔投票与动态规划

1. 从2016年的这套题说起：它到底在筛什么人

很多准备腾讯校招的同学会先去翻历年题库，翻到2016年研发工程师编程题时，经常是一脸懵：题目不难，但一看就知道暴力解会被卡，而且每道题背后都有一个非常典型的算法原型。这套题放在当年，其实是腾讯用来做大规模筛选的笔试题，语言不限，Java、C++、C都行，时间大概一到两小时，题量在四道左右。和现在动辄系统设计、并发编程、海量数据的笔试题相比，这套题显得相当“基本功”，但它筛人的逻辑恰恰是：在有限时间内，能不能快速识别题型，并写出没有边界bug的代码。

这套题里的“微信红包”“格雷码”“年终奖”“构造回文”等题目，后来几乎成了各大厂题库里的常客。哪怕放到现在，拿来当校招准备材料也不过时。我当年做这套题的时候，最大的感受是：它不考偏门算法，不考复杂的图论，它考的是“常见算法的原型你是否真的吃透了”。比如你要知道超过一半的数可以用摩尔投票，而不是只会HashMap；你要知道构造回文等于求最长回文子序列，而不是真的去DFS枚举删除哪几个字符。

所以这篇文章适合三类人：准备腾讯或者其他大厂校招的应届生，准备社招但想补算法基本功的后端开发，以及纯粹想把常见题型整理成体系的人。我会按题型把2016年这套题里比较有代表性的题目拆开讲，包括解题思路、代码实现、复杂度分析，以及我当时踩过的坑。

先给这套题做个速览，方便你对整张卷子有个整体感：

下面我们一道题一道题过，我不会只说“这题用XX法”，我会解释为什么能想到这个方法，以及在笔试现场怎么快速判断题型。

2. 数学思维题：格雷码的镜面反射与素数对的枚举边界

2.1 生成格雷码：不只是背公式，要懂它为什么成立

题目描述非常直接：在一组数的编码中，任意两个相邻的代码只有一位二进制数不同，这种编码称为格雷码。给定一个整数n，要求返回n位格雷码对应的编码序列，一般要求输出字符串数组或者整数数组。

我第一次看到这题，第一反应是回溯：逐位构造，每次改变一位，然后检查是否满足相邻只差一位。理论上能写出来，但实现非常容易乱，而且递归深度一大，代码自己都看不懂。实际上这题有更漂亮的解法，而且不止一种。

第一个方案是镜面反射法，也是最符合直觉的方法。假设我们已经有了n-1位格雷码，序列长度是2^(n-1)。要生成n位格雷码，只要把n-1位序列的正序前面加“0”，再把n-1位序列的逆序前面加“1”，拼起来就是完整序列。举例来说，1位格雷码是["0", "1"]，2位格雷码就是["00", "01"]拼上["11", "10"]，得到["00", "01", "11", "10"]。为什么这样拼接能保证相邻只差一位？因为正序部分内部相邻差1位，逆序部分内部相邻差1位，而正序最后一位和逆序第一位是同一个n-1位数值，只是前缀从0变成1，所以也只差1位。这个构造的精髓在于“对称翻转”。

第二个方案是一行公式：第i个格雷码等于 i ^ (i >> 1)。这个公式非常简洁，笔试现场用这个最快，而且不会写错。但面试官如果追问“为什么”，你需要能解释：把二进制数i右移一位再和自己异或，本质上是把每个二进制位的翻转信号错开了一位，使得相邻的i在生成的格雷码中只有一位发生变化。具体来说，从i到i+1，i的低位会有一串连续的1变成0，再往上的一个0变成1，异或右移操作恰好把这串变化压缩成一次翻转。

我给的代码兼顾可读性和正确性，用公式法实现：

public String[] getGray(int n) { int size = 1 << n; String[] res = new String[size]; for (int i = 0; i < size; i++) { int g = i ^ (i >> 1); StringBuilder sb = new StringBuilder(); for (int j = n - 1; j >= 0; j--) { sb.append((g >> j) & 1); } res[i] = sb.toString(); } return res; }

这里有两个细节容易踩坑。

第一个是n的边界。如果n等于0，有些题目的输入约定是n>=1，但万一遇到n=0，你返回的应该是["0"]而不是空数组。这个最好在写代码前先确认题目描述，或者直接在最前面加一个if判断。

第二个细节是转二进制字符串时，位数的补零。如果你直接用Integer.toBinaryString(g)，得到的字符串长度可能不足n位，会漏掉前导零，导致测试用例过不去。上面代码用了一个从高位到低位的循环手动拼接，就是为了保证长度恒为n。

如果面试官要求你给出“递归版”而不是公式版，用上面的镜面反射法写一个递归函数也不难：

public List<String> grayCode(int n) { List<String> res = new ArrayList<>(); if (n == 0) { res.add("0"); return res; } List<String> prev = grayCode(n - 1); int half = prev.size(); // 先放正序补0 for (int i = 0; i < half; i++) { res.add("0" + prev.get(i)); } // 再放逆序补1 for (int i = half - 1; i >= 0; i--) { res.add("1" + prev.get(i)); } return res; }

注意这个地方有一个非常隐蔽的坑：如果你在同一个循环里既给前半段补0，又给后半段补1，而且你是先修改了prev里的字符串再逆序引用，那后半段就会拿到补过0的字符串，导致答案全错。正确做法是把补0和补1分成两次循环，或者先复制逆序。上面的代码就是先正序补0，再逆序补1，顺序安全。

2.2 素数对：筛法一次到位，不要现场写朴素判断

题目大概是这样的：给定一个偶数n，问有多少对素数a、b满足a + b = n，并且a <= b。例如n = 10时，答案是2，因为3 + 7和5 + 5都是符合要求的素数对。

这题看起来简单，但很多人会在这里翻车，原因在于没有预估n的范围。如果n最大到十万甚至百万，而你每次判断一个数是不是素数都写一个O(sqrt(n))的循环，整体复杂度是O(n * sqrt(n))，在笔试平台上是很容易超时的。

正确思路是先预处理出一张素数表，再做枚举。具体分两步：第一步用埃氏筛把2到n之间的所有素数标记出来；第二步从a=2枚举到a=n/2，如果a是素数且n-a也是素数，计数加一。

public int countPrimePairs(int n) { boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } int cnt = 0; for (int a = 2; a <= n / 2; a++) { if (isPrime[a] && isPrime[n - a]) { cnt++; } } return cnt; }

枚举上界写成n/2是刻意的。因为a <= b的条件等价于a <= n/2，这样不会把2 + 8和8 + 2当成两对，也不会漏掉a == b的情况，比如n = 4时4/2=2，只枚举到2，isPrime[2] && isPrime[2]成立，计数为1。

这题还有一个容易被忽略的边界：n的最小取值。如果n是2，那2不是偶数且不满足条件，题目一般会保证n是大于等于4的偶数，但你还是可以写一个防御性的判断：if (n < 4) return 0。

3. 线性扫描的典型题：摩尔投票与最大差值

3.1 微信红包：超过一半的数不是求众数，是找候选人

这道题在当年的笔试题里非常经典，后来也在很多公司的题库里反复出现。题目描述是：春节期间小明收到很多微信红包，他发现有一个金额出现的次数超过了红包总数的一半，请找出这个金额，如果不存在则返回0。

如果你没有见过这个题，第一时间想到的解法通常是HashMap计数：遍历一遍数组，统计每个数出现次数，再找次数超过一半的那个。这个解法在功能上完全正确，时间复杂度O(n)，但空间复杂度也是O(n)，而且这道题的考察意图显然不是这个。你注意一下题目的限制，通常会要求空间复杂度O(1)。这就需要用到摩尔投票法。

摩尔投票的核心思想可以理解成“候选人对抗”：你维护一个候选人candidate和一个计数器count。遍历数组时，如果count为0，就把当前元素设为候选人，count设为1；如果当前元素等于候选人，count加1；否则count减1。整个过程的直观解释是：把数组中的元素看成投票，超过一半的多数派一定能抵消掉所有少数派之后还剩票数，所以最终留下的candidate一定是唯一可能的多数派。

但这里有个大坑：摩尔投票的结果只是“候选人”，不是最终答案。比如数组[1, 2, 3]，按算法走下来，最后candidate是3，count是1，但3的出现次数并没有超过一半。所以拿到候选人后，必须再遍历一遍数组，统计候选人真实出现次数，确认是否真的超过一半。这个第二遍验证非常容易被忽略，一旦忽略，隐藏用例直接挂。

public int getValue(int[] gifts) { if (gifts == null || gifts.length == 0) return 0; int candidate = 0; int count = 0; for (int x : gifts) { if (count == 0) { candidate = x; count = 1; } else if (candidate == x) { count++; } else { count--; } } int total = 0; for (int x : gifts) { if (x == candidate) total++; } return total * 2 > gifts.length ? candidate : 0; }

注意最后这里的判断，我写的是total * 2 > gifts.length，不是total > gifts.length / 2。原因是整数除法会向下取整，如果数组长度是5，出现次数是2，2 > 5/2 即 2 > 2 不成立，看起来没问题；但如果数组长度是4，出现次数是2，2 > 4/2 即 2 > 2 也不成立，答案应该是不存在，正确。可万一出现次数是3，3 > 4/2 即 3 > 2 成立，正确。看起来整除也没毛病，但为了避免所有可能的边界疑虑，乘2再比较是最稳妥的写法，而且不会产生浮点数。

我当时第一次写这个题，就是因为漏了第二遍验证，自信满满提交，结果挂了三个用例。后来才意识到，摩尔投票只能保证“如果有超过一半的数，它一定是候选人”，不能保证“候选人一定超过一半”。这两句话差着一个验证步骤，笔试时千万别省。

3.2 最大差值：维护前缀最小值，而不是排序

最大差值这道题的题面大概是：给定一个数组A，求满足i < j的A[j] - A[i]的最大值，如果不存在这样的差值返回0。这个题在LeetCode上对应的是“买卖股票的最佳时机”，只不过股票题里是“后一天减前一天的最大利润”，这里换成了数组下标顺序约束。

我看到很多人第一反应是：找最大值和最小值，然后相减。但这样做是错的，因为最大值可能在最小值前面，比如数组[5, 1, 3]，最大值是5，最小值是1，5 - 1 = 4，但满足i < j的最大差值其实是3 - 1 = 2。所以这个题不能排序，也不能简单取全局最大最小。

正确思路是线性扫描，同时维护“当前已经遍历过的位置中最小的值”。每遍历到一个位置j，就尝试用A[j]减去当前的最小值，更新答案。因为最小值一定出现在j之前，所以天然满足i < j的约束。

public int maxDiff(int[] A) { if (A == null || A.length < 2) return 0; int min = A[0]; int ans = Integer.MIN_VALUE; for (int j = 1; j < A.length; j++) { ans = Math.max(ans, A[j] - min); min = Math.min(min, A[j]); } return Math.max(ans, 0); }

需要注意两点：一是如果题目允许差值可以为负（也就是可以不交易），那我们需要在最后判断一下ans是否为正；如果题目明确规定“没有满足条件的差值就返回0”，那就用Math.max(ans, 0)包一下。二是答案初始值应该是Integer.MIN_VALUE而不是0，否则数组[1, 2, 3]能跑通，但数组[3, 2, 1]这种全是下降的场景，如果初始值是0，答案会被错误地赋成0而不是-1之类，导致无法区分“差值为0”和“没有交易”。虽然多数笔试题的最后返回值不是负数，但这个初始值习惯要养好。

这道题属于“看着像动态规划，其实连数组都不用开”的最小DP形态。本质上dp[j]表示以j结尾的最大差值，但转移只用到了dp[j-1]状态里的最小前缀值，所以一个变量就够了。在笔试现场，这种优化一定要敏锐地做到。

4. 二维DP的两种典型形态：网格DP与区间DP

4.1 年终奖：6x6网格上的二维DP与边界初始化

这道题的描述很生活化：小东所在公司每年发年终奖，老板给了一个6x6的方格，每个格子里放了一个价值不同的礼物。小东从左上角出发，每次只能向右或者向下走，走到右下角，问最多能拿到多少价值的礼物。

这是一个非常标准的二维网格DP。定义dp[i][j]表示从左上角走到(i, j)位置能获得的最大价值。因为只能向右和向下走，所以(i, j)只能从(i-1, j)或者(i, j-1)到达，状态转移就是取这两个来源的较大值，再加上当前格子的价值：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j]

关键是边界处理。第一行只能从左边走过来，第一列只能从上边走过来，所以需要先单独初始化第一行和第一列，否则dp[i-1][j]或dp[i][j-1]会访问到未初始化的0，结果虽然碰巧对，但逻辑上是错的。

public int getMost(int[][] board) { int m = board.length; int n = board[0].length; int[][] dp = new int[m][n]; dp[0][0] = board[0][0]; for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + board[0][j]; } for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + board[i][0]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + board[i][j]; } } return dp[m - 1][n - 1]; }

如果题目允许你修改原数组，也可以直接在board上原地更新，这样额外空间复杂度降为O(1)。但原地修改有一个隐患：如果你后面还要用board的原始值，就会被覆盖掉。笔试题里一般不要求保留原数组，所以原地版本也完全可以，不过面试官可能会问“你改原数组面试官给你的输入了怎么办”，这时候你要能说清楚“因为题目只要求返回最大值，原数组后续不再使用，所以这种做法是安全的”。

还有一种变体是问能不能用一维数组压缩空间。这个题的转移只依赖上一行的同一列和当前行的前一列，所以确实可以用一个长度为n的数组滚动更新：

public int getMost(int[][] board) { int m = board.length; int n = board[0].length; int[] dp = new int[n]; dp[0] = board[0][0]; for (int j = 1; j < n; j++) { dp[j] = dp[j - 1] + board[0][j]; } for (int i = 1; i < m; i++) { dp[0] += board[i][0]; for (int j = 1; j < n; j++) { dp[j] = Math.max(dp[j], dp[j - 1]) + board[i][j]; } } return dp[n - 1]; }

笔试中如果没有任何空间限制，不必为了炫技强行空间压缩，因为压缩之后思维负担更大，容易写错。但面试时能主动提出来，是加分项。

这道题在当年属于“送分题”，但每年还是有一批人因为边界条件写错而卡住。我自己的习惯是，写网格DP之前先画一个2x2的示意图，把第一行第一列的值标出来，确认清楚再动手。花三十秒画图，能省三分钟调试。

4.2 构造回文：删除最少字符，绕不开最长回文子序列

题目：给定一个字符串s，你可以删除其中的任意字符，使剩下的字符串成为一个回文串，求最少需要删除多少个字符。

这题如果直接思考“删除哪些字符”，很容易陷入穷举DFS，指数级复杂度完全不可行。需要做一个很重要的等价转换：删除最少的字符使剩余字符串成为回文，等价于在原字符串中找到一个最长的回文子序列，把它保留下来，其余的全删掉。所以答案就是：

s.length() - 最长回文子序列长度

最长回文子序列这个问题，用区间DP解。定义dp[i][j]表示字符串s从下标i到下标j这个子串的最长回文子序列长度。当s[i] == s[j]时，说明两端可以同时计入回文，dp[i][j] = dp[i+1][j-1] + 2；当s[i] != s[j]时，说明两端不可能同时出现在同一个回文子序列里，只能在去掉左端或去掉右端里取更大值，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

public int minDelete(String s) { int n = s.length(); int[][] dp = new int[n][n]; // i从大到小遍历 for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return n - dp[0][n - 1]; }

dp[i][j]依赖dp[i+1][j-1]和dp[i+1][j]、dp[i][j-1]，这些区间长度都比dp[i][j]短，所以理论上按区间长度从小到大遍历最安全。不过上面的代码用i从大到小、j从小到大，也能保证计算dp[i][j]时，依赖的状态已经算好了，这也是常见的写法。但这里有一个容易出问题的边界：当j = i + 1且s[i] == s[j]时，dp[i+1][j-1]就是dp[i+1][i]，这是一个“左端点大于右端点”的空区间。因为二维数组int默认值是0，所以直接取值结果是0，dp[i][j] = 2，正确。如果你用别的语言比如C++，二维数组初始化不一定是0，要特别注意这一点。

这道题还有一个非常有意思的姊妹变体：给定一个字符串，最少插入多少字符可以把它变成回文。答案是同一个公式：n - 最长回文子序列长度。为什么？因为插入字符和删除字符在本质上是互补的。你需要删除k个字符得到回文串，等价于向这个回文串中原来的字符之间插入k个对应字符，把多出来的字符“补成对称”。所以这两道题可以一起记忆，考试时看到“插入”或“删除”，直接映射到同一个DP。

还有一个常见的错误是把这题和“最长回文子串”混淆。最长回文子串要求连续，最长回文子序列不要求连续。构造回文的删除操作保留下的字符不要求连续，所以一定是子序列问题，不是子串问题。

5. 贪心与排序：纸牌游戏为什么敢直接排序

5.1 纸牌游戏：每次取最大就是最优，但要会证明

题目大意是：有一堆牌，每张牌上有一个数字，牛牛和羊羊轮流取牌，牛牛先手，每次取走当前牌堆中数字最大的牌，最后谁手上的数字之和大谁赢。求最终牛牛的总分减去羊羊的总分。

这题如果第一次见，你可能会觉得既然双方都聪明，是不是需要用博弈搜索？实际上完全不需要。因为题目里已经明确规则：“每次取剩下的牌中数字最大的那张”。这不是一个策略选择，而是强制规则，所以双方的行动路径是确定性的。你要做的只是把数组排序，然后牛牛拿第0、2、4……张（从大到小排序后的偶数下标），羊羊拿第1、3、5……张，最后累加差值即可。

public long getScoreGap(int[] cards) { Arrays.sort(cards); long diff = 0; int n = cards.length; for (int i = n - 1; i >= 0; i--) { if ((n - 1 - i) % 2 == 0) { diff += cards[i]; } else { diff -= cards[i]; } } return diff; }

这里有一个看起来很简单但容易翻车的点：结果要用long，不要用int。如果牌数很多，每张牌的数字很大，两个人的总分差完全可能超过int范围。笔试中很多题会用大样例卡int溢出，这是老套路了。

还有一个容易混淆的变体：如果题目改成“两个人轮流从牌堆两端取牌”，那贪心就不成立了，因为每次从两端取哪一端会影响后续可选的牌，这时候必须用区间DP。所以做题时一定要看清楚题目说的是“取最大的牌”还是“从两端任取一张”。前者排序，后者区间DP，完全两个难度。

这一题其实是整套2016年题目里最简单的，但我还是想多提一句：面试官问你“为什么排序后轮流取就是正确的”，你能把理由说出来吗？理由很简单，因为规则已经固定了“每次取最大”，那么实际上就是按照牌面大小的全局顺序依次分配，先手拿到第1大、第3大、第5大……后手拿到第2大、第4大、第6大……这不依赖于任何人的决策，所以没有博弈空间。

5.2 字符移位：一个“稳定分组”问题，别用普通partition

题意：给一个只包含大小写字母的字符串，把所有大写字母移动到字符串末尾，小写字母在前，且大小写字母各自的相对顺序不能改变。比如输入"aAbBcC"，输出"abcABC"。有的版本还要求不能使用额外空间。

如果你第一时间想用快排的partition思路，双指针从两端找大写和小写然后交换，这个做法在“只要求大小写分组”时看似可行，但会破坏相对顺序。举一个例子：字符串"ABc"。双指针partition后可能变成"cAB"，小写c跑到最前面，但如果我们期望的是保持原顺序，原顺序是A、B、c，移动后应该是"cAB"已经对了？换个例子"bAaB"，双指针做不稳定交换，结果可能是"baAB"或者别的，会导致小写字母之间的顺序变化。这道题的核心诉求是稳定分组，而不是简单分组。

所以最稳的写法是允许额外空间时，两遍扫描收集：

public String moveUppercase(String s) { StringBuilder lower = new StringBuilder(); StringBuilder upper = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLowerCase(c)) { lower.append(c); } else { upper.append(c); } } return lower.append(upper).toString(); }

这个写法清晰、不会出错，笔试首选。但题目如果明确要求“不能使用额外空间”，就需要用插入排序式的方法：从左往右扫描，维护一个“小写区末尾”的指针pos，初始为0。每当遇到一个小写字母，就把从pos到当前下标之间的字符整体右移一位，再把这个小写字母放到pos位置，pos加1。这个操作是稳定的，时间复杂度最坏O(n^2)，空间O(1)。

public void moveUppercase(char[] arr) { int pos = 0; for (int i = 0; i < arr.length; i++) { if (Character.isLowerCase(arr[i])) { char c = arr[i]; for (int j = i; j > pos; j--) { arr[j] = arr[j - 1]; } arr[pos] = c; pos++; } } }

为什么这个“整体右移”做法不会破坏相对顺序？因为它相当于标准的稳定插入：每个小写字母被插入到已排好的小写区末尾，其他元素保持原有先后关系。而普通快排交换属于不稳定操作，交换一次就可能让原本在后面的小写字母跑到前面去。这个区别，面试官非常喜欢追问。

6. 杂题与笔试环境的坑：有趣的数字和三个实战建议

6.1 有趣的数字：排序之后要分情况讨论，别一根筋扫相邻差

“有趣的数字”这道题在2016年腾讯研发工程师编程题里算比较复杂的一道。题目描述：给定n个整数，两两组成二元组，差最小的有多少对？差最大的有多少对？要求输出两个数。

思路是先排序，因为排序之后差最大的对一定是“最小值 × 最大值”的组合。假设排序后第一个数出现minCnt次，最后一个数出现maxCnt次，那么差最大的对数就是minCnt * maxCnt。这个结论很简单，但要注意如果所有数字都一样，比如[2, 2, 2]，最大值和最小值相同，此时任意两对都是差最大也是差最小，答案是C(3, 2) = 3对，而不是minCnt * maxCnt = 9。所以要先判断maxDiff是否为0，直接返回总对数。

差最小的情况更繁琐。如果数组里有重复数字，最小差就是0，对数是所有重复数字中选择两个的组合数之和。比如[1, 1, 1, 2, 3]里，三个1之间任取两个都能组成差为0的一对，所以有C(3, 2) = 3对。如果数组里没有重复数字，最小差就是排序后相邻元素差的最小值，对数等于相邻差等于这个最小值的相邻对数量。

完整代码可以这样写：

public int[] getPairCounts(int[] nums) { Arrays.sort(nums); int n = nums.length; int maxDiff = nums[n - 1] - nums[0]; long maxCnt; if (maxDiff == 0) { long allPairs = (long) n * (n - 1) / 2; return new int[]{(int) allPairs, (int) allPairs}; } int minCnt = 0; int maxValCnt = 0; for (int x : nums) { if (x == nums[0]) minCnt++; if (x == nums[n - 1]) maxValCnt++; } maxCnt = (long) minCnt * maxValCnt; int minDiff = Integer.MAX_VALUE; for (int i = 1; i < n; i++) { minDiff = Math.min(minDiff, nums[i] - nums[i - 1]); } long minCntPairs = 0; if (minDiff == 0)