[LeetCode] Reconstruct Original Digits from English 从英文中重建数字-阿里云开发者社区

开发者社区> 李博 bluemind> 正文

[LeetCode] Reconstruct Original Digits from English 从英文中重建数字

简介:
+关注继续查看

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

  1. Input contains only lowercase English letters.
  2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
  3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"
Output: "012"

Example 2:

Input: "fviefuro"
Output: "45"

这道题给了我们一串英文字符串,是由表示数字的英文单词组成的,不过字符顺序是打乱的,让我们重建出数字。那么这道题的思路是先要统计出各个字符出现的次数,然后算出每个单词出现的次数,然后就可以重建了。由于题目中限定了输入的字符串一定是有效的,那么不会出现无法成功重建的情况,这里需要用个trick。我们仔细观察这些表示数字的单词"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",我们可以发现有些的单词的字符是独一无二的,比如z,只出现在zero中,还有w,u,x,g这四个单词,分别只出现在two,four,six,eight中,那么这五个数字的个数就可以被确定了,由于含有o的单词有zero,two,four,one,其中前三个都被确定了,那么one的个数也就知道了;由于含有h的单词有eight,three,其中eight个数已知,那么three的个数就知道了;由于含有f的单词有four,five,其中four个数已知,那么five的个数就知道了;由于含有s的单词有six,seven,其中six个数已知,那么seven的个数就知道了;由于含有i的单词有six,eight,five,nine,其中前三个都被确定了,那么nine的个数就知道了,知道了这些问题就变的容易多了,我们按这个顺序"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"就能找出所有的个数了,参见代码如下:

解法一:

class Solution {
public:
    string originalDigits(string s) {
        string res = "";
        vector<string> words{"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"};
        vector<int> nums{0, 2, 4, 6, 8, 1, 3, 5, 7, 9}, counts(26, 0);
        vector<char> chars{'z', 'w', 'u', 'x', 'g', 'o', 'h', 'f', 's', 'i'};
        for (char c : s) ++counts[c - 'a'];
        for (int i = 0; i < 10; ++i) {
            int cnt = counts[chars[i] - 'a'];
            for (int j = 0; j < words[i].size(); ++j) {
                counts[words[i][j] - 'a'] -= cnt;
            }
            while (cnt--) res += (nums[i] + '0');
        }
        sort(res.begin(), res.end());
        return res;
    }
};

另外我们也可以用更加简洁易懂的方法来快速的找出各个数字的个数,参见代码如下:

解法二:

class Solution {
public:
    string originalDigits(string s) {
        string res = "";
        vector<int> counts(128, 0), nums(10, 0);
        for (char c : s) ++counts[c];
        nums[0] = counts['z'];
        nums[2] = counts['w'];
        nums[4] = counts['u'];
        nums[6] = counts['x'];
        nums[8] = counts['g'];
        nums[1] = counts['o'] - nums[0] - nums[2] - nums[4];
        nums[3] = counts['h'] - nums[8];
        nums[5] = counts['f'] - nums[4];
        nums[7] = counts['s'] - nums[6];
        nums[9] = counts['i'] - nums[6] - nums[8] - nums[5];
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < nums[i]; ++j) {
                res += (i + '0');
            }
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:从英文中重建数字[LeetCode] Reconstruct Original Digits from English ,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10092 0
EasyUI表单验证,自定义插件验证,自定义js插件验证,远程验证,常见手机号,中英文,qq等验证规则验证
  {                       field : 'startPort',                       title : "起始端口",                       editor: "text",                       width : 50,                       editor: {    
1810 0
ASCII,Utf8,Unicode编码下的中英文字符大小
    一,测试Demo namespace 不同编码下的中英文字符大小 { class Program { static void Main(string[] args) { ShowCode()...
671 0
Word中插入英文格式的算法流程
  如图上部分所示,需要序号自动编号,那么插入一个一行一列的的表格,然后点击编号,使得项目自动编号,编号一个就在后面输入一些内容,按enter后第二行开始自动编号,如果要缩进,不能按Tab,Tab自动创建下一行,用两个空格。
3150 0
程序员必看--23种设计模式及解释(中英文对照)
转自:http://blog.csdn.net/yaolingrui/article/details/7338263 设计模式是每个程序员的必修课,这里将23种模式整理在一起,想学习这方面知识的朋友们有福了,呵呵。
936 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13893 0
C#语言之“中英文混合字符串对齐”的方法【转】
参考自:(1)http://www.cnblogs.com/cnluoke/articles/1213398.html            (2)http://www.cnblogs.com/sql4me/archive/2009/11/16/1603996.html 方法一:将已有字符串组织成新字符串时填充 由于某一个字段,包含有汉字和数字。
786 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7365 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
2107
文章
1103
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载