【LeetCode笔记 - 每日一题】423. 从英文中重建数字（Java、字符串、偏思路）

【LeetCode笔记 - 每日一题】423. 从英文中重建数字（Java、字符串、偏思路）

文章目录

• • • 题目描述
    • 思路 && 代码

题目描述

• 看了题目以后想到啥？
  • 字符数量统计
  • 银行家算法逐个拆解
  • 建立数字 - 字符串的全局映射
    

思路 && 代码

• 抄答案了，采取了评论区三叶dalao的写法（不得不说，人家的处理写法是真的优雅），学习学习。

class Solution {
    static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", 
        "eight", "nine"};
    static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
    public String originalDigits(String s) { 
        // part 1： 字符数量统计
        int[] counts = new int[26];
        for(char c : s.toCharArray()) counts[c - 'a']++;

        // part 2：获取值（这里的嵌套循环处理很棒）
        StringBuilder sb = new StringBuilder();
        for(int i : priority) { // 按照"0, 8, 6, 3, 2, 7, 5, 9, 4, 1"的序列来
            int k = Integer.MAX_VALUE;
            for(char c : ss[i].toCharArray()) k = Math.min(k, counts[c - 'a']); // 获取当前最多的可行值
            for(char c : ss[i].toCharArray()) counts[c - 'a'] -= k; // 逐个减去可行值
            while(k-- > 0) sb.append(i); // 添加对应个数的 ans
        }

        // final: 排序、格式处理
        char[] cs = sb.toString().toCharArray();
        Arrays.sort(cs);
        return String.valueOf(cs);
    }
}

• 无注释版

class Solution {
    static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", 
        "eight", "nine"};
    static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
    public String originalDigits(String s) { 
        int[] counts = new int[26];
        for(char c : s.toCharArray()) counts[c - 'a']++;
        
        StringBuilder sb = new StringBuilder();
        for(int i : priority) { 
            int k = Integer.MAX_VALUE;
            for(char c : ss[i].toCharArray()) k = Math.min(k, counts[c - 'a']); 
            for(char c : ss[i].toCharArray()) counts[c - 'a'] -= k; 
            while(k-- > 0) sb.append(i); 
        }

        char[] cs = sb.toString().toCharArray();
        Arrays.sort(cs);
        return String.valueOf(cs);
    }
}