替换数字

发表于 更新于 分类于

算法-替换数字

背景

  • 算法–替换数字

  • 博主以代码随想录算法公开课进行学习

题目

  • 给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

    例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

    对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”

    输入：一个字符串 s,s 仅包含小写字母和数字字符。

    输出：打印一个新的字符串，其中每个数字字符都被替换为了number

    样例输入：a1b2c3

    样例输出：anumberbnumbercnumber

    数据范围：1 <= s.length < 10000。

思路

  • 统计数字数量：
    • 先遍历原字符串，统计其中数字字符的个数。这一步的核心目的是计算新字符串的长度 —— 因为每个数字（1 个字符）要替换成 “number”（6 个字符），相当于每个数字会让字符串长度增加 5，因此新长度 = 原长度 + 数字个数 × 5。
  • 创建新字符数组：
    • 基于计算出的新长度，创建一个固定长度的字符数组
  • 双指针从后往前填充：
    • 定义两个指针：i指向新字符数组的末尾（待填充位置），j指向原字符串的末尾（待遍历位置）。
    • 从后往前遍历原字符串：
      • 如果j指向的是字母，直接将该字母复制到i的位置，然后i和j都向前移动一位；
      • 如果j指向的是数字，从i的位置向前依次填充 ‘r’、‘e’、‘b’、‘m’、‘u’、‘n’（即 “number” 的逆序），然后i向前移动 6 位，j向前移动一位。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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 < sOldSize; i++) {
            if (Character.isDigit(s.charAt(i))) {
                count++;
            }
        }
        
        // 第二步：创建新字符数组，长度 = 原长度 + 数字个数*5（number是6个字符，替换1个数字多占5位）
        char[] newS = new char[sOldSize + count * 5];
        int sNewSize = newS.length;
        
        // 第三步：双指针从后往前填充（核心修正）
        // i：新数组指针，j：原字符串指针
        for (int i = sNewSize - 1, j = sOldSize - 1; j >= 0; j--) {
            // 如果是字母，直接复制到新数组
            if (!Character.isDigit(s.charAt(j))) {
                newS[i] = s.charAt(j);
                i--;
            } else {
                // 如果是数字，替换为"number"（从后往前填）
                newS[i] = 'r';
                newS[i - 1] = 'e';
                newS[i - 2] = 'b';
                newS[i - 3] = 'm';
                newS[i - 4] = 'u';
                newS[i - 5] = 'n';
                i -= 6; // 直接移动6位，避免循环的i--干扰（更清晰）
            }
        }
        
        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();
    }
}

总结

  • 从后往前填充的优势：避免从前往后填充时数字替换导致的字符覆盖，无需频繁移动已处理的字符，时间复杂度为 O (n)（n 为原字符串长度）。