欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Reconstruct Original Digits from English

程序员文章站 2022-04-24 14:06:43
...

Reconstruct Original Digits from English

1. 解析 

题目大意,英文形式的数字被表示成无序的字符串,将其还原,并按照从小到大的顺序返回。

2. 分析

个人感觉这道题出的还是蛮不错。思路我想到了,但代码是参考@Grandyang博客写的,大家可以去看一下,写的很清晰。如果我们数字的字符串表示形式,就会发现,某个特定的字符只会出现在一个数字当中。在"zero",  "one", "two",  "three", "four", "five", "six", "seven", "eight", "nine"中,"zero", "two", "four", "six", "eight"只出现过一次的字符分别为:'z'、'w'、'u'、'x'、'g',即这几个数是可以确定的。出现过'o'的"zero", "two", "four"和"one",前面的3个"zero", "two", "four"可以确定,所以也就可以确定"one";出现过't'的有"two"和"three","two"可以确定了,所以"three"也可以确定;出现过'f'的有"four"和"five","four"可以确定了,所以"five"也可以确定;出现过's的有"six"和"seven","six"可以确定了,所以"seven"也可以确定;最后根据'i'也可以确定"nine"。详见代码,还是很不错的一道题。注意,特定字符chars中存储的顺序不能随意排列,因为涉及到先后的问题

class Solution {
public:
    string originalDigits(string s) {
        string res = "";
        
        vector<string> digit{"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"};
        vector<int> count(26, 0);
        vector<char> chars{'z', 'w', 'u', 'x', 'g', 'o', 't', 'f', 's', 'i'};
        vector<char> c_digit{'0', '2', '4', '6', '8', '1', '3', '5', '7', '9'};
        for (char ch : s) count[ch-'a']++; //统计字母出现的次数
        for (int i = 0; i < 10; ++i){
            int cnt = count[chars[i]-'a']; //获取相应数字的次数
            for (char ch : digit[i]) count[ch - 'a'] -= cnt;            
            while (cnt--) res += c_digit[i];
        }
        sort(res.begin(), res.end());
        return res;
    }
};

 [1]https://www.cnblogs.com/grandyang/p/5996239.html

相关标签: # 细节算法