双指针技巧在字符串反转与处理中的应用
1. 字符串操作基础与双指针技巧字符串处理是算法学习中最基础也最常考的核心技能点。今天要解决的两个经典问题 - 541.反转字符串II和151.翻转字符串里的单词恰好覆盖了字符串操作的两种典型场景局部处理和全局重组。先看第一个问题给定字符串abcdefg和k2需要每2k个字符反转前k个变成bacdfeg。这看似简单但隐藏着几个关键考察点边界处理当剩余字符不足k个时的处理逻辑遍历步长每次移动2k而非k的巧妙设计原地修改C等语言要求O(1)空间复杂度void reverse(string s, int start, int end) { for (int i start, j end; i j; i, j--) { swap(s[i], s[j]); } } string reverseStr(string s, int k) { for (int i 0; i s.size(); i 2 * k) { if (i k s.size()) { reverse(s, i, i k - 1); } else { reverse(s, i, s.size() - 1); } } return s; }关键技巧reverse函数采用双指针相向而行这是字符串反转的黄金模板。注意区间是左闭右闭[i, ik-1]这种边界定义能避免90%的off-by-one错误。2. 复杂字符串处理的拆解策略151题要求翻转字符串中的单词顺序保留空格例如the sky is blue变成blue is sky the。这需要综合运用多种字符串处理技术去多余空格首尾/中间连续空格整体反转字符串逐个反转单词def reverseWords(s: str) - str: # 去除多余空格 s list(s) n len(s) # 双指针去空格 slow fast 0 while fast n: if s[fast] ! : if slow ! 0: s[slow] slow 1 while fast n and s[fast] ! : s[slow] s[fast] slow 1 fast 1 fast 1 s s[:slow] # 整体反转 s.reverse() # 单词逐个反转 start 0 for i in range(len(s) 1): if i len(s) or s[i] : s[start:i] reversed(s[start:i]) start i 1 return .join(s)避坑指南Python中字符串不可变先转为list处理更高效去空格时slow指针的移动条件是关键需要处理单词间的单个空格。3. 双指针法的六种经典应用场景通过这两个题目我们可以总结双指针在字符串处理中的核心应用模式相向而行反转类问题同向快慢去重/删除元素中心扩散回文判断滑动窗口子串问题边界收缩容器类问题多序列比较归并类问题以快慢指针去空格为例我们需要明确fast指针探索新字符的侦察兵slow指针构建新字符串的工程师两者配合实现O(n)时间O(1)空间的操作// 快慢指针去空格模板 public String removeSpaces(String s) { char[] chars s.toCharArray(); int slow 0; for (int fast 0; fast chars.length; fast) { if (chars[fast] ! ) { if (slow ! 0) chars[slow] ; while (fast chars.length chars[fast] ! ) chars[slow] chars[fast]; } } return new String(chars, 0, slow); }4. 字符串处理的工程实践要点在实际工程中处理字符串时还需要注意编码问题明确使用UTF-8还是ASCII内存管理C要注意\0结束符不可变性Java/Python中字符串的不可变特性API选择正则表达式 vs 原生操作性能陷阱连续拼接使用StringBuilder特别提醒算法题中常用的s[i]访问方式在JavaScript中可能效率极低V8引擎的字符串优化策略实际开发中应转换为数组操作。// 低效写法 let reversed ; for (let i s.length - 1; i 0; i--) { reversed s[i]; // 每次拼接都创建新字符串 } // 高效写法 const arr s.split(); let left 0, right arr.length - 1; while (left right) { [arr[left], arr[right]] [arr[right], arr[left]]; left; right--; } return arr.join();在处理151题这类复杂字符串问题时建议分步骤验证先单独测试去空格函数再测试整体反转最后测试单词局部反转 这种分治策略能快速定位问题所在阶段。
)
