IT面试题|麻瓜面试

Appearance

字符串 ​

字符串是面试中的常见题型，通常结合双指针、滑动窗口、动态规划等技巧来考察。本模块涵盖有效的字母异位词、回文子串、最长回文子串、字符串转换整数、KMP算法等经典题目。掌握字符串处理的常用API和核心算法是关键。

Q1: 有效的字母异位词 「🟢 初级」 ​

题目描述：给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

考察点：数组计数、哈希表、排序。

解题思路：

  • 方法1：排序后比较（时间O(nlogn)，空间O(1)或O(n)）
  • 方法2：数组计数（时间O(n)，空间O(1)因为字符集有限）- 最优解
  • 方法3：哈希表（时间O(n)，空间O(n)，适合Unicode字符）

代码实现：

java
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }
    for (char c : t.toCharArray()) {
        count[c - 'a']--;
        if (count[c - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

复杂度分析：时间复杂度 O(n)，遍历两次字符串；空间复杂度 O(1)，固定大小的计数数组。

变体扩展：

  • 变体1：字母异位词分组
  • 变体2：找到字符串中所有字母异位词
  • 变体3：字符串的排列
  • 变体4：赎金信

Q2: 反转字符串 「🟢 初级」 ​

题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

考察点：双指针、原地反转、字符操作。

解题思路：

  • 方法：双指针，左右指针向中间移动，交换对应字符（时间O(n)，空间O(1)）- 最优解

代码实现：

java
public void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

复杂度分析：时间复杂度 O(n)，交换n/2次；空间复杂度 O(1)，原地修改。

变体扩展：

  • 变体1：反转字符串II（每2k个字符反转前k个）
  • 变体2：反转字符串中的单词
  • 变体3：反转字符串中的元音字母
  • 变体4：整数反转

Q3: 回文子串 「🟡 中级」 ​

题目描述：给你一个字符串 s，请你统计并返回这个字符串中回文子串的数目。回文字符串是正读和反读都一样的字符串。子字符串是字符串中由连续字符组成的序列。

考察点：中心扩展法、动态规划、Manacher算法。

解题思路：

  • 方法1：暴力枚举（时间O(n³)，空间O(1)）
  • 方法2：中心扩展法，枚举每个回文中心向两边扩展（时间O(n²)，空间O(1)）- 最优解
  • 方法3：动态规划（时间O(n²)，空间O(n²)）
  • 方法4：Manacher算法（时间O(n)，空间O(n)）

代码实现：

java
public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += expand(s, i, i);     // 奇数长度回文
        count += expand(s, i, i + 1); // 偶数长度回文
    }
    return count;
}

private int expand(String s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        count++;
        left--;
        right++;
    }
    return count;
}

复杂度分析：时间复杂度 O(n²)，每个中心最多扩展n次；空间复杂度 O(1)。

变体扩展：

  • 变体1：最长回文子串
  • 变体2：最长回文子序列
  • 变体3：验证回文串
  • 变体4：回文数

Q4: 最长回文子串 「🟡 中级」 ​

题目描述：给你一个字符串 s，找到 s 中最长的回文子串。

考察点：中心扩展法、动态规划、Manacher算法。

解题思路：

  • 方法1：暴力枚举（时间O(n³)，空间O(1)）
  • 方法2：中心扩展法（时间O(n²)，空间O(1)）- 最优解
  • 方法3：动态规划（时间O(n²)，空间O(n²)）
  • 方法4：Manacher算法（时间O(n)，空间O(n)）

代码实现：

java
public String longestPalindrome(String s) {
    int start = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);     // 奇数长度
        int len2 = expand(s, i, i + 1); // 偶数长度
        int len = Math.max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

复杂度分析：时间复杂度 O(n²)，每个中心最多扩展n次；空间复杂度 O(1)。

变体扩展：

  • 变体1：回文子串（计数）
  • 变体2：最长回文子序列
  • 变体3：最短回文串
  • 变体4：分割回文串

Q5: 字符串转换整数 (atoi) 「🟡 中级」 ​

题目描述：请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。函数会根据以下步骤处理：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符是正号还是负号
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾
  4. 将前面步骤读入的这些数字转换为整数
  5. 如果整数数超过32位有符号整数范围，截断使其保持在范围内

考察点：字符串处理、边界判断、溢出处理。

解题思路：

  • 方法：按步骤逐步处理，注意符号、前导零、溢出判断（时间O(n)，空间O(1)）- 最优解

代码实现：

java
public int myAtoi(String s) {
    if (s == null || s.length() == 0) return 0;
    int i = 0, sign = 1, res = 0;
    int n = s.length();
    // 跳过前导空格
    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 digit = s.charAt(i) - '0';
        // 溢出判断
        if (res > Integer.MAX_VALUE / 10 || 
            (res == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        res = res * 10 + digit;
        i++;
    }
    return res * sign;
}

复杂度分析：时间复杂度 O(n)，最多遍历一次字符串；空间复杂度 O(1)。

变体扩展：

  • 变体1：整数反转
  • 变体2：回文数
  • 变体3：字符串相乘
  • 变体4：字符串相加

Q6: KMP算法 / 实现strStr() 「🔴 高级」 ​

题目描述：给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。

考察点：KMP算法、前缀函数（next数组）、字符串匹配。

解题思路：

  • 方法1：暴力匹配（时间O(m*n)，空间O(1)）
  • 方法2：KMP算法，利用next数组避免重复比较（时间O(m+n)，空间O(m)）- 最优解
  • 方法3：Rabin-Karp算法（滚动哈希）

代码实现：

java
public int strStr(String haystack, String needle) {
    if (needle.length() == 0) return 0;
    int[] next = buildNext(needle);
    int j = 0;
    for (int i = 0; i < haystack.length(); i++) {
        while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
            j = next[j - 1]; // 不匹配时回退
        }
        if (haystack.charAt(i) == needle.charAt(j)) {
            j++;
        }
        if (j == needle.length()) {
            return i - j + 1; // 匹配成功，返回起始下标
        }
    }
    return -1;
}

// 构建next数组（前缀函数）
private int[] buildNext(String pattern) {
    int[] next = new int[pattern.length()];
    int j = 0;
    for (int i = 1; i < pattern.length(); i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

复杂度分析：时间复杂度 O(m+n)，构建next数组O(m)，匹配O(n)；空间复杂度 O(m)，next数组。

变体扩展：

  • 变体1：重复的子字符串
  • 变体2：最短回文串
  • 变体3：找出字符串中第一个匹配项的下标
  • 变体4：旋转字符串

Copyright © 2025-2026 京公网安备 11010102000001号 京ICP备2024078125号-1