搜狗客户端秋招笔试题解析：字符串、动态规划与螺旋矩阵实战

拿到这套“搜狗2019秋招客户端工程师编程题合集（第二场）”时，我第一反应是：这几乎是客户端方向笔试的“标准样本卷”。三道题覆盖了字符串处理、动态规划、二维数组边界控制，难度适中，不偏不怪，但每一道都埋了能让一半候选人翻车的细节。

如果你正在准备客户端开发岗（Android/iOS/Windows桌面端）的秋招笔试，这套题非常值得反复刷。它考的不是“会不会背模板”，而是“在有限时间内能不能把一道基础题写干净”。下面我挑这三个题型的核心考点、完整思路、参考代码和避坑经验，一条条拆开讲。

1. 真题结构与考点复盘

1.1 这三道题到底在考什么

先说整体印象。这套“第二场”的编程题，整体难度属于“中等偏低到中等”的分布，没有出现复杂的图论、网络流、平衡树这种竞赛型考点，反而非常贴近客户端工程师的日常工作场景。

三道题的考点非常典型：

• 字符串循环移位包含判断：核心是字符串处理、子串匹配、边界条件。
• 环形街区偷窃问题：核心是动态规划、环形结构的拆解处理。
• 螺旋矩阵打印：核心是二维数组遍历、边界指针控制、模拟过程。

从考点分布来看，这套题没有刻意追求“偏难怪”，而是把客户端日常开发中最容易遇到的几类操作抽象成了算法题。字符串解析、列表滑动、界面上的二维控件遍历，本质上都是这些基础能力的延伸。所以搜狗出这套题，明显是想筛掉“代码写不利索”的候选人，而不是想考倒数学天才。

1.2 为什么客户端岗偏爱这些题

客户端开发和后端有个很大的区别：后端经常处理高并发、分布式、海量数据，而客户端更多面对的是单机上的用户交互、数据展示、本地存储。这就决定了客户端的算法题通常有几个特点：

第一，题干场景偏“应用层”。比如环形街区偷窃问题，本质上是一个资源分配问题，和客户端里做缓存淘汰、内存分配有相似之处。螺旋矩阵打印，则直接对应图片处理、表格渲染、地图瓦片遍历等场景。

第二，边界条件考察得特别细。客户端程序跑在用户设备上，用户输入千奇百怪，一个空数组、一个长度为1的字符串、一个只含一行的矩阵，都可能让App闪退。所以笔试里特别爱考这些边界，考察候选人有没有“防御式编程”的习惯。

第三，代码要求可读性。客户端开发通常是多人协作，代码要给别人review。笔试虽然只看结果，但面试官在复盘时一定会看你写的代码风格。变量命名是否清晰、逻辑是否冗余、有没有写注释，这些都会被注意到。

1.3 我对这套题的整体评价

如果让我打分，这套题我会给“中等偏易”四颗星，难度主要在“做对”而不在“会做”。三道题的核心算法结论都非常经典，基本上一眼就能看出来属于哪个题型。但真正动手写代码时，各种细节问题就冒出来了：for循环的边界是小于还是小于等于，动态规划的初始值该设多少，螺旋矩阵打印到最内层会不会重复遍历。

我见过不少候选人，看到题觉得“我刷过”，结果一跑用例就挂在边界上。所以这套题最适合用来做“基本功自测”——如果你能在60分钟内、不查资料、一次通过全部用例，那你笔试这关就比较稳了。

2. 字符串题：循环移位包含判断

2.1 题目原型与第一层破题思路

先看第一道典型的字符串题，题目长这样：

给定两个字符串s1和s2，判断s2是否由s1的循环移位得到。例如s1 = "AABCD"，s2 = "CDAA"，则s2是s1循环移位后得到的子串，返回true。

很多同学拿到这题，第一反应是模拟移位：把s1不断左移或右移，每移一位就判断一次是否包含s2。这个思路没错，但效率很差，时间复杂度是O(n^2)，在笔试里遇到较长的字符串容易超时。

正确的破题思路是抓住“循环移位”的本质。所谓循环移位，就是把字符串末尾的字符搬到开头，或者开头搬到末尾，相当于在字符串尾部再接一个相同的字符串。例如s1 = "AABCD"，循环移位一次变成"DAABC"，两次变成"CDAAB"，三次变成"BCDAA"，四次变成"ABCDA"。如果你把s1自身拼接一次得到"AABCDAABCD"，你会发现，所有这些循环移位后的结果，都包含在这个拼接串里。

这是一个很漂亮的结论：s2可以由s1循环移位得到，当且仅当s2是s1+s1的子串，并且s2的长度不能超过s1。实际题目里如果严格要求“循环移位得到整个字符串”，则要求两者长度相等；如果只要求“循环移位后包含s2”，则只需要长度不大于s1。

2.2 参考代码与边界处理

基于上面的结论，核心代码可以写得很短。我用Java实现一版：

public boolean isRotatedString(String s1, String s2) { if (s1 == null || s2 == null) { return false; } if (s1.length() != s2.length()) { return false; } if (s1.length() == 0 && s2.length() == 0) { return true; } String doubled = s1 + s1; return doubled.contains(s2); }

这里有几个细节必须注意。

第一个是空判断。如果s1和s2都是空串，按道理空串经过任意次循环移位还是空串，所以应该返回true。如果不加这个判断，直接走doubled.contains(s2)，由于空串是任意字符串的子串，也会返回true，所以更严谨的做法是显式处理。

第二个是长度判断。如果题目要求“s2是s1循环移位后得到的完整字符串”，那长度必须相等。如果不限制长度，只是问“s2是否出现在s1的某个循环移位中”，那判断条件就变成s2.length() <= s1.length()，同时s1+s1里包含s2即可。

第三个是关于contains方法的效率。Java的String.contains内部用的是朴素的暴力匹配，最坏情况下是O(n*m)。笔试里字符串长度一般不超过几千，完全够用。如果面试官追问“能不能更快”，你可以回答用KMP算法把匹配复杂度降到O(n+m)，或者用Boyer-Moore。但实际笔试中，没有必要为了炫技去手写KMP，除非题目明确要求。

2.3 这道题的扩展问法

这道题在面试环节经常被扩展，常见的有两种：

第一种：如果s2只是s1循环移位后的子串，不要求完整字符串，怎么改？代码几乎不用变，只需要把长度判断改成s2.length() <= s1.length()。这个变体更贴近实际业务里的“环形缓冲区查找”。

第二种：如果两个字符串长度都很大，比如超过10万，朴素匹配会超时。此时要手写KMP。KMP的核心是计算next数组，在匹配失败时跳转到已匹配的前缀位置，避免重复比较。这个属于进阶考点，建议准备客户端岗的同学还是写一遍KMP，毕竟面试官一旦追问，能当场写出来是非常加分的。

另外，这道题还有一个容易踩的坑：字符集。如果字符串里包含中文字符或Unicode字符，Java的String.length()返回的是UTF-16编码下的代码单元数量，不是“字符个数”。在绝大多数笔试场景下，输入都是纯ASCII字符，这个问题可以忽略。但如果题目明确说“包含任意Unicode字符”，建议用codePointCount来统计字符数，避免代理对导致的长度误判。

3. 动态规划题：环形街区偷窃问题

3.1 环形结构怎么拆解

第二道题是动态规划，题目原型是“打家劫舍”的环形版本：你是一个专业小偷，沿街有一排环形排列的房子，每间房里藏着一定金额的现金。唯一限制是相邻的房子不能同时被偷，否则会触发报警。给定每间房子的金额数组，求今晚能偷到的最大金额。

线性版本大家都很熟：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。但环形版本多了一个约束：第一间房子和最后一间房子相邻，不能同时偷。

很多同学第一次看到环形就慌了，想着用状态压缩或复杂的分类讨论。其实环形问题的通用解法非常简单：枚举“第一家偷不偷”，把一个环拆成两个线性问题。

具体来说，分两种情况：

• 不偷第一家，那么第二家到最后一家可以自由决策，问题退化为对nums[1]到nums[n-1]的线性“打家劫舍”。
• 不偷最后一家，那么第一家到倒数第二家可以自由决策，问题退化为对nums[0]到nums[n-2]的线性“打家劫舍”。

取这两种情况的最大值，就是答案。

为什么这样拆是对的？因为环形带来的额外约束只有“首尾相邻”这一条。只要保证“第一家不偷”和“最后一家不偷”两种方案都被覆盖到，就不存在漏解的情况。这种“枚举特殊情况，消除环形影响”的思路，在算法题里非常通用，比如环形数组最大子序和也是用同样的套路。

3.2 状态转移与代码实现

线性“打家劫舍”的状态转移方程，我用滚动变量的方式实现，省空间：

public int rob(int[] nums) { int n = nums.length; if (nums == null || n == 0) { return 0; } if (n == 1) { return nums[0]; } return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1)); } private int robRange(int[] nums, int start, int end) { int prev2 = 0; int prev1 = 0; for (int i = start; i <= end; i++) { int cur = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = cur; } return prev1; }

这段代码里，prev2代表dp[i-2]，prev1代表dp[i-1]，每次迭代计算当前最优值cur，然后滚动更新。空间复杂度从O(n)降到了O(1)，在笔试里是加分项。

这里特别说一下n == 1的边界处理。当数组只有一个元素时，robRange(nums, 0, n - 2)会变成robRange(nums, 0, -1)，循环一次都不会执行，返回0；而robRange(nums, 1, n - 1)也会因为1 > 0而返回0，最终结果错误地变成0。所以必须在一开始就单独处理n == 1的情况。这是这道题最容易翻车的地方，没有之一。

3.3 动态规划的易错点与我的调试心得

除了n == 1，我在实际写题时还遇到过几个问题，这里一起说。

第一是“把环复制两遍”的误区。有些同学想当然地认为，环形问题可以把数组复制一份变成2n长度，然后跑线性DP。这样做的问题在于，同一个房子会在数组里出现两次，动态规划可能同时选择这两个重复项，导致“同一个房子被偷两次”。虽然在某些特殊场景下答案可能碰巧正确，但逻辑上是不严谨的，笔试时容易被面试官追问到哑口无言。所以老老实实用“拆环”的解法最稳妥。

第二是负数金额的处理。标准“打家劫舍”假定金额是非负的，因为状态转移里prev2 + nums[i]不会因为负数而变得更糟。但如果题目允许负数金额，比如“房子可能负债”，那dp[i] = max(dp[i-1], dp[i-2] + nums[i])在处理负数时就会出问题，因为可能“不偷任何一个房子”才是最优解。遇到这种情况，需要把初始值改成负数，或者明确说明“必须偷至少一间”。不过搜狗这套题里没有这个陷阱，正常做即可。

第三是滚动变量更新顺序。prev2 = prev1; prev1 = cur;这两行顺序不能反。如果先更新prev1再更新prev2，那prev2拿到的就是已经更新过的prev1，后面的计算就全错了。这种低级错误在笔试紧张时很容易犯，建议写完后用[2, 3, 2]这种小用例手推一遍：正确答案是3（偷2），如果代码算出来是4，那一定是滚动更新顺序错了。

4. 模拟题：螺旋矩阵打印

4.1 边界控制是翻车率最高的点

第三道题是二维数组操作，题目原型是“螺旋矩阵”：给定一个m行n列的矩阵，按顺时针螺旋顺序返回矩阵中的所有元素。例如：

1 2 3 4 5 6 7 8 9

输出应该是[1, 2, 3, 6, 9, 8, 7, 4, 5]。

这道题不涉及高深的算法，纯粹考察“模拟过程”和“边界控制”。但恰恰是这种模拟题，实际通过率往往不高。原因很简单：四个方向循环遍历时，边界更新的顺序很容易搞混，尤其到了最内层，容易重复遍历或漏遍历。

我用一个生活化的类比来理解：螺旋打印就像拿抹布擦一个矩形桌面，你贴着墙边一圈一圈往中间擦。每擦完一条边，就把对应的那堵“墙”往里推一点。四个方向的墙就是上下左右四个边界。当左墙越过右墙、上墙越过下墙时，说明桌面擦完了。

有了这个模型，代码就很好写了。维护四个变量：top、bottom、left、right，分别代表当前未遍历区域的上、下、左、右边界。然后按照“从左到右、从上到下、从右到左、从下到上”的顺序循环，每遍历完一条边就收缩对应的边界。

4.2 参考代码与调试经验

Java实现如下：

public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return result; } int top = 0; int bottom = matrix.length - 1; int left = 0; int right = matrix[0].length - 1; while (top <= bottom && left <= right) { for (int j = left; j <= right; j++) { result.add(matrix[top][j]); } top++; for (int i = top; i <= bottom; i++) { result.add(matrix[i][right]); } right--; if (top <= bottom) { for (int j = right; j >= left; j--) { result.add(matrix[bottom][j]); } bottom--; } if (left <= right) { for (int i = bottom; i >= top; i--) { result.add(matrix[i][left]); } left++; } } return result; }

这段代码里有几个关键细节值得单独拿出来说。

第一个是每轮循环结束后的边界收缩。top++、right--、bottom--、left++四个操作顺序对应遍历方向，不能乱。否则下一轮循环的起点就错了。

第二个是内层两个for循环前要加判断。当矩阵只有一行时，top++之后top > bottom，此时不应该再从右往左遍历；当矩阵只有一列时，right--之后left > right，此时也不应该再从下往上遍历。这两个判断就是防止重复遍历。

第三个是初始判空条件。matrix.length == 0和matrix[0].length == 0都要判断，因为二维数组可能是空行，也可能是空列。有些同学只判断matrix == null，结果在取matrix[0].length时直接空指针。

调试这道题有一个很实用的方法：找一张纸，手写一个3x3和一个4x3的矩阵，然后用笔模拟代码的遍历过程，每走一步就更新边界。我当年备考时把这个过程重复了至少五遍，后来遇到任何螺旋遍历的变体题都能秒杀。如果你嫌手推麻烦，也可以在当地IDE里打日志，在每次进入while循环时打印top、bottom、left、right四个值，很快就能定位越界问题。

4.3 输入输出陷阱与扩展思考

这道题的输入输出有几个容易踩的坑，我单独列一下。

第一，如果矩阵元素是字符串或对象，而不是整数，代码逻辑不变，但要注意ArrayList的泛型类型。笔试里通常是整数矩阵，但也要留意题目的具体说明。

第二，如果矩阵非常大，比如10000x10000，结果列表会占用大量内存。虽然题目一般不会给这么大的数据，但思路要清楚：螺旋遍历的时间复杂度是O(m*n)，这是无法避免的，因为你必须访问每个元素至少一次。

第三，有些变体题会要求“从外到内”转成“从内到外”，或者改成逆时针。处理方式类似，只需要调整遍历方向和边界收缩顺序。我建议把标准螺旋矩阵的代码背熟，遇到变体时在这个框架上微调即可。

5. 高频易错点与笔试提效技巧

5.1 三道题常见错误速查表

我把这三道题最容易被挂掉的坑整理成一张表，方便你写完代码后逐项自查。

5.2 客户端笔试环境准备与时间分配

除了算法本身，我还想聊点实用的笔试经验。很多同学代码写得没问题，但挂在环境适应上，非常可惜。

搜狗这类公司的笔试一般走牛客网或赛码网，输入输出格式是标准的。如果你是第一次用这些平台，建议提前熟悉一下“多组测试用例”的处理方式。很多题目会同时给多组数据，需要用while (scanner.hasNext())循环处理，而不是只读一次。我记得有不少人就是因为没处理多组输入，第一道题一分都没拿到。

时间分配上，我的建议是“先易后难、先拿基础分”。笔试时长一般120分钟，三道题里肯定有一道相对简单。先把能AC的题写完、提交、验证通过，再去啃难题。不要在一道题上死磕超过40分钟，否则后面两道题只能交白卷。

另外，一定要培养“写完就自测”的习惯。本地IDE或者平台自带的编辑器里，用题目给的示例用例跑一遍，再自己构造几个边界用例，比如空数组、单元素数组、单行矩阵。实测下来，很多明显的bug都能在这一步暴露出来，远比提交后才发现要划算。

5.3 从笔试到面试的追问准备

最后说一下，这套编程题不只是笔试完就结束了。面试官在复试环节通常会拿着你写的代码追问，所以答题时要多留几个心眼。

第一，准备好复杂度分析。“你这个解法时间复杂度是多少？”“能不能优化空间？”这是最常见的追问。循环移位是O(n^2)暴力实现的话，要能说出用s1+s1可以降到O(n)；打家劫舍要能说出空间O(1)的滚动优化；螺旋矩阵要能说明为什么时间复杂度是O(m*n)。

第二，准备好“为什么不用其他方法”。比如打家劫舍，为什么拆成两个区间而不是用三维DP？因为环形结构首尾约束是全局唯一的，枚举首尾状态后，剩下的是两个独立的线性子问题，拆解后状态数和转移都更简单。能把这个逻辑讲清楚，比背答案有用得多。

第三，准备好手写测试用例。面试官很可能让你“给几个测试用例验证你的代码”。不要只会用题目给的例子，要主动构造边界用例：空字符串、长度不等的字符串、金额全为0的数组、只有一列的矩阵。这能直接体现你的工程素养，而工程素养恰恰是客户端岗位最看重的。

我个人在实际操作中的一个体会是：这套题的价值不在题目本身，而在于它把“写代码的严谨性”摆到了台面上。字符串的长度判断、动态规划的初始条件、二维数组的边界收缩，这些细节恰恰是客户端日常开发中最容易出bug的地方。把这三道题刷透，比盲目刷两百道新题有用得多。面试官真正想看的不是你见过多少题，而是你在压力下能不能把一道基础题写干净、想清楚。这套题，就是检验这个能力的最好试金石。