文档章节

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

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 9
博文 556
码字总数 321694
作品 0
海淀

暂无文章

HTTPS is easy

HTTPS is easy https://www.troyhunt.com/https-is-easy/ HTTPS is easy! In fact, it's so easy I decided to create 4 short videos around 5 minutes each to show people how to enable ......

openthings
18分钟前
0
0
bugList 2

用户端: 1. 上传文件时,当选择:彩色-A3-双面时,第二个图片有bug 应改为 和第一个图片的类型相同 2. 确认打印时,三个下拉选目前有bug 应改为:根据后台配置的商家,group by计算出不同城...

勇恒
21分钟前
2
0
keras cnn 网咯 mnist 分类

搭建貌似比tf是简单很多。。。。。 from keras.datasets import mnistfrom keras.utils import np_utilsfrom keras.models import Sequentialfrom keras.layers import Dense, Activat......

阿豪boy
23分钟前
0
0
解决 /var/run/nginx.pid failed

nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory) sudo nginx -c /etc/nginx/nginx.conf nginx -s reload...

驛路梨花醉美
25分钟前
0
0
nginx负载均衡-ssl原理-生成ssl密钥对-nginx配置ssl

nginx负载均衡: 1.创建配置文件 vim /usr/local/nginx/conf/vhost/load.conf #添加以下内容: upstream qq_com #名字自定义,借助此模块定义多个IP,后面...

ZHENG-JY
25分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部