字符串与矩阵高频 - 面试题

#

★★★

1. 三数之和中排序+双指针的去重细节为何是高频扣分点？

问题

求解三数之和，说明排序+双指针的去重细节，以及为何去重是高频扣分点？

考察点

排序 + 固定一个数 + 双指针
跳过重复元素（外层与内层）防重复结果
去重时机与边界

答案

排序后固定第一个数 i，用双指针 l=i+1、r=n-1 找两数和为 -nums[i]。去重细节：① 外层 i 去重：若 nums[i]==nums[i-1] 则跳过（避免同一首元素重复枚举，因为排序后相同值相邻）；② 内层去重：当找到一组解后，l 向右跳过与 nums[l] 相同的值，r 向左跳过与 nums[r] 相同的值，避免同一尾对重复。去重是"高频扣分点"是因为：只去重 l/r 而不去重 i，或去重时机在更新前而非更新后，都会产生重复三元组；且 i 去重必须用 i-1 而非 i+1（否则会漏掉可行解）。正确写法：i 去重用 if(i>0 && nums[i]==nums[i-1]) continue；找到解后 while(l<r && nums[l]==nums[l+1]) l++; while(l<r && nums[r]==nums[r-1]) r--; 再 l++, r--。

解析

去重本质是"排序后的相邻跳过"，保证每个值组合只枚举一次。i 去重用 i-1 是防止漏解（若用 i+1 会把 i 与 i+1 相同但 i 是必要首元的情况也跳过）。内层去重发生在"找到解之后"，否则去重会破坏解。这些细节决定输出是否含重复三元组，故常被面试官深挖。

示例代码

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 外层去重
        int l = i + 1, r = nums.length - 1, target = -nums[i];
        while (l < r) {
            int s = nums[l] + nums[r];
            if (s == target) {
                res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                while (l < r && nums[l] == nums[l + 1]) l++; // 内层去重
                while (l < r && nums[r] == nums[r - 1]) r--;
                l++; r--;
            } else if (s < target) l++;
            else r--;
        }
    }
    return res;
}

#

★★★

2. 最长回文子串中中心扩展、动态规划与 Manacher 的复杂度与实现成本对比？

问题

对比最长回文子串的中心扩展、动态规划与 Manacher 三种方法的复杂度与实现成本？

考察点

中心扩展 O(n²) 时间、O(1) 空间
DP O(n²) 时间、O(n²) 空间
Manacher O(n) 时间、O(n) 空间、实现复杂

答案

中心扩展：以每个字符及每两个字符间为回文中心，向两侧扩展，枚举所有中心（2n−1 个）各扩展 O(n)，总 O(n²)，空间 O(1)；实现简单。动态规划：dp[i][j] 表示 s[i..j] 是否回文，转移 dp[i][j]=dp[i+1][j-1] && s[i]==s[j]，按长度递增填表，O(n²) 时间、O(n²) 空间；实现中等。Manacher：用对称扩展把每个中心的最长回文半径摊到 O(n)，总 O(n) 时间、O(n) 空间；实现最复杂（需处理 # 插入、对称取 min、更新最右边界）。对比：n 小时三者皆可（中心扩展最简）；n 大且需 O(n) 时用 Manacher；DP 适合需要所有回文子串信息的衍生题。

解析

三种方法体现"从简单到最优"的递进：中心扩展靠枚举所有中心，DP 靠区间递推，Manacher 靠"回文对称性"复用已算半径。Manacher 的难点是"以最右边界为中心，对称位置取 min 初始化当前半径"，这是 O(n) 的关键。实现成本与性能呈反比，选型看数据规模。

示例代码

// 中心扩展
String longestPalindrome(String s) {
    int start = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int len : new int[]{expand(s, i, i), expand(s, i, i + 1)}) {
            if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; }
        }
    }
    return s.substring(start, start + maxLen);
}
int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

#

★★★

3. 字符串转整数（atoi）的完整边界清单中空白、符号、溢出、非法字符？

问题

实现 atoi 字符串转整数，列出空白、符号、溢出、非法字符的完整边界清单？

考察点

前导空白处理
正负号处理
溢出判断（用加法前判断）

答案

边界清单：① 前导空白：跳过开头的空格（+ 制表符等）；② 符号：可选 '+' 或 '-'，只允许一个且在数字前；③ 数字解析：只取连续数字，遇到第一个非数字字符即停止（忽略后续）；④ 溢出：累加前判断 result > (Integer.MAX_VALUE - digit)/10 则溢出，需按符号截断到 MAX/MIN；⑤ 无有效数字：返回 0；⑥ 空串/全空白：返回 0。溢出处理最常见：在 result*10+digit 前用 (MAX−digit)/10 判断，防止乘法溢出。负数范围：MIN_VALUE 的绝对值比 MAX 大 1，需特殊处理。

解析

atoi 是边界处理的经典题，考察对"输入不可控"的健壮性。核心难点是溢出判断——必须在乘法前用除法预判，避免自身溢出。符号仅影响最终符号与溢出截断方向。非法字符停止解析是标准行为（非报错）。

示例代码

int myAtoi(String s) {
    int i = 0, n = s.length(), sign = 1, res = 0;
    while (i < n && s.charAt(i) == ' ') i++;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) { sign = s.charAt(i) == '-' ? -1 : 1; i++; }
    while (i < n && Character.isDigit(s.charAt(i))) {
        int d = s.charAt(i) - '0';
        if (res > (Integer.MAX_VALUE - d) / 10) // 溢出判断
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        res = res * 10 + d; i++;
    }
    return res * sign;
}

#

★★★

4. 最长公共子序列（LCS）与最长公共子串中 DP 转移差异与空间优化（滚动数组）？

问题

求解最长公共子序列与最长公共子串，说明 DP 转移差异与滚动数组空间优化？

考察点

LCS 允许不连续 vs 子串连续
状态定义与转移差异
滚动数组把空间从 O(n²) 降到 O(n)

答案

LCS（不连续）：dp[i][j] 表示 A[0..i-1] 与 B[0..j-1] 的 LCS 长度。转移：若 A[i-1]==B[j-1] 则 dp[i][j]=dp[i-1][j-1]+1；否则 dp[i][j]=max(dp[i-1][j], dp[i][j-1])。最长公共子串（连续）：dp[i][j] 表示以 A[i-1]、B[j-1] 结尾的最长公共子串长度。转移：若相等则 dp[i][j]=dp[i-1][j-1]+1，否则 dp[i][j]=0（不连续就断开）；答案取所有 dp 的最大值。转移差异：LCS 不相等时取 max 延续，子串不相等时清零。空间优化：每行 dp 只依赖上一行，故用滚动数组（两行或一维倒序）把空间从 O(n²) 降到 O(n)。注意子串求最长时需在 dp 过程中维护全局 max。

解析

核心差异是"连续性"：LCS 的 max 允许跳过不匹配的字符，子串的 0 表示一旦不连续就重新开始。这决定了两者转移方程的形态。滚动数组利用"只依赖上一行"的局部性，是二维 DP 空间优化的通用手段。

示例代码

// LCS 用滚动数组（两行）
int longestCommonSubsequence(String a, String b) {
    int m = a.length(), n = b.length();
    int[] prev = new int[n + 1], cur = new int[n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) cur[j] = prev[j - 1] + 1;
            else cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        int[] t = prev; prev = cur; cur = t; Arrays.fill(cur, 0);
    }
    return prev[n];
}

#

★★★

5. 正则表达式匹配（LeetCode 10）中星号匹配前字符的 DP 状态如何定义，为什么需要特殊处理星号匹配零次？

问题

实现正则表达式匹配（. 与 *），说明 DP 状态定义，以及为何需要特殊处理星号匹配零次？

考察点

dp[i][j] 表示 s 前 i 与 p 前 j 是否匹配
星号匹配前字符零次/一次/多次
匹配零次分支的必要性

答案

dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。边界 dp[0][0]=true。转移：若 p[j-1]=='.' 或 ==s[i-1]，则 dp[i][j]=dp[i-1][j-1]；若 p[j-1]==''，则分两种情况：① 匹配零次：dp[i][j]=dp[i][j-2]（跳过字符和星号）；② 匹配一次或多次：若 p[j-2]=='.' 或 ==s[i-1]，则 dp[i][j]=dp[i][j] || dp[i-1][j]（星号匹配 s 的当前字符，继续用星号匹配更多）。为什么必须处理匹配零次：星号可以表示"前字符出现 0 次"，即该字符可有可无，若只考虑匹配一次/多次，遇到 p 中"a" 与 s 中无 a 的情况会误判不匹配。匹配零次分支是星号语义"可省略"的体现。

解析

星号是重点：它前字符可重复 0 次（跳过）、1 次多次（匹配并继续）。dp[i][j-2] 对应"零次"，dp[i-1][j] 对应"匹配当前字符后继续用星号"。正确性依赖这两种分支的完备性。这是区间/字符串 DP 的经典题。

示例代码

boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int j = 2; j <= n; j++) if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[i][j] = dp[i][j - 2]; // 匹配零次
            if (j >= 2 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)))
                dp[i][j] |= dp[i - 1][j]; // 匹配一次及以上
        } else if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))
            dp[i][j] = dp[i - 1][j - 1];
    }
    return dp[m][n];
}

#

★★★

6. 矩阵遍历中螺旋矩阵、矩阵旋转、岛屿数量（DFS/BFS）的实现要点？

问题

说明螺旋矩阵、矩阵旋转、岛屿数量的实现要点？

考察点

螺旋矩阵的边界收缩
矩阵原地旋转（转置+翻转）
岛屿数量 DFS/BFS 洪泛

答案

螺旋矩阵：维护 top/bottom/left/right 四个边界，按"右→下→左→上"循环，每次走完一条边收缩对应边界，注意处理单行/单列避免重复访问。矩阵旋转 90°：原地转置（swap a[i][j] 与 a[j][i]）+ 每行反转（顺时针）或列反转（逆时针），O(n²) 时间、O(1) 空间。岛屿数量：DFS/BFS 洪泛——遍历每个格子，若为 '1' 且未访问，则岛屿数+1 并连同其所有相邻 '1' 标记（DFS 递归或 BFS 队列），把整个连通块标记为已访问（原地改 '0' 或用 visited）。要点：方向数组（上下左右）、边界检查、避免重复访问。

解析

三者都是"矩阵遍历"范式。螺旋矩阵用边界收缩，旋转用转置+翻转的数学变换，岛屿数量用洪泛连通分量。共同点是方向数组与边界检查。原地旋转的"转置+翻转"是空间 O(1) 的关键技巧。

示例代码

// 岛屿数量 DFS
int numIslands(char[][] g) {
    int cnt = 0;
    for (int i = 0; i < g.length; i++) for (int j = 0; j < g[0].length; j++)
        if (g[i][j] == '1') { cnt++; dfs(g, i, j); }
    return cnt;
}
void dfs(char[][] g, int i, int j) {
    if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] != '1') return;
    g[i][j] = '0'; // 原地标记
    dfs(g, i + 1, j); dfs(g, i - 1, j); dfs(g, i, j + 1); dfs(g, i, j - 1);
}

#

★★★

7. 字符串 DP 的高频模型中编辑距离、最长公共子序列、最长回文子序列的转移？

问题

总结编辑距离、最长公共子序列、最长回文子序列三类字符串 DP 的状态定义与转移？

考察点

编辑距离的插入/删除/替换转移
LCS 的 max 转移
最长回文子序列的区间转移

答案

编辑距离：dp[i][j]=把 A[0..i-1] 变成 B[0..j-1] 的最少操作。若 A[i-1]==B[j-1] 则 dp[i][j]=dp[i-1][j-1]；否则 dp[i][j]=1+min(替换 dp[i-1][j-1], 删除 dp[i-1][j], 插入 dp[i][j-1])。LCS：dp[i][j]=A[0..i-1] 与 B[0..j-1] 的 LCS 长度。相等则 dp[i-1][j-1]+1，否则 max(dp[i-1][j], dp[i][j-1])。最长回文子序列：dp[i][j]=s[i..j] 的最长回文子序列长度。若 s[i]==s[j] 则 dp[i][j]=dp[i+1][j-1]+2，否则 max(dp[i+1][j], dp[i][j-1])。三者均按"末端字符是否相等"分情况，编辑距离多一个"三操作取 min"，区间 DP（回文子序列）按长度递增填表。

解析

三类 DP 的共同框架是"根据末端字符关系决定转移"，编辑距离核心是三种操作代价取 min，LCS 是取 max，回文子序列是区间两端向内收缩。这些是面试字符串 DP 的"母题"，掌握它们可迁移到子序列/子串的众多变体。

示例代码

// 编辑距离
int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
        else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
    }
    return dp[m][n];
}

#

★★★

8. 矩阵类问题的通用解法中 DFS 洪泛、BFS 层序与原地修改（空间 O(1)）的技巧？

问题

总结矩阵类问题的通用解法：DFS 洪泛、BFS 层序与原地修改的空间 O(1) 技巧？

考察点

DFS 洪泛连通分量
BFS 层序求最短步数
原地修改（用特殊值标记）省 visited 空间

答案

DFS 洪泛：用于连通分量类（岛屿数量、被围绕区域），递归访问相邻格子标记。BFS 层序：用于求最短步数/层数（腐烂橘子、最短路径），用队列按层处理，记录层数。原地修改技巧：用特殊值（如 '0'、'#'、负数）原地标记已访问，避免 O(n²) 的 visited 数组；但要保证标记值不会与后续判断冲突，且能恢复（如生命游戏用位编码）。空间 O(1) 的通用法则是"用状态本身存额外信息"，如把感染的格子改成 2、把访问过的改成 0。DFS 深度在网格大时可能栈溢出，可改用 BFS 或显式栈。

解析

矩阵问题三件套：洪泛（DFS/BFS）、层序（BFS 记层、多源）、原地标记（省空间）。原地标记的关键是"标记不破坏后续遍历的正确性"，常用"改成不会再用到的值"或"位编码同时存当前与下一状态"。DFS 栈深是网格类问题的隐患，需评估递归深度。

示例代码

// BFS 层序（腐烂橘子式）：每层代表一分钟
int bfs(int[][] grid) {
    Deque<int[]> q = new ArrayDeque<>();
    int minutes = 0;
    // 初始所有腐烂入队；每层处理一圈，minutes++
    while (!q.isEmpty()) {
        int size = q.size();
        for (int k = 0; k < size; k++) { /* 处理一层 */ }
        minutes++;
    }
    return minutes;
}

#

★★★

9. 整数反转（LeetCode 7）中逐位取余拼接时如何用“溢出前判断”避免结果溢出，负数如何处理？

问题

实现整数反转，说明逐位取余拼接时如何用溢出前判断避免溢出，以及负数如何处理？

考察点

逐位取余、分离、拼接
溢出前判断（乘法前预判）
负数在 Java 中取余的天然处理

答案

逐位反转：while(x!=0){ int d=x%10; x/=10; res=res10+d; }。溢出判断：拼接前检查 res>Integer.MAX_VALUE/10 或（res==MAX/10 且 d>MAX%10），同样对负数检查 MIN，否则丢弃 res 返回 0。负数处理：Java 的 % 对负数保留符号，如 x=-123，d=-3，-12%10=-2，拼出的 res=-321，天然正确，无需特判正负。只需在溢出判断时统一用绝对值比较或用积的符号判断。关键：必须在 res10+d 之前预判溢出，因为乘法本身可能溢出。

解析

核心是"溢出前判断"：不能先乘再判断，而要先用 MAX/10 与 MAX%10 预判。负数因 Java 取余保留负号而自动正确，是语言特性带来的简化。溢出返回 0 是题目明确要求。

示例代码

int reverse(int x) {
    int res = 0;
    while (x != 0) {
        int d = x % 10;
        x /= 10;
        if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && d > 7)) return 0;
        if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && d < -8)) return 0;
        res = res * 10 + d;
    }
    return res;
}

#

★★

10. 螺旋矩阵与旋转图像中边界收缩法与原地转置+翻转的实现要点？

问题

说明螺旋矩阵的边界收缩法与旋转图像的原地转置+翻转实现要点？

考察点

螺旋矩阵四边界收缩
旋转图像转置+翻转的等价变换
原地操作与边界细节

答案

螺旋矩阵：维护 top/bottom/left/right，按右→下→左→上循环，每走完一条边收缩对应边界，循环条件 top<=bottom && left<=right；注意单行/单列时避免重复添加（如 right 边后若 top>bottom 直接 break）。旋转图像 90°（顺时针）：先原地转置（a[i][j] 与 a[j][i] 互换，仅 i<j），再把每行反转；逆时针则是转置后每列反转。要点：转置只处理 i<j 避免重复交换；行反转用双指针。二者都是 O(n²) 时间、O(1) 空间。

解析

螺旋矩阵用"边界收缩 + 方向循环"的顺序遍历；旋转用"转置+翻转"的等价分解，避免逐元素旋转的复杂下标。两者都强调原地与边界。旋转的"转置+翻转"是空间 O(1) 的经典技巧。

示例代码

// 旋转图像（顺时针 90°）
void rotate(int[][] m) {
    int n = m.length;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t; }
    for (int i = 0; i < n; i++) { int l = 0, r = n - 1; while (l < r) { int t = m[i][l]; m[i][l] = m[i][r]; m[i][r] = t; l++; r--; } }
}

#

★★

11. 大数相加/相乘的手写实现中进位处理与前导零清理？

问题

手写大数相加与相乘，说明进位处理与前导零清理？

考察点

字符串表示的逐位相加进位
相乘的逐位累加与进位
前导零清理（结果去掉开头多余的 0）

答案

大数相加：从低位到高位逐位相加，维护进位 carry，把两个数字串与可能的进位相加，结果逐位插入；最后处理最高位进位。大数相乘：用数组 res 存中间结果，位置 i+j 累加 a[i]*b[j]，然后从低位到高位处理进位（res[k+1]+=res[k]/10; res[k]%=10），最后逆序输出并清理前导零。前导零清理：结果为 "0" 或 "0000" 这类时，去掉开头所有 '0'，但至少保留一个 '0'（处理全零）。进位处理的关键是"逐位加并传递进位"，相乘则是"双层循环 + 进位规范化"。

解析

大数运算本质是"模拟人工竖式"。相加维护一个进位；相乘先逐位乘积累加到位置数组，再一次扫描进位。前导零清理要保证"全是零时也输出一个 0"。这是"字符串模拟"的经典题。

示例代码

String addStrings(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry > 0) {
        int s = carry;
        if (i >= 0) s += a.charAt(i--) - '0';
        if (j >= 0) s += b.charAt(j--) - '0';
        sb.append(s % 10); carry = s / 10;
    }
    return sb.reverse().toString();
}

#

★★

12. 字符串匹配中 KMP 的 next 数组构建，与 BM 算法的坏字符/好后缀启发式？

问题

说明 KMP 的 next 数组构建，以及 BM 算法的坏字符与好后缀启发式？

考察点

KMP next 数组（最长公共前后缀）
KMP 匹配时主串不回退
BM 坏字符/好后缀两种跳步启发式

答案

KMP：next[i] 表示模式串前 i 个字符的最长相等前后缀长度（不含 i 整个串）。构建：两指针，若相同则 next[i]=next[i-1]+1，否则回退到 next[next[i-1]]。匹配时主串指针不回退，失配时按 next 移动模式串，故 O(n+m)。BM：从右往左匹配，失配时用两种启发式取较大跳步：① 坏字符规则：对齐后，把模式串中靠右的相同字符移到失配位置；② 好后缀规则：利用已匹配的后缀，把模式串中有相同后缀的前缀对齐，或移动整个（无相同后缀时）。BM 通常比 KMP 快（尤其英文文本），但构建复杂度 O(n+m)，最坏有退化。

解析

KMP 的 next 数组是"前缀函数"，让失配时主串不回退、模式串一次性跳到可复用前缀的位置。BM 从右往左匹配，坏字符/好后缀都给出"尽量跳远"的步长，取两者最大值保证不跳过头。BM 适合长文本，KMP 更稳定。

示例代码

// KMP next 数组构建
int[] buildNext(String p) {
    int[] next = new int[p.length()];
    for (int i = 1, j = 0; i < p.length(); i++) {
        while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
        if (p.charAt(i) == p.charAt(j)) j++;
        next[i] = j;
    }
    return next;
}

#

★★

13. KMP 与 Z 函数中 next 数组/最长公共前后缀的两种等价构造？

问题

说明 KMP 的 next 数组与 Z 函数两种等价构造？

考察点

Z 函数定义（以 i 开头的子串与前缀的最长公共前缀）
next 与 Z 的等价关系
两者互相转换

答案

Z 数组：z[i] 表示从位置 i 开始的子串与整个字符串前缀的最长公共前缀长度。Z 函数用线性算法构建：维护 [l,r] 区间（当前最右已匹配的 Z-box），若 i≤r 则 z[i]=min(z[i-l], r-i+1) 再扩展，否则从 0 扩展，总 O(n)。KMP 的 next（前缀函数）与 Z 函数等价：next[i] 表示前缀长度 i 的最长相等前后缀，而 z 数组能推导出前缀函数（next[i] 与 z 的关系为：对每个 i，若 z[i]>0 则更新 next[i+z[i]-1]=max(next[i+z[i]-1], z[i])，再倒序传递）。两者都刻画"最长公共前后缀"信息，只是视角不同（next 按前缀长度、Z 按起始位置）。

解析

两者是同一信息的两种编码：next 关注"前缀 i 的最长相等前后缀"，Z 关注"每个位置与开头的 LCP"。Z 算法以"Z-box 复用"达到线性，KMP 以前缀函数回退达到线性。它们的等价性是字符串匹配领域的经典对应关系。

示例代码

// Z 函数
int[] zFunction(String s) {
    int n = s.length();
    int[] z = new int[n];
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    return z;
}

#

★★

14. 有序矩阵搜索（LeetCode 240）中为什么从右上角开始搜索能 O(m+n)，从左下角开始的对称性？

问题

有序矩阵搜索（每行升序、每列升序），说明从右上角搜索为何 O(m+n)，以及从左下角开始的对称性？

考察点

右上角/左下角作为"拐点"的性质
每次比较排除一行或一列
与二分搜索的对比

答案

从右上角（或左下角）开始：右上角元素 matrix[0][n-1] 是所在行最大、所在列最小（因每行升序、每列升序）。若 target 大于它，则整行都小于 target，向下移动（排除一行）；若 target 小于它，则整列都大于 target，向左移动（排除一列）。每次比较排除一行或一列，最多 m+n 步，故 O(m+n)。从左下角对称：左下角是所在行最小、所在列最大，target 大则右移（排除列），target 小则上移（排除行），同样 O(m+n)。关键在"拐角元素同时是一端的最值，使每次比较能排除一种维度"。

解析

右上角/左下角的"鹰嘴"性质（行最大列最小，或反之）让每次比较要么排除整行要么排除整列，把搜索压缩成 O(m+n)。若从左上角失败（左上角同时是行最小列最小，无法排除），这解释了为何必须选拐角。这是"有序矩阵"搜索的经典 O(m+n) 解法。

示例代码

boolean searchMatrix(int[][] m, int target) {
    int r = 0, c = m[0].length - 1; // 右上角
    while (r < m.length && c >= 0) {
        if (m[r][c] == target) return true;
        else if (m[r][c] < target) r++; // 排除整行
        else c--;                       // 排除整列
    }
    return false;
}

#

★★

15. 字母异位词与滑动窗口（LeetCode 438）中字符计数如何 O(n) 判断窗口内是否为异位词，计数如何更新？

问题

找到字符串中所有字母异位词，说明字符计数如何 O(n) 判断窗口内是否为异位词，以及计数如何更新？

考察点

固定窗口 + 字符计数数组
滑动窗口左右移动时计数更新
用"差异计数"或"匹配数"优化判断

答案

用固定长度 p 的滑动窗口。维护一个计数数组 count（对 p 先扣减，窗口内字符增加），或用"窗口内与 p 的差异计数"。常用做法：count 数组初始化时对 p 中字符 -1，窗口内字符 +1；统计一个 match 变量表示"count 中值为 0 的字符数"。滑动时：右指针加入字符，左指针移出字符，更新 count 与 match。当 match==26（所有字符都平衡）时，窗口构成异位词。O(n) 来自线性滑动，每次更新 O(1)（只动窗口两端字符的计数）。

解析

核心是"字符计数 + 平衡判断"。直接比较两个计数数组需 O(26)，但用 match 变量维护"平衡字符数"可在 O(1) 判断，把总复杂度降到 O(n)。滑动窗口的计数更新是"右边加、左边减"，保持窗口长度固定。

示例代码

List<Integer> findAnagrams(String s, String p) {
    int[] cnt = new int[26];
    for (char c : p.toCharArray()) cnt[c - 'a']--;
    List<Integer> res = new ArrayList<>();
    int match = 0;
    for (int i = 0; i < 26; i++) if (cnt[i] == 0) match++;
    for (int r = 0; r < s.length(); r++) {
        int add = s.charAt(r) - 'a';
        if (++cnt[add] == 0) match++; else if (cnt[add] == 1) match--; // 更新
        if (r >= p.length()) {
            int rm = s.charAt(r - p.length()) - 'a';
            if (--cnt[rm] == 0) match++; else if (cnt[rm] == -1) match--;
        }
        if (match == 26) res.add(r - p.length() + 1);
    }
    return res;
}

#

★★

16. 罗马数字转整数（LeetCode 13）中为什么只需比较当前字符与下一字符的大小即可判断左减右加？

问题

将罗马数字转整数，说明为什么只需比较当前字符与下一字符的大小即可判断左减右加？

考察点

罗马数字的规则：小值在左则减、在右则加
只需比较当前与下一字符的数值大小
单调不增的规则

答案

罗马数字中，每个符号代表一个数值，且规则可归纳为：若当前符号的值小于其右侧符号的值，则当前值应减去（左减）；否则加上（右加）。例如 IV：I(1)<V(5)，故减 1 得 4；VI：V(5)>I(1)，加 1 得 6。只需比较当前与下一字符，因为罗马数字的"左减右加"只在相邻字符间发生，且不会出现连续左减（如 IX 是 9，I 与 X 相邻）。遍历时，若当前值<下一值则减当前，否则加当前，最后加上最后一个字符。复杂度 O(n)。

解析

罗马数字的数值结构保证"减法只发生在相邻且左小右大"。逐字符比较相邻即可，无需回溯。这是"编码规则简化"的经典题——把"左减右加"化为"相邻比较"。

示例代码

int romanToInt(String s) {
    int res = 0;
    for (int i = 0; i < s.length(); i++) {
        int cur = value(s.charAt(i));
        if (i + 1 < s.length() && cur < value(s.charAt(i + 1))) res -= cur;
        else res += cur;
    }
    return res;
}
int value(char c) {
    switch (c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}

#

★★

17. 最长公共前缀（LeetCode 14）中纵向逐字符扫描与排序后比较首尾字符串的取舍？

问题

求最长公共前缀，说明纵向逐字符扫描与排序后比较首尾字符串的取舍？

考察点

纵向扫描：逐列比较所有字符串的同一位置
排序后比较首尾字符串
两种方法的复杂度与适用

答案

纵向扫描：取第一个字符串为基准，逐列比较所有字符串的相同位置字符，直到某列不匹配或越界，公共前缀即前面匹配的列。O(n×L)（n 为字符串数，L 为最短串长度），空间 O(1)。排序后比较首尾：把所有字符串排序，公共前缀等于"排序后第一个与最后一个字符串的公共前缀"（因为排序后差异最大的两个在首尾，它们的公共前缀即整体公共前缀）。排序 O(n log n×L)，无需逐列比较。取舍：n 小、字符串短时纵向扫描更简单直接；n 大且字符串长时排序后只比较首尾更省（但排序本身有成本）。实际纵向扫描最常用。

解析

纵向扫描直观、无需排序，是标准解法；排序法利用"排序后首尾差异最大"的性质，把问题缩到两个字符串。纵向扫描 O(nL) 已很线性，排序法因排序开销 O(n log n) 通常不优，但可作为一种思路。

示例代码

String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++)
            if (i >= strs[j].length() || strs[j].charAt(i) != c) return strs[0].substring(0, i);
    }
    return strs[0];
}

#

★★

18. 字符串解码（LeetCode 394）中栈如何同时保存重复次数与已解码前缀，嵌套括号的展开顺序？

问题

解码如 "3[a2[c]]" 的字符串，说明栈如何同时保存重复次数与已解码前缀，以及嵌套括号的展开顺序？

考察点

双栈：数字栈与字符串栈
遇到 [ 时压栈、遇到 ] 时弹栈展开
嵌套括号的从内向外展开

答案

用两个栈：一个存重复次数（num 栈），一个存已解码前缀（str 栈）。遍历：数字字符累积成 num；'[' 时把当前 num 与当前已解码前缀压栈，并重置；字母直接累积到当前前缀；']' 时弹出 num 与前缀，把当前前缀重复 num 次拼到弹出的前缀后，作为新的当前前缀。嵌套括号按"后进先出"顺序从内向外展开：先遇到内层 ']' 先展开，再展开外层。例 "3[a2[c]]"：处理到内层 ']' 时 "c" 重复 2 次得 "cc"；再处理外层 ']' 时 "acc" 重复 3 次得 "accaccacc"。

解析

双栈（数字+前缀）是处理"嵌套重复"的标准结构。遇到 '[' 时把上下文压栈，遇到 ']' 时恢复并展开，天然匹配嵌套的 LIFO 顺序。展开从最内层开始，符合"内层先完成"的规则。

示例代码

String decodeString(String s) {
    Deque<Integer> numStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int num = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) num = num * 10 + (c - '0');
        else if (c == '[') { numStack.push(num); strStack.push(cur); cur = new StringBuilder(); num = 0; }
        else if (c == ']') {
            int k = numStack.pop(); StringBuilder prev = strStack.pop();
            for (int i = 0; i < k; i++) prev.append(cur);
            cur = prev;
        } else cur.append(c);
    }
    return cur.toString();
}

#

★★

19. 杨辉三角（LeetCode 118/119）中递推公式 dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 与只用 O(k) 空间的滚动数组写法？

问题

生成杨辉三角，说明递推公式，以及只用 O(k) 空间的滚动数组写法？

考察点

递推公式 dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
完整三角 vs 只求第 k 行
滚动数组从后往前更新

答案

杨辉三角递推：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]，边界 dp[i][0]=dp[i][i]=1。生成完整 n 行时每行都新数组，O(n²) 空间。求第 k 行（119）用 O(k) 空间：用一维数组滚动，从第 k 行从后往前更新 ans[j]=ans[j]+ans[j-1]（j 从 i 到 1），因为新值依赖上一行的 ans[j] 与 ans[j-1]，从后往前保证 ans[j-1] 还是上一行的值。首尾为 1。例第 3 行 [1,2,1]：从后往前更新得到 [1,3,3,1]。

解析

递推公式是"二项式系数"的 Pascal 递推。滚动数组的关键是"从后往前"更新，使 ans[j-1] 保留上一行旧值，避免被本轮覆盖。这是"只依赖上一行"的二维 DP 空间优化标准写法。

示例代码

List<Integer> getRow(int k) {
    List<Integer> row = new ArrayList<>();
    row.add(1);
    for (int i = 1; i <= k; i++) {
        row.add(0);
        for (int j = i; j >= 1; j--) row.set(j, row.get(j) + row.get(j - 1)); // 从后往前
    }
    return row;
}

#

★★

20. 矩阵置零（LeetCode 73）中如何用第一行与第一列作标记实现 O(1) 额外空间，标记冲突如何避免？

问题

矩阵置零，说明如何用第一行与第一列作标记实现 O(1) 空间，以及标记冲突如何避免？

考察点

用第一行/第一列记录该行/列是否置零
标记冲突：第一行/列本身是否置零需单独标志
分两个阶段处理

答案

用第一行和第一列作为标记：遍历矩阵，若 a[i][j]==0，则设 a[i][0]=0 与 a[0][j]=0 作为"该行/该列要置零"的标记。但第一行与第一列本身是否置零需单独用两个布尔变量 row0、col0 记录（因为标记会覆盖它们自身的原始状态）。处理分阶段：先遍历并记录标记与 row0/col0；再据标记把非首行首列中需要置零的格子置零；最后单独处理第一行与第一列（若 row0/col0 为真则整行/整列置零）。O(1) 空间。标记冲突的根源：第一行/第一列的格子既是被标记区又可能是被置零对象，用两个布尔变量消歧。

解析

核心是"把标记存在矩阵自身（第一行/列）"，省去额外数组。但第一行/列兼作标记与被处理对象存在冲突，故先用 row0/col0 保存其原始意图。这是"原地标记"的经典题，两个布尔变量是消歧关键。

示例代码

void setZeroes(int[][] m) {
    boolean row0 = false, col0 = false;
    for (int j = 0; j < m[0].length; j++) if (m[0][j] == 0) row0 = true;
    for (int i = 0; i < m.length; i++) if (m[i][0] == 0) col0 = true;
    for (int i = 1; i < m.length; i++) for (int j = 1; j < m[0].length; j++)
        if (m[i][j] == 0) { m[i][0] = 0; m[0][j] = 0; }
    for (int i = 1; i < m.length; i++) for (int j = 1; j < m[0].length; j++)
        if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
    if (row0) for (int j = 0; j < m[0].length; j++) m[0][j] = 0;
    if (col0) for (int i = 0; i < m.length; i++) m[i][0] = 0;
}

#

★

21. 矩阵的原地旋转/翻转中如何用转置+行反转实现 90° 旋转？

问题

说明矩阵原地旋转 90° 的转置+行反转实现？

考察点

顺时针旋转 = 转置 + 行反转
逆时针旋转 = 转置 + 列反转
转置的原地交换

答案

顺时针旋转 90°：先转置（a[i][j] 与 a[j][i] 互换，仅 i<j），再对每一行反转。组合效果：转置把 (i,j) 移到 (j,i)，行反转把 (j,i) 移到 (j, n-1-i)，等价于顺时针旋转 (i,j)→(j,n-1-i)。逆时针旋转：转置后对每一列反转（每列上下反转），效果 (i,j)→(n-1-j,i)。转置用原地双层循环（i<j 交换避免重复）。两者都是 O(n²) 时间、O(1) 空间。

解析

"转置+翻转"把旋转分解为两个简单操作，避免逐元素旋转的复杂下标变换。转置是基础，翻转方向决定顺逆时针。这是空间 O(1) 旋转的标准技巧。

示例代码

// 顺时针旋转：转置 + 行反转
void rotate90(int[][] m) {
    int n = m.length;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t; }
    for (int i = 0; i < n; i++) { int l = 0, r = n - 1; while (l < r) { int t = m[i][l]; m[i][l] = m[i][r]; m[i][r] = t; l++; r--; } }
}

#

★

22. 生命游戏（LeetCode 289）中原地更新时如何用“当前/下一状态”两位编码避免覆盖影响？

问题

生命游戏原地更新，说明如何用当前/下一状态两位编码避免覆盖影响？

考察点

每位格子的 8 邻域活细胞计数
用二进制两位编码（当前位/下一位）省空间
扫描后统一更新

答案

用二进制两位编码：最低位存当前状态（0 死/1 活），高位存下一状态。遍历时，对每个格子统计周围 8 格子的"当前状态"（取 &1），按生命游戏规则决定下一状态，写入高位的第二位（2 表示将活，1 表示下一状态死但当前活）。统计用低位的当前状态，不受高位影响。全部扫描后再统一把每个格子右移一位（>>1）得到下一状态。这样在同一矩阵内同时保存当前与下一状态，避免使用新矩阵，O(1) 额外空间。规则：活细胞周围 2/3 活则活，否则死；死细胞周围 3 活则活。

解析

位编码是"原地更新"的通用技巧：用不同位存"当前"与"下一"状态，统计时读低位、写高位，最后整体右移提交。避免了"先更新会影响后续统计"的覆盖问题。这是"状态压缩 + 原地"的经典题。

示例代码

void gameOfLife(int[][] board) {
    int m = board.length, n = board[0].length;
    int[] dx = {-1,-1,-1,0,0,1,1,1}, dy = {-1,0,1,-1,1,-1,0,1};
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
        int live = 0;
        for (int k = 0; k < 8; k++) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni >= 0 && nj >= 0 && ni < m && nj < n && (board[ni][nj] & 1) == 1) live++;
        }
        if (board[i][j] == 1 && (live == 2 || live == 3)) board[i][j] |= 2; // 下一状态活
        if (board[i][j] == 0 && live == 3) board[i][j] |= 2;
    }
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) board[i][j] >>= 1; // 提交
}