柠檬微趣 Unity 岗笔试：四道算法，从 LC 1003 到双向链表排序

《面试题目》

1. 检查替换后的词是否有效（LeetCode 1003）：给出若干次把 abc 替换成空串的操作，判断最终能否把字符串清空。
2. 下一个更大元素 III（LeetCode 556）：给定一个正整数，找出由它的数字重排能得到的最小且大于它的整数，不存在则返回 -1。
3. 正则表达式匹配（LeetCode 10）：实现支持 . 与 * 的模式匹配。
4. 双向链表排序：用题目给定的头文件，对双向链表做排序。

《参考解析》

第 1 题：LC 1003 的两种写法

这题的题面是「反复把子串 abc 删掉，能否删空」，本质是括号匹配的变体。最直观的是栈：逐个字符入栈，栈顶凑出 abc 就弹出三个，最后栈空即可；因为 abc 只有三个字符，判断时看栈顶两个加当前字符就够，复杂度 O(n)。另一种是字符串模拟：每次 find("abc") 再 erase，写法短，但每次都整体搬移，最坏 O(n²)，数据量大时会超时。笔试里优先写栈版本，写之前先跟面试官说一句思路，卡住时也好往这边靠。

第 2 题：LC 556 是「下一个排列」的应用题

思路分三步：先从右往左找第一个 nums[i] < nums[i+1] 的位置，这说明右侧已经是降序、没有更大的组合了；再从右往左找第一个大于 nums[i] 的数，与它交换；最后把 i 右侧整体反转成升序，得到的就是「比原数大的里面最小的那个」。有两个坑：一是全程要用字符串或长整型，换回 int 会溢出；二是没有找到 i 时返回 -1。这题和第 3 题连在一起出现，说明出题人想看的是「会不会把排列类模板迁移到别的题面」。

第 3 题：LC 10 是这四道里唯一的硬题

二维动态规划，dp[i][j] 表示 s 的前 i 个字符能否被 p 的前 j 个字符匹配。转移分两种情况：p[j-1] 是普通字符或 . 时，直接看 dp[i-1][j-1] 且当前字符相等；p[j-1] 是 * 时，先继承「星号匹配零次」的 dp[i][j-2]，再看「星号再多吃一个字符」的 dp[i-1][j] 且 s[i-1] 与 p[j-2] 相等或 p[j-2] == '.'。边界是 dp[0][0] = true，以及空串对 a*b* 这类模式也要能匹配。写的时候先把状态定义和转移念出来，比闷头写代码更稳——这题面试官通常不只看跑通，还看你能不能讲清为什么这么转移。

第 4 题：双向链表排序的两个层次

能写对的是第一层：把链表节点倒进数组，用 sort 排完再按顺序接回 prev / next，注意头尾指针和原来 head 的处置。要拿高分是第二层：在链表上直接做归并排序——快慢指针找中点、断开、递归排两半、再按 next 归并，归并时同步维护 prev。既然题目给了头文件、又注明是「核心代码模式」，说明它想考的正是链表指针操作本身，而不是调库；写之前先确认头文件里节点结构的字段名与是否有哨兵节点，这是这类题最容易白丢分的地方。

关于这场笔试的形态

四道题里三道是 LeetCode 原题（1003、556、10），第四道是手写数据结构，题量不大但难度分布很开：前两题是熟练度，第三题是动态规划基本功，第四题是指针功底。Unity 客户端岗出这种组合，说明笔试筛的是通用算法能力而不是引擎知识——准备时按 LeetCode 中等题过一遍字符串、栈、DP、链表四类，比专门去背 Unity API 更对路。