文档章节

Roman to Integer

叶枫啦啦
 叶枫啦啦
发布于 2017/06/27 16:06
字数 548
阅读 0
收藏 0
点赞 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;
    } 
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 3
博文 540
码字总数 260604
作品 0
海淀

暂无相关文章

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 昨天 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部