文档章节

罗马数字转换为整数 Roman to Integer

叶枫啦啦
 叶枫啦啦
发布于 2017/06/27 16:06
字数 606
阅读 0
收藏 0

问题:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

解决:

【注--罗马数字--->阿拉伯数字规则】

基本字符:

  I、V、X、L、C、D、M

  相应的阿拉伯数字表示为:

  1.5、10、50、100、500、1000

  (1)相同的数字连写,所表示的数等于这些数字相加得到的数,如:Ⅲ = 3;

  (2)小的数字在大的数字的右边,所表示的数等于这些数字相加得到的数, 如:Ⅷ = 8;Ⅻ = 12;

  (3)小的数字,(限于Ⅰ、X 和C)在大的数字的左边,所表示的数等于大数减小数得到的数,如:Ⅳ= 4;Ⅸ= 9;

  (4)正常使用时连写的数字重复不得超过三次。(表盘上的四点钟--“IIII”,例外。)

  (5)在一个数的上面画一条横线,表示这个数增值1000 倍。

① 使用map保存转换后的每一位数,比较第 i 个位置与第 i+1个位置的数的大小,根据规则加上或减去对应的数即可。耗时100ms.

public class Solution{
    public static int romanToInt(String s) {
        if (s == null || s.length() == 0)
            return -1;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int len = s.length();
        int result = map.get(s.charAt(len - 1));
        for (int i = len - 2; i >= 0; i--) {
            if (map.get(s.charAt(i)) >= map.get(s.charAt(i + 1)))
                result += map.get(s.charAt(i));
            else
                result -= map.get(s.charAt(i));
        }

        return result;
    }
}

② 使用hash table保存对应的阿拉伯数字,若 i 大于 i+1上的数,就减2次,否则加上。耗时104ms。

public class Solution{
    public static int romanToInt(String s) {
        int hash[] = new int[26];
        hash['I' - 'A'] = 1;
        hash['V' - 'A'] = 5;
        hash['X' - 'A'] = 10;
        hash['L' - 'A'] = 50;
        hash['C' - 'A'] = 100;
        hash['D' - 'A'] = 500;
        hash['M' - 'A'] = 1000;
        char prev ='A';
        int res = 0;
        for (char c : s.toCharArray()) {
            if (hash[c - 'A'] > hash[prev - 'A']) {
                res -= 2 * hash[prev - 'A'];
            }
            res += hash[c - 'A'];
            prev = c;
        }

        return res;
    }
}

③ 使用hash table的简单易理解

class Solution {//93ms
    public int romanToInt(String s) {
        if(s == null || s.length() == 0) return 0;
        int[] hash = new int[26];
        hash['I' - 'A'] = 1;
        hash['V' - 'A'] = 5;
        hash['X' - 'A'] = 10;
        hash['L' - 'A'] = 50;
        hash['C' - 'A'] = 100;
        hash['D' - 'A'] = 500;
        hash['M' - 'A'] = 1000;
        int res = 0;
        for(int i = 0;i < s.length();i ++){
            res += hash[s.charAt(i) - 'A'];
            if(i > 0 && hash[s.charAt(i) - 'A'] > hash[s.charAt(i - 1) - 'A']){
                res -= 2 * hash[s.charAt(i - 1) - 'A'];
            }
        }
        return res;
    } 
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 12
博文 569
码字总数 354997
作品 0
海淀
私信 提问

暂无文章

Dubbo下一站:Apache顶级项目

导读: 近日,在Apache Dubbo开发者沙龙杭州站的活动中,阿里巴巴中间件技术专家曹胜利(展图)向开发者们分享了Dubbo2.7版本的规划。 本文将为你探秘 Dubbo 2.7背后的思考和实现方式。 作者:...

阿里云官方博客
13分钟前
1
0
量化策略构建:均值回归模型

“ 现在已然衰朽者,将来可能重放异彩。现在备受青睐者,将来却可能黯然失色。” 当事物发展严重偏离其均值时,均值会像万有引力一样令其回归。如果时间足够长,万物都终将回归于其均值。正所...

酒逢知己千杯少
15分钟前
2
0
从内部自用到对外服务,配置管理的演进和设计优化实践

本文整理自阿里巴巴中间件技术专家彦林在中国开源年会上的分享,通过此文,您将了解到: 微服务给配置管理所带来的变化 配置管理演进过程中的设计思考 配置管理开源后的新探索 配置中心控制台...

阿里云云栖社区
19分钟前
1
0
使用screen恢复会话时出现There is no screen to be resumed matching错误解决办法

有时在恢复 screen 时会出现 There is no screen to be resumed matching ******? 输入命令 :screen -d **** 然后再使用恢复命令恢复就可以了...

Alex142857
26分钟前
1
0
只到及格线?盘点科技公司遵循的数据伦理

在过去的一段时间中,数据泄露的新闻时有发生,这也引发了大众对于谁拥有我们的数据、我们的数据如何被使用和共享的关注。尽管在事情发生之后,很多科技公司都表态会以更好的方式来使用和保护...

技术阿飞
26分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部