1. 从2016年的这套题说起它到底在筛什么人很多准备腾讯校招的同学会先去翻历年题库翻到2016年研发工程师编程题时经常是一脸懵题目不难但一看就知道暴力解会被卡而且每道题背后都有一个非常典型的算法原型。这套题放在当年其实是腾讯用来做大规模筛选的笔试题语言不限Java、C、C都行时间大概一到两小时题量在四道左右。和现在动辄系统设计、并发编程、海量数据的笔试题相比这套题显得相当“基本功”但它筛人的逻辑恰恰是在有限时间内能不能快速识别题型并写出没有边界bug的代码。这套题里的“微信红包”“格雷码”“年终奖”“构造回文”等题目后来几乎成了各大厂题库里的常客。哪怕放到现在拿来当校招准备材料也不过时。我当年做这套题的时候最大的感受是它不考偏门算法不考复杂的图论它考的是“常见算法的原型你是否真的吃透了”。比如你要知道超过一半的数可以用摩尔投票而不是只会HashMap你要知道构造回文等于求最长回文子序列而不是真的去DFS枚举删除哪几个字符。所以这篇文章适合三类人准备腾讯或者其他大厂校招的应届生准备社招但想补算法基本功的后端开发以及纯粹想把常见题型整理成体系的人。我会按题型把2016年这套题里比较有代表性的题目拆开讲包括解题思路、代码实现、复杂度分析以及我当时踩过的坑。先给这套题做个速览方便你对整张卷子有个整体感题目类型代表题核心考察点难度数学构造格雷码递归/位运算边界处理中等数论素数对筛法 枚举避免重复计数简单偏中等线性扫描微信红包摩尔投票法空间O(1)中等线性扫描最大差值前缀最小值思想简单二维DP年终奖网格DP边界初始化简单偏中等区间DP构造回文最长回文子序列中等贪心排序纸牌游戏排序后按奇偶累加简单字符串处理字符移位稳定性处理中等统计细节有趣的数字排序 组合数 分类讨论中等偏难下面我们一道题一道题过我不会只说“这题用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到i1i的低位会有一串连续的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有些题目的输入约定是n1但万一遇到n0你返回的应该是[0]而不是空数组。这个最好在写代码前先确认题目描述或者直接在最前面加一个if判断。第二个细节是转二进制字符串时位数的补零。如果你直接用Integer.toBinaryString(g)得到的字符串长度可能不足n位会漏掉前导零导致测试用例过不去。上面代码用了一个从高位到低位的循环手动拼接就是为了保证长度恒为n。如果面试官要求你给出“递归版”而不是公式版用上面的镜面反射法写一个递归函数也不难public ListString grayCode(int n) { ListString res new ArrayList(); if (n 0) { res.add(0); return res; } ListString 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之间的所有素数标记出来第二步从a2枚举到an/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/22只枚举到2isPrime[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是3count是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出现次数是22 5/2 即 2 2 不成立看起来没问题但如果数组长度是4出现次数是22 4/2 即 2 2 也不成立答案应该是不存在正确。可万一出现次数是33 4/2 即 3 2 成立正确。看起来整除也没毛病但为了避免所有可能的边界疑虑乘2再比较是最稳妥的写法而且不会产生浮点数。我当时第一次写这个题就是因为漏了第二遍验证自信满满提交结果挂了三个用例。后来才意识到摩尔投票只能保证“如果有超过一半的数它一定是候选人”不能保证“候选人一定超过一半”。这两句话差着一个验证步骤笔试时千万别省。3.2 最大差值维护前缀最小值而不是排序最大差值这道题的题面大概是给定一个数组A求满足i j的A[j] - A[i]的最大值如果不存在这样的差值返回0。这个题在LeetCode上对应的是“买卖股票的最佳时机”只不过股票题里是“后一天减前一天的最大利润”这里换成了数组下标顺序约束。我看到很多人第一反应是找最大值和最小值然后相减。但这样做是错的因为最大值可能在最小值前面比如数组[5, 1, 3]最大值是5最小值是15 - 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与区间DP4.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[i1][j-1] 2当s[i] ! s[j]时说明两端不可能同时出现在同一个回文子序列里只能在去掉左端或去掉右端里取更大值dp[i][j] max(dp[i1][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[i1][j-1]和dp[i1][j]、dp[i][j-1]这些区间长度都比dp[i][j]短所以理论上按区间长度从小到大遍历最安全。不过上面的代码用i从大到小、j从小到大也能保证计算dp[i][j]时依赖的状态已经算好了这也是常见的写法。但这里有一个容易出问题的边界当j i 1且s[i] s[j]时dp[i1][j-1]就是dp[i1][i]这是一个“左端点大于右端点”的空区间。因为二维数组int默认值是0所以直接取值结果是0dp[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)