【LeetCode刷题日记】：字符串替换技巧揭秘

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言昨天是周六本来是说每天更新两个文章一篇算法相关的一篇后端的但是我虽然早上写了两题算法下午出去了然后晚上回来学了会项目再把文章发出来就已经凌晨了所以就留到周末来发这个算法题目了主要内容就是关于字符串的相关算法。题目背景卡码网 替换数字给定一个字符串 s它包含小写字母和数字字符请编写一个函数将字符串中的字母字符保持不变而将每个数字字符替换为number。例如对于输入字符串 a1b2c3函数应该将其转换为 anumberbnumbercnumber。对于输入字符串 a5b函数应该将其转换为 anumberb输入一个字符串 s,s 仅包含小写字母和数字字符。输出打印一个新的字符串其中每个数字字符都被替换为了number样例输入a1b2c3样例输出anumberbnumbercnumber数据范围1 s.length 10000。题目分析首先拿到这个题目显然就是字符串反转的问题但是又多了一些别的逻辑处理首先扩充数组到每个数字字符替换成 number 之后的大小。例如 字符串 a5b 的长度为3那么 将 数字字符变成字符串 number 之后的字符串为 anumberb 长度为 8。然后从后向前替换数字字符也就是双指针法过程如下i指向新长度的末尾j指向旧长度的末尾。为什么要从后向前填充从前向后填充不行么从前向后填充就是O(n^2)的算法了因为每次添加元素都要将添加元素之后的所有元素整体向后移动。其实很多数组填充类的问题其做法都是先预先给数组扩容带填充后的大小然后在从后向前进行操作。这里需要注意的是我们用的是javajava底层的字符串是不可变的所以我们要转成字符数组进行处理。之后我们将这个转成字符数组拷贝到新的已经扩容的字符数组中然后进行一系列的反转。char[] newS new char[s.length() count * 5];关于这个count也就是我们通过遍历得到字符串中有几个数字从而count一个count对应五个位置。接下来就是新数组中的处理了整体演示比较好理解原字符串: a 1 b 索引: 0 1 2 新数组(初始): a 1 b _ _ _ _ _ 索引: 0 1 2 3 4 5 6 7 从后向前处理: 第1步: 复制b → b 索引: 7 第2步: 遇到1 → 填入 number(反向) 填入: n u m b e r 索引: 1 2 3 4 5 6 最终结果: a n u m b e r b 0 1 2 3 4 5 6 7 转为字符串: anumberb主要还是要判断哪个位置是数字然后从后往前填充至于为什么这样因为如果是从前往后每次添加元素都要将添加元素之后的所有元素整体向后移动。题目答案import java.util.Scanner; public class Main { public static String replaceNumber(String s) { int count 0; // 统计数字的个数 int sOldSize s.length(); for (int i 0; i s.length(); i) { if(Character.isDigit(s.charAt(i))){ count; } } // 扩充字符串s的大小也就是每个空格替换成number之后的大小 char[] newS new char[s.length() count * 5]; int sNewSize newS.length; // 将旧字符串的内容填入新数组 System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize); // 从后先前将空格替换为number for (int i sNewSize - 1, j sOldSize - 1; j i; j--, i--) { if (!Character.isDigit(newS[j])) { newS[i] newS[j]; } else { newS[i] r; newS[i - 1] e; newS[i - 2] b; newS[i - 3] m; newS[i - 4] u; newS[i - 5] n; i - 5; } } return new String(newS); }; public static void main(String[] args) { Scanner scanner new Scanner(System.in); String s scanner.next(); System.out.println(replaceNumber(s)); scanner.close(); } }总结这个算法的核心思路先创建足够大的新数组复制原内容到新数组前半部分从后向前处理遇到非数字直接复制遇到数字则从后往前写入 number覆盖原数字位置因为 number 比 1 长必须向后延伸所以从后向前处理可以避免覆盖未处理的内容第二种写法// 为了还原题目本意先把原数组复制到扩展长度后的新数组然后不再使用原数组、原地对新数组进行操作。 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.next(); int len s.length(); for (int i 0; i s.length(); i) { if (s.charAt(i) 0 s.charAt(i) 9) { len 5; } } char[] ret new char[len]; for (int i 0; i s.length(); i) { ret[i] s.charAt(i); } for (int i s.length() - 1, j len - 1; i 0; i--) { if (0 ret[i] ret[i] 9) { ret[j--] r; ret[j--] e; ret[j--] b; ret[j--] m; ret[j--] u; ret[j--] n; } else { ret[j--] ret[i]; } } System.out.println(ret); }流程计算新数组长度text原长度 3 遇到数字1 → len 5 → len 8步骤2创建新数组并复制java char[] ret new char[8]; // [_, _, _, _, _, _, _, _] // 复制原字符串 ret [a, 1, b, _, _, _, _, _] 0 1 2 3 4 5 6 7步骤3从后向前填充java i 2, j 7第1次循环 (i2)ret[2] b不是数字java ret[7] b j 6结果[a, 1, b, _, _, _, _, b]第2次循环 (i1)ret[1] 1是数字java ret[6] r // j6→5 ret[5] e // j5→4 ret[4] b // j4→3 ret[3] m // j3→2 ret[2] u // j2→1 ret[1] n // j1→0结果[a, n, u, m, b, e, r, b]第3次循环 (i0)ret[0] a不是数字java ret[0] a // j0→ -1整体的逻辑更清晰易懂逻辑清晰i只管遍历原内容j只管填充新位置容易理解标准的双指针从后向前填充模式没有歧义不需要判断j i这种边界条件正确性保证每个数字固定多占5个位置指针移动步数确定结语其实在写算法题的时候我们要养成手撕的习惯这对我们以后的面试帮助很大刚开始肯定很难有时候连方法的格式返回值什么的都写的模糊不清但只要坚持下来会收获很大。如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励