企业官网建设流程全解析

• 教程

字符串删除是算法面试中的高频基础题，难点不在于“删掉一个字符”，而在于在不开辟新空间的前提下，用一次遍历完成删除，并保持剩余字符的相对顺序。本专题基于 Learn-Algorithms 仓库的面试题笔记（1.2 字符串-删除.md），逐层拆解“删除指定字符 → 删除字符集 → 删除数字并压缩”三道递进题目，并结合仓库内 C 源码（delete_occurence_character.c、string.c）讲透双指针原地删除的原理、实现细节与复杂度。读完本文，你将掌握一类“快慢指针式”原地过滤字符问题的统一套路，可直接迁移到 LeetCode 同型题目及生产环境字符串清洗场景。

一、问题本质：为什么“删除字符”没有表面那么简单

对 C 语言字符串（以'\0'结尾的字符数组）执行删除操作时，有一个天然约束：字符数组长度是固定的，删除字符后必须把后续字符整体前移。

最直观的写法是：找到目标字符后，把它后面的所有字符逐个向前移动一位。例如删除"abcdeccba"中的'c'，每删一个'c'就要移动一次剩余串。

这种做法的复杂度是 O(N²)：

• 外层扫描每个字符需要 O(N)；
• 每次删除触发一次 O(N) 级别的整体搬移；
• 最坏情况（如"cccccccc"全部删除）下，搬移总量为 N + (N-1) + ... = O(N²)。

那么有没有 O(N) 的方法？答案是肯定的，核心武器就是双指针（快慢指针）原地覆写——这也是本文三条主线贯穿始终的统一套路。

二、双指针原地删除：front 与 rear 的配合

2.1 算法思想

维护两个指针，一前一后（一快一慢）：

• front（快指针）：负责向前扫描源字符串的每一个字符，是唯一的遍历者；
• rear（慢指针）：负责指向“下一个可写入的位置”，它始终不越过front。

两个指针配合的规则：

1. 当前front指向的字符 ≠ 目标字符：两个指针一起前进，并且把*front拷贝到*rear指向的空间（覆写）；
2. 当前front指向的字符 == 目标字符：front单独向前一步（跳过它，相当于“删除”），rear原地不动。

遍历结束后，在rear处写入字符串结束符'\0'，删除即完成。

之所以能做到 O(N)，是因为每个字符最多被读写一次，且删除操作退化为“跳过”，不再产生批量搬移。

2.2 源码实现

仓库中该算法的完整可运行版本位于 delete_occurence_character.c：

#include "stdio.h" char *delete_occurence_character(char *src , char target){ char *front = src; char *rear = src; while(*front != '\0'){ if (*front != target){ *rear = *front; rear++; } front++; } *rear = '\0'; return src; } int main(int argc, char const *argv[]) { char test[] = "abcdeccba"; printf("%s\n", delete_occurence_character(test,'c')); return 0; }

运行结果：

abdeba

注意主函数中的关键细节：测试串必须声明为可写的字符数组char test[] = "abcdeccba"，而不能是char *test = "abcdeccba"。因为该算法是原地修改，而字符串字面量在多数平台位于只读数据段，对其写入会触发运行时错误（仓库 string.c 的注释中就有// 居然会出 bus error！！！！！？？？？的踩坑记录，正是对只读字面量执行原地写导致的）。

2.3 正确性验证：为什么rear永远不会超过front

这是该算法最值得向面试官讲解的严谨性要点：

• 只有发生“跳过”时，rear才会落后于front；
• 没有跳过时，rear与front同步前进；
• 因此恒有rear <= front，*rear = *front覆写的永远是已扫描过的位置（或被跳过的待删除位置），绝不会破坏尚未扫描的字符。

这与“删除数组元素后用双指针压缩”是同一数学结构：慢指针指向新数组的写入端，快指针负责从旧数组取值。

2.4 变体：不用临时变量版

仓库 string.c 中还有一个结构相同但写法略有差异的版本delete_character，它把“相等则跳、不等则拷贝”的逻辑反过来组织：

void delete_character(char *src , char target){ char *back=src,*forward = src; while(*forward){ if (*forward == target){ forward++; }else{ *back++ = *forward++; } } *back = '\0'; }

两种写法本质一致：一个把“删除判断”放在拷贝分支里（if (*front != target)），一个把“删除判断”放在跳过分支里（if (*forward == target)）。面试时可任选一种，关键是向面试官讲清快指针负责读、慢指针负责写的职责划分。

三、升级版：从字符串中删除一个“字符集”

3.1 题目描述

输入两个字符串，从第一个字符串中删除第二个字符串中所有的字符。例如输入"They are students."和"aeiou"，则删除之后的第一个字符串变成"Thy r stdnts."。

这是上一题的升级版：判断条件从“等于单个字符”变成“属于一个字符集合”。

3.2 两种解法对比

蛮力法的问题在于：内层每次都要 O(M) 去“查找”，整体退化为平方级。而借助哈希表，把“是否删除”的判定降到 O(1)，整体一次遍历即可完成。

3.3 哈希表标记的正确打开方式：注意 char 的符号性

初始化 256 长度的标记数组时，有一个 C 语言经典陷阱（仓库 1.1 字符串-查找.md 中特别强调过）：char的范围是 -128~127，unsigned char才是 0~255。若直接用signed char作为数组下标，遇到扩展 ASCII 字符（大于 127）会产生负下标，导致越界访问。

正确写法应使用unsigned char（或显式转型）：

// 建立删除标记表：hash[c] = 1 表示 c 属于待删除集合 char *delete_occurence_characterset(char *source, const char *del){ unsigned char hash[256] = {0}; const unsigned char *p = (const unsigned char *)del; while (*p != '\0') { hash[*p] = 1; p++; } char *front = source; char *rear = source; while (*front != '\0') { // 不在删除集合中的字符才被保留（覆写） if (hash[(unsigned char)*front] == 0) { *rear = *front; rear++; } front++; } *rear = '\0'; return source; }

核心变化只有一处：把if (*front != target)换成if (hash[(unsigned char)*front] == 0)。双指针框架完全复用，这正是“一类题一个框架”的价值。

实测本题示例：输入"They are students."、删除集"aeiou"，输出"Thy r stdnts."——元音字母全部被跳过，剩余字符相对顺序不变。

3.4 延伸思考：字符集合变大怎么办

若删除集合不再是单字节字符，而是多字节编码（如 UTF-8 中文字符）或超长集合，可以改用布尔数组 + 动态扩容的哈希表（如 Open Addressing / 链地址法），思路不变，只是把 256 的定长表换成通用哈希结构。仓库 HashMap in Java.md、HashMap in Golang.md 中对哈希表的实现与扩容策略可作参考。

四、删除字符串中的数字并压缩（一次遍历、零额外空间）

4.1 题目描述

如字符串"abc123de4fg56"处理后变为"abcdefg"。要求注意空间和效率，最好一次遍历、不开辟新空间。

4.2 实现：trim_number

这道题与上一道是同一个意思——把“删除集合”具体化为'0' ~ '9'这 10 个数字字符。原文档给出示例：

char *trim_number(char *source){ char *start = source; char *end = source; if (source == NULL) return NULL; while(*end != '\0'){ if (*end < '0' || *end > '9' ){ *start = *end; start++; } end++; } *start = '\0'; return source; }

执行过程：

• end是快指针，逐字符扫描；
• 非数字字符（ASCII 码不在'0'(48) ~'9'(57) 区间）被拷贝到start指向的写入位；
• 数字字符被直接跳过；
• 结束时在start处补'\0'。

对"abc123de4fg56"：'1''2''3'、'4'、'5''6'六个数字被跳过，"abcdefg"依次被覆写回原数组，输出"abcdefg"。时间复杂度 O(N)、空间复杂度 O(1)，全程只对原数组做就地覆写。

4.3 仓库中的同型实现filternum

仓库 string.c 中保留了该问题的另一个实现filternum，逻辑完全一致，仅命名不同（back/forward对应start/end）：

void filternum(char *src){ if (!*src) return; char *back=src, *forward=src; while(*forward){ if (*forward >= '0' && *forward <= '9'){ forward++; // 数字：跳过 }else{ *back++ = *forward++; // 非数字：覆写保留 } } *back='\0'; }

这两个版本佐证了同一结论：“删除数字并压缩”本质上就是“按字符类别过滤 + 双指针原地覆写”，与第二节的删除指定字符共用同一套代码骨架。

4.4 边界情况自查清单

面试中写完代码后，建议主动用以下输入自查：

注意trim_number版本中if (source == NULL) return NULL;的判空是先于指针赋值执行的，这是防御式编程的好习惯；而filternum版本不处理NULL，使用时需保证传入非空串。

五、三题串讲：一类题的统一套路与面试表达

5.1 统一框架：原地过滤四步曲

把本文三道题抽象为同一个模板：

char *filter_in_place(char *src, int (*should_keep)(unsigned char c)){ if (src == NULL) return NULL; char *write = src; // 慢指针：写入位 char *read = src; // 快指针：扫描位 while (*read != '\0') { if (should_keep((unsigned char)*read)) { // 保留条件 *write++ = *read; } read++; } *write = '\0'; return src; }

• 删除指定字符：should_keep(c)为c != target；
• 删除字符集：should_keep(c)为hash[c] == 0；
• 删除数字：should_keep(c)为c < '0' || c > '9'。

凡是“从原串中过滤掉满足某条件的字符、保持相对顺序、原地完成”的问题，都可以先套这个框架，再填充条件逻辑。

5.2 向面试官讲解的要点顺序

1. 先讲朴素解法（O(N²) 批量搬移），并主动点明瓶颈；
2. 提出双指针：快指针读、慢指针写，删除=跳过；
3. 用不变量write <= read证明算法不会破坏未扫描数据；
4. 分析复杂度：O(N) 时间、O(1) 额外空间（字符集解法为 O(256) 常量空间）；
5. 指出'\0'收尾、NULL判空、char符号性等边界细节。

这套表达顺序与仓库 README.md 中“编程思路和框架 → 编程细节”的刷题方法论一致：先套框架，再抠细节。

5.3 在项目与面试题库中的位置

本专题隶属于仓库 9 Algorithms Job Interview 面试题整理的字符串模块，与 1 字符串.md 中罗列的“回文判断、字符统计、子串查找、字符串修改、字符串压缩”共同构成字符串高频考点。掌握了双指针原地覆写后，可以顺带打通 1.3 字符串-修改.md 中“替换空格（从后往前双指针）”等姊妹题——它们共用同一类“指针分工”的思维模型。

六、总结

本文围绕“字符串删除”从三个递进层次展开：

1. 删除单个指定字符：双指针 front/rear 原地覆写，O(N) 时间、O(1) 空间，源码见 delete_occurence_character.c；
2. 删除字符集：256 位哈希表打标记 + 双指针一次遍历，O(N+M) 时间，注意char符号性陷阱；
3. 删除数字并压缩：本质是“按类别过滤”，trim_number与仓库filternum双版本互证，O(N) 时间、零额外空间。

三者共享同一个代码骨架，理解“快指针负责读、慢指针负责写”的不变量后，这一类题即可举一反三。仓库内对应的完整源码、可运行测试与笔记原文，可作为进一步研读与动手编译验证的第一手材料。

• 教程