尧图网站开发 
拿到这套“搜狗2019秋招客户端工程师编程题合集第二场”时我第一反应是这几乎是客户端方向笔试的“标准样本卷”。三道题覆盖了字符串处理、动态规划、二维数组边界控制难度适中不偏不怪但每一道都埋了能让一半候选人翻车的细节。如果你正在准备客户端开发岗Android/iOS/Windows桌面端的秋招笔试这套题非常值得反复刷。它考的不是“会不会背模板”而是“在有限时间内能不能把一道基础题写干净”。下面我挑这三个题型的核心考点、完整思路、参考代码和避坑经验一条条拆开讲。1. 真题结构与考点复盘1.1 这三道题到底在考什么先说整体印象。这套“第二场”的编程题整体难度属于“中等偏低到中等”的分布没有出现复杂的图论、网络流、平衡树这种竞赛型考点反而非常贴近客户端工程师的日常工作场景。三道题的考点非常典型字符串循环移位包含判断核心是字符串处理、子串匹配、边界条件。环形街区偷窃问题核心是动态规划、环形结构的拆解处理。螺旋矩阵打印核心是二维数组遍历、边界指针控制、模拟过程。从考点分布来看这套题没有刻意追求“偏难怪”而是把客户端日常开发中最容易遇到的几类操作抽象成了算法题。字符串解析、列表滑动、界面上的二维控件遍历本质上都是这些基础能力的延伸。所以搜狗出这套题明显是想筛掉“代码写不利索”的候选人而不是想考倒数学天才。1.2 为什么客户端岗偏爱这些题客户端开发和后端有个很大的区别后端经常处理高并发、分布式、海量数据而客户端更多面对的是单机上的用户交互、数据展示、本地存储。这就决定了客户端的算法题通常有几个特点第一题干场景偏“应用层”。比如环形街区偷窃问题本质上是一个资源分配问题和客户端里做缓存淘汰、内存分配有相似之处。螺旋矩阵打印则直接对应图片处理、表格渲染、地图瓦片遍历等场景。第二边界条件考察得特别细。客户端程序跑在用户设备上用户输入千奇百怪一个空数组、一个长度为1的字符串、一个只含一行的矩阵都可能让App闪退。所以笔试里特别爱考这些边界考察候选人有没有“防御式编程”的习惯。第三代码要求可读性。客户端开发通常是多人协作代码要给别人review。笔试虽然只看结果但面试官在复盘时一定会看你写的代码风格。变量命名是否清晰、逻辑是否冗余、有没有写注释这些都会被注意到。1.3 我对这套题的整体评价如果让我打分这套题我会给“中等偏易”四颗星难度主要在“做对”而不在“会做”。三道题的核心算法结论都非常经典基本上一眼就能看出来属于哪个题型。但真正动手写代码时各种细节问题就冒出来了for循环的边界是小于还是小于等于动态规划的初始值该设多少螺旋矩阵打印到最内层会不会重复遍历。我见过不少候选人看到题觉得“我刷过”结果一跑用例就挂在边界上。所以这套题最适合用来做“基本功自测”——如果你能在60分钟内、不查资料、一次通过全部用例那你笔试这关就比较稳了。2. 字符串题循环移位包含判断2.1 题目原型与第一层破题思路先看第一道典型的字符串题题目长这样给定两个字符串s1和s2判断s2是否由s1的循环移位得到。例如s1 AABCDs2 CDAA则s2是s1循环移位后得到的子串返回true。很多同学拿到这题第一反应是模拟移位把s1不断左移或右移每移一位就判断一次是否包含s2。这个思路没错但效率很差时间复杂度是O(n^2)在笔试里遇到较长的字符串容易超时。正确的破题思路是抓住“循环移位”的本质。所谓循环移位就是把字符串末尾的字符搬到开头或者开头搬到末尾相当于在字符串尾部再接一个相同的字符串。例如s1 AABCD循环移位一次变成DAABC两次变成CDAAB三次变成BCDAA四次变成ABCDA。如果你把s1自身拼接一次得到AABCDAABCD你会发现所有这些循环移位后的结果都包含在这个拼接串里。这是一个很漂亮的结论s2可以由s1循环移位得到当且仅当s2是s1s1的子串并且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()同时s1s1里包含s2即可。第三个是关于contains方法的效率。Java的String.contains内部用的是朴素的暴力匹配最坏情况下是O(n*m)。笔试里字符串长度一般不超过几千完全够用。如果面试官追问“能不能更快”你可以回答用KMP算法把匹配复杂度降到O(nm)或者用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 ListInteger spiralOrder(int[][] matrix) { ListInteger 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 三道题常见错误速查表我把这三道题最容易被挂掉的坑整理成一张表方便你写完代码后逐项自查。题目常见错误正确做法循环移位包含忘记判断长度直接拼接s1s1后contains先判断长度相等或长度不大于s1循环移位包含空串边界返回false两个空串应返回true循环移位包含用暴力移位模拟复杂度高用s1s1包含s2的性质O(n)级环形打家劫舍n1时返回0单独处理n1返回nums[0]环形打家劫舍把数组复制两遍跑线性DP拆成两个子区间分别取最大环形打家劫舍滚动变量更新顺序写反prev2先更新再更新prev1螺旋矩阵内外层for循环边界写错用四个边界变量每轮收缩螺旋矩阵单行/单列时重复遍历内层两个for前加topbottom和leftright判断螺旋矩阵没判断matrix[0].length为0判空时同时检查行和列5.2 客户端笔试环境准备与时间分配除了算法本身我还想聊点实用的笔试经验。很多同学代码写得没问题但挂在环境适应上非常可惜。搜狗这类公司的笔试一般走牛客网或赛码网输入输出格式是标准的。如果你是第一次用这些平台建议提前熟悉一下“多组测试用例”的处理方式。很多题目会同时给多组数据需要用while (scanner.hasNext())循环处理而不是只读一次。我记得有不少人就是因为没处理多组输入第一道题一分都没拿到。时间分配上我的建议是“先易后难、先拿基础分”。笔试时长一般120分钟三道题里肯定有一道相对简单。先把能AC的题写完、提交、验证通过再去啃难题。不要在一道题上死磕超过40分钟否则后面两道题只能交白卷。另外一定要培养“写完就自测”的习惯。本地IDE或者平台自带的编辑器里用题目给的示例用例跑一遍再自己构造几个边界用例比如空数组、单元素数组、单行矩阵。实测下来很多明显的bug都能在这一步暴露出来远比提交后才发现要划算。5.3 从笔试到面试的追问准备最后说一下这套编程题不只是笔试完就结束了。面试官在复试环节通常会拿着你写的代码追问所以答题时要多留几个心眼。第一准备好复杂度分析。“你这个解法时间复杂度是多少”“能不能优化空间”这是最常见的追问。循环移位是O(n^2)暴力实现的话要能说出用s1s1可以降到O(n)打家劫舍要能说出空间O(1)的滚动优化螺旋矩阵要能说明为什么时间复杂度是O(m*n)。第二准备好“为什么不用其他方法”。比如打家劫舍为什么拆成两个区间而不是用三维DP因为环形结构首尾约束是全局唯一的枚举首尾状态后剩下的是两个独立的线性子问题拆解后状态数和转移都更简单。能把这个逻辑讲清楚比背答案有用得多。第三准备好手写测试用例。面试官很可能让你“给几个测试用例验证你的代码”。不要只会用题目给的例子要主动构造边界用例空字符串、长度不等的字符串、金额全为0的数组、只有一列的矩阵。这能直接体现你的工程素养而工程素养恰恰是客户端岗位最看重的。我个人在实际操作中的一个体会是这套题的价值不在题目本身而在于它把“写代码的严谨性”摆到了台面上。字符串的长度判断、动态规划的初始条件、二维数组的边界收缩这些细节恰恰是客户端日常开发中最容易出bug的地方。把这三道题刷透比盲目刷两百道新题有用得多。面试官真正想看的不是你见过多少题而是你在压力下能不能把一道基础题写干净、想清楚。这套题就是检验这个能力的最好试金石。 
拿到这套“搜狗2019秋招客户端工程师编程题合集第二场”时我第一反应是这几乎是客户端方向笔试的“标准样本卷”。三道题覆盖了字符串处理、动态规划、二维数组边界控制难度适中不偏不怪但每一道都埋了能让一半候选人翻车的细节。如果你正在准备客户端开发岗Android/iOS/Windows桌面端的秋招笔试这套题非常值得反复刷。它考的不是“会不会背模板”而是“在有限时间内能不能把一道基础题写干净”。下面我挑这三个题型的核心考点、完整思路、参考代码和避坑经验一条条拆开讲。1. 真题结构与考点复盘1.1 这三道题到底在考什么先说整体印象。这套“第二场”的编程题整体难度属于“中等偏低到中等”的分布没有出现复杂的图论、网络流、平衡树这种竞赛型考点反而非常贴近客户端工程师的日常工作场景。三道题的考点非常典型字符串循环移位包含判断核心是字符串处理、子串匹配、边界条件。环形街区偷窃问题核心是动态规划、环形结构的拆解处理。螺旋矩阵打印核心是二维数组遍历、边界指针控制、模拟过程。从考点分布来看这套题没有刻意追求“偏难怪”而是把客户端日常开发中最容易遇到的几类操作抽象成了算法题。字符串解析、列表滑动、界面上的二维控件遍历本质上都是这些基础能力的延伸。所以搜狗出这套题明显是想筛掉“代码写不利索”的候选人而不是想考倒数学天才。1.2 为什么客户端岗偏爱这些题客户端开发和后端有个很大的区别后端经常处理高并发、分布式、海量数据而客户端更多面对的是单机上的用户交互、数据展示、本地存储。这就决定了客户端的算法题通常有几个特点第一题干场景偏“应用层”。比如环形街区偷窃问题本质上是一个资源分配问题和客户端里做缓存淘汰、内存分配有相似之处。螺旋矩阵打印则直接对应图片处理、表格渲染、地图瓦片遍历等场景。第二边界条件考察得特别细。客户端程序跑在用户设备上用户输入千奇百怪一个空数组、一个长度为1的字符串、一个只含一行的矩阵都可能让App闪退。所以笔试里特别爱考这些边界考察候选人有没有“防御式编程”的习惯。第三代码要求可读性。客户端开发通常是多人协作代码要给别人review。笔试虽然只看结果但面试官在复盘时一定会看你写的代码风格。变量命名是否清晰、逻辑是否冗余、有没有写注释这些都会被注意到。1.3 我对这套题的整体评价如果让我打分这套题我会给“中等偏易”四颗星难度主要在“做对”而不在“会做”。三道题的核心算法结论都非常经典基本上一眼就能看出来属于哪个题型。但真正动手写代码时各种细节问题就冒出来了for循环的边界是小于还是小于等于动态规划的初始值该设多少螺旋矩阵打印到最内层会不会重复遍历。我见过不少候选人看到题觉得“我刷过”结果一跑用例就挂在边界上。所以这套题最适合用来做“基本功自测”——如果你能在60分钟内、不查资料、一次通过全部用例那你笔试这关就比较稳了。2. 字符串题循环移位包含判断2.1 题目原型与第一层破题思路先看第一道典型的字符串题题目长这样给定两个字符串s1和s2判断s2是否由s1的循环移位得到。例如s1 AABCDs2 CDAA则s2是s1循环移位后得到的子串返回true。很多同学拿到这题第一反应是模拟移位把s1不断左移或右移每移一位就判断一次是否包含s2。这个思路没错但效率很差时间复杂度是O(n^2)在笔试里遇到较长的字符串容易超时。正确的破题思路是抓住“循环移位”的本质。所谓循环移位就是把字符串末尾的字符搬到开头或者开头搬到末尾相当于在字符串尾部再接一个相同的字符串。例如s1 AABCD循环移位一次变成DAABC两次变成CDAAB三次变成BCDAA四次变成ABCDA。如果你把s1自身拼接一次得到AABCDAABCD你会发现所有这些循环移位后的结果都包含在这个拼接串里。这是一个很漂亮的结论s2可以由s1循环移位得到当且仅当s2是s1s1的子串并且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()同时s1s1里包含s2即可。第三个是关于contains方法的效率。Java的String.contains内部用的是朴素的暴力匹配最坏情况下是O(n*m)。笔试里字符串长度一般不超过几千完全够用。如果面试官追问“能不能更快”你可以回答用KMP算法把匹配复杂度降到O(nm)或者用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 ListInteger spiralOrder(int[][] matrix) { ListInteger 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 三道题常见错误速查表我把这三道题最容易被挂掉的坑整理成一张表方便你写完代码后逐项自查。题目常见错误正确做法循环移位包含忘记判断长度直接拼接s1s1后contains先判断长度相等或长度不大于s1循环移位包含空串边界返回false两个空串应返回true循环移位包含用暴力移位模拟复杂度高用s1s1包含s2的性质O(n)级环形打家劫舍n1时返回0单独处理n1返回nums[0]环形打家劫舍把数组复制两遍跑线性DP拆成两个子区间分别取最大环形打家劫舍滚动变量更新顺序写反prev2先更新再更新prev1螺旋矩阵内外层for循环边界写错用四个边界变量每轮收缩螺旋矩阵单行/单列时重复遍历内层两个for前加topbottom和leftright判断螺旋矩阵没判断matrix[0].length为0判空时同时检查行和列5.2 客户端笔试环境准备与时间分配除了算法本身我还想聊点实用的笔试经验。很多同学代码写得没问题但挂在环境适应上非常可惜。搜狗这类公司的笔试一般走牛客网或赛码网输入输出格式是标准的。如果你是第一次用这些平台建议提前熟悉一下“多组测试用例”的处理方式。很多题目会同时给多组数据需要用while (scanner.hasNext())循环处理而不是只读一次。我记得有不少人就是因为没处理多组输入第一道题一分都没拿到。时间分配上我的建议是“先易后难、先拿基础分”。笔试时长一般120分钟三道题里肯定有一道相对简单。先把能AC的题写完、提交、验证通过再去啃难题。不要在一道题上死磕超过40分钟否则后面两道题只能交白卷。另外一定要培养“写完就自测”的习惯。本地IDE或者平台自带的编辑器里用题目给的示例用例跑一遍再自己构造几个边界用例比如空数组、单元素数组、单行矩阵。实测下来很多明显的bug都能在这一步暴露出来远比提交后才发现要划算。5.3 从笔试到面试的追问准备最后说一下这套编程题不只是笔试完就结束了。面试官在复试环节通常会拿着你写的代码追问所以答题时要多留几个心眼。第一准备好复杂度分析。“你这个解法时间复杂度是多少”“能不能优化空间”这是最常见的追问。循环移位是O(n^2)暴力实现的话要能说出用s1s1可以降到O(n)打家劫舍要能说出空间O(1)的滚动优化螺旋矩阵要能说明为什么时间复杂度是O(m*n)。第二准备好“为什么不用其他方法”。比如打家劫舍为什么拆成两个区间而不是用三维DP因为环形结构首尾约束是全局唯一的枚举首尾状态后剩下的是两个独立的线性子问题拆解后状态数和转移都更简单。能把这个逻辑讲清楚比背答案有用得多。第三准备好手写测试用例。面试官很可能让你“给几个测试用例验证你的代码”。不要只会用题目给的例子要主动构造边界用例空字符串、长度不等的字符串、金额全为0的数组、只有一列的矩阵。这能直接体现你的工程素养而工程素养恰恰是客户端岗位最看重的。我个人在实际操作中的一个体会是这套题的价值不在题目本身而在于它把“写代码的严谨性”摆到了台面上。字符串的长度判断、动态规划的初始条件、二维数组的边界收缩这些细节恰恰是客户端日常开发中最容易出bug的地方。把这三道题刷透比盲目刷两百道新题有用得多。面试官真正想看的不是你见过多少题而是你在压力下能不能把一道基础题写干净、想清楚。这套题就是检验这个能力的最好试金石。