Roman to Integer
Roman to Integer
叶枫啦啦 发表于6个月前
Roman to Integer
  • 发表于 6个月前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

问题:

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;
    } 
}

共有 人打赏支持
粉丝 0
博文 253
码字总数 122876
×
叶枫啦啦
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: