解题思路

这是一道字符串处理题目，主要思路如下：

  1. 问题分析：

    • 每个数字对应一个英文单词
    • 单词被打乱，需要还原原始数字
    • 单词中的字母可能被多次使用

  2. 解决方案：

    • 统计每个关键字母的出现次数
    • 按特定顺序处理，避免重复计算
    • 通过减法消除重复使用的字母

  3. 数字对应关系：

    • ZERO(Z) -> 2
    • ONE(O) -> 3
    • TWO(W) -> 4
    • THREE(H) -> 5
    • FOUR(U) -> 6
    • FIVE(F) -> 7
    • SIX(X) -> 8
    • SEVEN(S) -> 9
    • EIGHT(G) -> 0
    • NINE(I) -> 1

代码

#include <stdio.h>
#include <string.h>

int main() {
    int b[10], n, len;
    char str[10001];
    scanf("%d", &n);
    
    while(n--) {
        // 初始化计数数组
        memset(b, 0, sizeof(b));
        scanf("%s", str);
        len = strlen(str);
        
        // 统计关键字母出现次数
        for(int i = 0; i < len; i++) {
            if(str[i] == 'Z') b[0]++;      // ZERO -> 2
            if(str[i] == 'O') b[1]++;      // ONE -> 3
            if(str[i] == 'W') b[2]++;      // TWO -> 4
            if(str[i] == 'H') b[3]++;      // THREE -> 5
            if(str[i] == 'U') b[4]++;      // FOUR -> 6
            if(str[i] == 'F') b[5]++;      // FIVE -> 7
            if(str[i] == 'X') b[6]++;      // SIX -> 8
            if(str[i] == 'S') b[7]++;      // SEVEN -> 9
            if(str[i] == 'G') b[8]++;      // EIGHT -> 0
            if(str[i] == 'I') b[9]++;      // NINE -> 1
        }
        
        // 处理重复字母
        b[1] = b[1] - b[0] - b[2] - b[4];  // O出现在ZERO,TWO,FOUR中
        b[3] = b[3] - b[8];                 // H出现在EIGHT中
        b[5] = b[5] - b[4];                 // F出现在FOUR中
        b[7] = b[7] - b[6];                 // S出现在SIX中
        b[9] = b[9] - b[8] - b[5] - b[6];  // I出现在EIGHT,FIVE,SIX中
        
        // 按顺序输出结果
        while(b[8]--) printf("0");  // EIGHT -> 0
        while(b[9]--) printf("1");  // NINE -> 1
        while(b[0]--) printf("2");  // ZERO -> 2
        while(b[1]--) printf("3");  // ONE -> 3
        while(b[2]--) printf("4");  // TWO -> 4
        while(b[3]--) printf("5");  // THREE -> 5
        while(b[4]--) printf("6");  // FOUR -> 6
        while(b[5]--) printf("7");  // FIVE -> 7
        while(b[6]--) printf("8");  // SIX -> 8
        while(b[7]--) printf("9");  // SEVEN -> 9
        printf("\n");
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        while(n-- > 0) {
            String str = sc.next();
            int[] b = new int[10];
            
            // 统计关键字母出现次数
            for(char c : str.toCharArray()) {
                if(c == 'Z') b[0]++;
                if(c == 'O') b[1]++;
                if(c == 'W') b[2]++;
                if(c == 'H') b[3]++;
                if(c == 'U') b[4]++;
                if(c == 'F') b[5]++;
                if(c == 'X') b[6]++;
                if(c == 'S') b[7]++;
                if(c == 'G') b[8]++;
                if(c == 'I') b[9]++;
            }
            
            // 处理重复字母
            b[1] -= b[0] + b[2] + b[4];
            b[3] -= b[8];
            b[5] -= b[4];
            b[7] -= b[6];
            b[9] -= b[8] + b[5] + b[6];
            
            // 构建结果
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < b[8]; i++) sb.append('0');
            for(int i = 0; i < b[9]; i++) sb.append('1');
            for(int i = 0; i < b[0]; i++) sb.append('2');
            for(int i = 0; i < b[1]; i++) sb.append('3');
            for(int i = 0; i < b[2]; i++) sb.append('4');
            for(int i = 0; i < b[3]; i++) sb.append('5');
            for(int i = 0; i < b[4]; i++) sb.append('6');
            for(int i = 0; i < b[5]; i++) sb.append('7');
            for(int i = 0; i < b[6]; i++) sb.append('8');
            for(int i = 0; i < b[7]; i++) sb.append('9');
            
            System.out.println(sb.toString());
        }
    }
}

def solve(s: str) -> str:
    # 初始化计数数组
    b = [0] * 10
    
    # 统计关键字母出现次数
    for c in s:
        if c == 'Z': b[0] += 1      # ZERO -> 2
        elif c == 'O': b[1] += 1    # ONE -> 3
        elif c == 'W': b[2] += 1    # TWO -> 4
        elif c == 'H': b[3] += 1    # THREE -> 5
        elif c == 'U': b[4] += 1    # FOUR -> 6
        elif c == 'F': b[5] += 1    # FIVE -> 7
        elif c == 'X': b[6] += 1    # SIX -> 8
        elif c == 'S': b[7] += 1    # SEVEN -> 9
        elif c == 'G': b[8] += 1    # EIGHT -> 0
        elif c == 'I': b[9] += 1    # NINE -> 1
    
    # 处理重复字母
    b[1] = b[1] - b[0] - b[2] - b[4]
    b[3] = b[3] - b[8]
    b[5] = b[5] - b[4]
    b[7] = b[7] - b[6]
    b[9] = b[9] - b[8] - b[5] - b[6]
    
    # 构建结果
    result = '0' * b[8] + '1' * b[9] + '2' * b[0] + '3' * b[1] + \
             '4' * b[2] + '5' * b[3] + '6' * b[4] + '7' * b[5] + \
             '8' * b[6] + '9' * b[7]
    
    return result

def main():
    n = int(input())
    for _ in range(n):
        s = input()
        print(solve(s))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心 + 计数
  • 时间复杂度： - 为字符串长度
  • 空间复杂度： - 只需要固定大小的数组