文档章节

罗马数字转换为整数 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;
    } 
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 10
博文 565
码字总数 340658
作品 0
海淀

暂无文章

命令行新建Maven多项目

参考地址 # DgroupId 可以理解为包名# DartifactId 可以理解为项目名mvn archetype:generate -DgroupId=cn.modfun -DartifactId=scaffold -DarchetypeArtifactId=maven-archetype-quickst......

阿白
55分钟前
1
0
OSChina 周四乱弹 —— 上帝对我单身年限的惩罚越来越长了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @达尔文:分享张卫健的单曲《身体健康》 《身体健康》- 张卫健 手机党少年们想听歌,请使劲儿戳(这里) 昨天是重阳节咯, 可惜小小编辑总是晚...

小小编辑
57分钟前
10
0
django rest framework 外键序列化方法与问题总结

django rest framework 外键序列化方法与问题总结 当借口中需要出现一对多关系的时候,我们可以用rest_framwork的序列化功能来处理,代码如下. # models.pyfrom django.db import modelscl...

_Change_
昨天
3
0
SingleNumber136 leetCode

Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you im......

woshixin
昨天
3
0
String ,  StringBuffer ,  StringBuilder的区别

String , StringBuffer , StringBuilder的区别 String 首先,String 是用来表示一个字符串常量的,它是一个不可变对象,意味着,一旦我们创建了某个字符串之后,就不能再改变它的值了,我们可...

tsmyk0715
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部