第48章面试高频题（一）

课程目录第48章面试高频题（一）

48、面试高频题（一）：字符串反转、判断回文、查找第一个只出现一次的字符、atoi实现

说实话，面试到了这个阶段，面试官基本不会再问那些「C语言有多少个关键字」这种基础问题了。他们更关心的是——你能不能把代码写对、写稳、写漂亮。

这四道题，我称之为「面试必考四件套」。字符串反转、判断回文、找第一个只出现一次的字符、手写atoi。每一道都看似简单，但每一道都能筛掉不少人。我自己面试别人的时候，也特别喜欢拿这几道题来摸底。

好，咱们一个一个来拆。

1. 字符串反转

这道题，说白了就是考你双指针的敏感度。很多新手一上来就想着开个新数组，其实完全没必要。

  核心思路： 两个指针，一个指向头，一个指向尾，交换字符，然后向中间移动。

#include <stdio.h>
#include <string.h>

void reverse_string(char *s) {
    if (s == NULL) return;
    int left = 0;
    int right = strlen(s) - 1;
    char temp;

    while (left < right) {
        temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

int main() {
    char str[] = "hello";
    reverse_string(str);
    printf("%s\n", str);  // 输出 "olleh"
    return 0;
}

小提示： 记得检查空指针。我见过不少线上崩溃，就是因为传了个NULL进来，程序直接段错误。

我在项目中遇到过类似场景——嵌入式设备上要翻转一个协议字段的字节序。当时我第一反应就是用双指针，效率高，代码也干净。

2. 判断回文

回文就是正着读和反着读一样。比如 "aba"、"level"、"上海自来水来自海上"（嗯，中文也能玩）。

判断回文其实和字符串反转很像，也是双指针。只不过这次不用交换，而是比较。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool is_palindrome(const char *s) {
    if (s == NULL) return false;
    int left = 0;
    int right = strlen(s) - 1;

    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    printf("%d\n", is_palindrome("aba"));   // 1
    printf("%d\n", is_palindrome("hello")); // 0
    return 0;
}

注意： 如果字符串包含空格或标点，比如 "A man, a plan, a canal: Panama"，那就需要先做预处理——去除非字母数字字符，并统一大小写。面试时一定要问清楚面试官的输入范围。

我曾经在面试一个候选人时，他写回文判断，直接忽略了大小写问题。我问他「Aba是不是回文？」他愣了一下，然后才意识到要忽略大小写。嗯，细节决定成败。

3. 查找第一个只出现一次的字符

这道题，我愿称之为「哈希表思想的入门题」。题目是这样的：给定一个字符串，找到第一个不重复的字符，返回它的索引。如果不存在，返回 -1。

你想想看，最笨的办法是什么？两层循环，每个字符都往后找一遍。时间复杂度 O(n²)，面试官看了直摇头。

更好的办法是用一个计数数组。因为字符范围有限（ASCII 0-127），我们可以用一个大小为128的数组来记录每个字符出现的次数。

#include <stdio.h>
#include <string.h>

int first_unique_char(const char *s) {
    if (s == NULL) return -1;
    int count[128] = {0};
    int len = strlen(s);

    // 第一遍：统计每个字符出现次数
    for (int i = 0; i < len; i++) {
        count[(unsigned char)s[i]]++;
    }

    // 第二遍：找到第一个次数为1的字符
    for (int i = 0; i < len; i++) {
        if (count[(unsigned char)s[i]] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    printf("%d\n", first_unique_char("leetcode")); // 输出 0 (l)
    printf("%d\n", first_unique_char("aabb"));     // 输出 -1
    return 0;
}

技巧： 用 (unsigned char) 强制转换，是为了防止字符值为负数时数组越界。这个坑我踩过，血的教训。

我个人习惯在写这类题时，先问清楚字符集范围。如果是 Unicode，那数组就不够用了，得用哈希表。但面试时一般默认 ASCII，放心用数组就好。

4. atoi 实现

atoi 就是把字符串转成整数。这道题看起来简单，但坑特别多。我面试别人的时候，十个人里有八个写不全。

需要考虑的情况：

空字符串
前导空格
正负号
溢出（INT_MAX / INT_MIN）
非法字符

#include <stdio.h>
#include <limits.h>
#include <ctype.h>

int my_atoi(const char *s) {
    if (s == NULL) return 0;

    int i = 0;
    int sign = 1;
    long result = 0;  // 用 long 防止溢出

    // 跳过前导空格
    while (isspace(s[i])) {
        i++;
    }

    // 处理正负号
    if (s[i] == '+' || s[i] == '-') {
        sign = (s[i] == '-') ? -1 : 1;
        i++;
    }

    // 转换数字
    while (s[i] >= '0' && s[i] <= '9') {
        result = result * 10 + (s[i] - '0');

        // 溢出检查
        if (result * sign > INT_MAX) {
            return INT_MAX;
        }
        if (result * sign < INT_MIN) {
            return INT_MIN;
        }
        i++;
    }

    return (int)(result * sign);
}

int main() {
    printf("%d\n", my_atoi("   -42"));    // -42
    printf("%d\n", my_atoi("4193 with words")); // 4193
    printf("%d\n", my_atoi("words and 987"));  // 0
    printf("%d\n", my_atoi("-91283472332"));   // INT_MIN
    return 0;
}

重要： 溢出检查一定要在乘法之后、赋值之前做。我曾经见过有人先赋值再检查，结果已经溢出了，检查就失去了意义。

嗯，这里要注意一点：用 long 来暂存结果，是为了在溢出前能检测到。如果你用 int 来存，乘到一半就溢出了，那就没法救了。

知识体系总览

下面这张图，是我对这四道题核心逻辑的总结。你可以把它当作面试前的快速复习地图。

这四道题，每一道都代表了一类面试题的典型解法。字符串反转和回文是双指针的入门，唯一字符是哈希表思想的简化版，atoi 则是边界条件处理的集大成者。

我个人建议，把这四道题背熟、写熟、想熟。面试时遇到类似的题，你就能快速反应出套路。毕竟，面试官要的不是你「会不会」，而是你「稳不稳」。

📚 课程目录

48、面试高频题（一）：字符串反转、判断回文、查找第一个只出现一次的字符、atoi实现

1. 字符串反转

2. 判断回文

3. 查找第一个只出现一次的字符

4. atoi 实现

知识体系总览