 算法解析)
教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载字符串删除是算法面试中的高频基础题难点不在于“删掉一个字符”而在于在不开辟新空间的前提下用一次遍历完成删除并保持剩余字符的相对顺序。本专题基于 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。两个指针配合的规则当前front指向的字符 ≠ 目标字符两个指针一起前进并且把*front拷贝到*rear指向的空间覆写当前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 *backsrc,*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(N × M)N 为源串长度M 为删除集合长度O(1)哈希表 一次遍历先用 256 长度的数组把删除集合打上标记再复用双指针一次遍历O(N M)O(256)即 O(1) 常量空间蛮力法的问题在于内层每次都要 O(M) 去“查找”整体退化为平方级。而借助哈希表把“是否删除”的判定降到 O(1)整体一次遍历即可完成。3.3 哈希表标记的正确打开方式注意 char 的符号性初始化 256 长度的标记数组时有一个 C 语言经典陷阱仓库 1.1 字符串-查找.md 中特别强调过char的范围是 -128~127unsigned 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。对abc123de4fg56123、4、56六个数字被跳过abcdefg依次被覆写回原数组输出abcdefg。时间复杂度 O(N)、空间复杂度 O(1)全程只对原数组做就地覆写。4.3 仓库中的同型实现filternum仓库 string.c 中保留了该问题的另一个实现filternum逻辑完全一致仅命名不同back/forward对应start/endvoid filternum(char *src){ if (!*src) return; char *backsrc, *forwardsrc; while(*forward){ if (*forward 0 *forward 9){ forward; // 数字跳过 }else{ *back *forward; // 非数字覆写保留 } } *back\0; }这两个版本佐证了同一结论“删除数字并压缩”本质上就是“按字符类别过滤 双指针原地覆写”与第二节的删除指定字符共用同一套代码骨架。4.4 边界情况自查清单面试中写完代码后建议主动用以下输入自查输入预期输出说明123456空串全部删除start未前进只在原位置写\0abcabc无数字原样保留空串while不执行写\0安全NULL不做操作返回 NULLtrim_number显式判空filternum用if (!*src)兜底a1b2c3abc数字与非数字交错注意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 向面试官讲解的要点顺序先讲朴素解法O(N²) 批量搬移并主动点明瓶颈提出双指针快指针读、慢指针写删除跳过用不变量write read证明算法不会破坏未扫描数据分析复杂度O(N) 时间、O(1) 额外空间字符集解法为 O(256) 常量空间指出\0收尾、NULL判空、char符号性等边界细节。这套表达顺序与仓库 README.md 中“编程思路和框架 → 编程细节”的刷题方法论一致先套框架再抠细节。5.3 在项目与面试题库中的位置本专题隶属于仓库 9 Algorithms Job Interview 面试题整理的字符串模块与 1 字符串.md 中罗列的“回文判断、字符统计、子串查找、字符串修改、字符串压缩”共同构成字符串高频考点。掌握了双指针原地覆写后可以顺带打通 1.3 字符串-修改.md 中“替换空格从后往前双指针”等姊妹题——它们共用同一类“指针分工”的思维模型。六、总结本文围绕“字符串删除”从三个递进层次展开删除单个指定字符双指针 front/rear 原地覆写O(N) 时间、O(1) 空间源码见 delete_occurence_character.c删除字符集256 位哈希表打标记 双指针一次遍历O(NM) 时间注意char符号性陷阱删除数字并压缩本质是“按类别过滤”trim_number与仓库filternum双版本互证O(N) 时间、零额外空间。三者共享同一个代码骨架理解“快指针负责读、慢指针负责写”的不变量后这一类题即可举一反三。仓库内对应的完整源码、可运行测试与笔记原文可作为进一步研读与动手编译验证的第一手材料。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐LeetCode 1384 链表的保留 m 个、删除 n 个模式双指针原地删除与 O(1) 空间实现LeetCode 1384 链表的保留 m 个、删除 n 个模式双指针原地删除与 O 1 空间实现 本文围绕 leetcode 仓库中的文章 delete示例工程教程DigitalPlat FreeDomain终极指南零成本构建全球数字身份的技术实战解析DigitalPlat FreeDomain终极指南零成本构建全球数字身份的技术实战解析 在数字化浪潮席卷全球的今天拥有专属域名已成为个人品牌和企业在线存在教程LeetCode 1209 全解析删除字符串中所有相邻重复字符的四种解法从暴力扫描到双指针原地修改LeetCode 1209 全解析删除字符串中所有相邻重复字符的四种解法从暴力扫描到双指针原地修改 本文以仓库中的题解文档 remove all adja示例工程教程上一篇Deep Image Prior模型解释使用Grad-CAM可视化特征重要性下一篇DouK-Downloader 从 0 跑通抖音/TikTok 作品下载与数据采集实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Learn-Algorithms 字符串删除专题：双指针原地删除与 O(N) 算法解析
教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载字符串删除是算法面试中的高频基础题难点不在于“删掉一个字符”而在于在不开辟新空间的前提下用一次遍历完成删除并保持剩余字符的相对顺序。本专题基于 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。两个指针配合的规则当前front指向的字符 ≠ 目标字符两个指针一起前进并且把*front拷贝到*rear指向的空间覆写当前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 *backsrc,*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(N × M)N 为源串长度M 为删除集合长度O(1)哈希表 一次遍历先用 256 长度的数组把删除集合打上标记再复用双指针一次遍历O(N M)O(256)即 O(1) 常量空间蛮力法的问题在于内层每次都要 O(M) 去“查找”整体退化为平方级。而借助哈希表把“是否删除”的判定降到 O(1)整体一次遍历即可完成。3.3 哈希表标记的正确打开方式注意 char 的符号性初始化 256 长度的标记数组时有一个 C 语言经典陷阱仓库 1.1 字符串-查找.md 中特别强调过char的范围是 -128~127unsigned 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。对abc123de4fg56123、4、56六个数字被跳过abcdefg依次被覆写回原数组输出abcdefg。时间复杂度 O(N)、空间复杂度 O(1)全程只对原数组做就地覆写。4.3 仓库中的同型实现filternum仓库 string.c 中保留了该问题的另一个实现filternum逻辑完全一致仅命名不同back/forward对应start/endvoid filternum(char *src){ if (!*src) return; char *backsrc, *forwardsrc; while(*forward){ if (*forward 0 *forward 9){ forward; // 数字跳过 }else{ *back *forward; // 非数字覆写保留 } } *back\0; }这两个版本佐证了同一结论“删除数字并压缩”本质上就是“按字符类别过滤 双指针原地覆写”与第二节的删除指定字符共用同一套代码骨架。4.4 边界情况自查清单面试中写完代码后建议主动用以下输入自查输入预期输出说明123456空串全部删除start未前进只在原位置写\0abcabc无数字原样保留空串while不执行写\0安全NULL不做操作返回 NULLtrim_number显式判空filternum用if (!*src)兜底a1b2c3abc数字与非数字交错注意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 向面试官讲解的要点顺序先讲朴素解法O(N²) 批量搬移并主动点明瓶颈提出双指针快指针读、慢指针写删除跳过用不变量write read证明算法不会破坏未扫描数据分析复杂度O(N) 时间、O(1) 额外空间字符集解法为 O(256) 常量空间指出\0收尾、NULL判空、char符号性等边界细节。这套表达顺序与仓库 README.md 中“编程思路和框架 → 编程细节”的刷题方法论一致先套框架再抠细节。5.3 在项目与面试题库中的位置本专题隶属于仓库 9 Algorithms Job Interview 面试题整理的字符串模块与 1 字符串.md 中罗列的“回文判断、字符统计、子串查找、字符串修改、字符串压缩”共同构成字符串高频考点。掌握了双指针原地覆写后可以顺带打通 1.3 字符串-修改.md 中“替换空格从后往前双指针”等姊妹题——它们共用同一类“指针分工”的思维模型。六、总结本文围绕“字符串删除”从三个递进层次展开删除单个指定字符双指针 front/rear 原地覆写O(N) 时间、O(1) 空间源码见 delete_occurence_character.c删除字符集256 位哈希表打标记 双指针一次遍历O(NM) 时间注意char符号性陷阱删除数字并压缩本质是“按类别过滤”trim_number与仓库filternum双版本互证O(N) 时间、零额外空间。三者共享同一个代码骨架理解“快指针负责读、慢指针负责写”的不变量后这一类题即可举一反三。仓库内对应的完整源码、可运行测试与笔记原文可作为进一步研读与动手编译验证的第一手材料。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐LeetCode 1384 链表的保留 m 个、删除 n 个模式双指针原地删除与 O(1) 空间实现LeetCode 1384 链表的保留 m 个、删除 n 个模式双指针原地删除与 O 1 空间实现 本文围绕 leetcode 仓库中的文章 delete示例工程教程DigitalPlat FreeDomain终极指南零成本构建全球数字身份的技术实战解析DigitalPlat FreeDomain终极指南零成本构建全球数字身份的技术实战解析 在数字化浪潮席卷全球的今天拥有专属域名已成为个人品牌和企业在线存在教程LeetCode 1209 全解析删除字符串中所有相邻重复字符的四种解法从暴力扫描到双指针原地修改LeetCode 1209 全解析删除字符串中所有相邻重复字符的四种解法从暴力扫描到双指针原地修改 本文以仓库中的题解文档 remove all adja示例工程教程上一篇Deep Image Prior模型解释使用Grad-CAM可视化特征重要性下一篇DouK-Downloader 从 0 跑通抖音/TikTok 作品下载与数据采集实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考