开发者社区> 嗯哼9925> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

LeetCode:Roman to Integer,Integer to Roman

简介:
+关注继续查看

首先简单介绍一下罗马数字,一下摘自维基百科

罗马数字共有7个,即I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”,与进位制无关。一般认为罗马数字只用来记数,而不作演算。

  • 重复数次:一个罗马数字重复几次,就表示这个数的几倍。
  • 右加左减:
    • 在较大的罗马数字的右边记上较小的罗马数字,表示大数字加小数字。
    • 在较大的罗马数字的左边记上较小的罗马数字,表示大数字减小数字。
    • 左减的数字有限制,仅限于I、X、C。比如45不可以写成VL,只能是XLV
    • 但是,左减时不可跨越一个位数。比如,99不可以用IC(100 - 1)表示,而是用XCIX([100 - 10] + [10 - 1])表示。(等同于阿拉伯数字每位数字分别表示。)
    • 左减数字必须为一位,比如8写成VIII,而非IIX。
    • 右加数字不可连续超过三位,比如14写成XIV,而非XIIII。(见下方“数码限制”一项。)
  • 加线乘千:
    • 在罗马数字的上方加上一条横线或者加上下标的Ⅿ,表示将这个数乘以1000,即是原数的1000倍。
    • 同理,如果上方有两条横线,即是原数的1000000(1000^{2})倍。
  • 数码限制:
    • 同一数码最多只能出现三次,如40不可表示为XXXX,而要表示为XL。
    • 例外:由于IV是古罗马神话主神朱庇特(即IVPITER,古罗马字母里没有J和U)的首字,因此有时用IIII代替IV。

Roman to Integer

Given a roman numeral, convert it to an integer.

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

 

 

3999范围内的罗马数字不会用到加上划线的字母

从最后一个字符开始,如果当前字符对应的数字比上一个数字小,那么就把结果减去当前字符对应的数字,否则加上当前字符对应数字。为了处理边界情况,在原字符串最后添加一个字符,该字符是原来的尾字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int romanToInt(string s) {
        int map[26];
        map['I'-'A'] = 1; map['V'-'A'] = 5; map['X'-'A'] = 10; map['L'-'A'] = 50;
        map['C'-'A'] = 100; map['D'-'A'] = 500; map['M'-'A'] = 1000;
        int res = 0, n = s.size();
        s.push_back(s[n-1]);
        for(int i = 0; i < n; i++)
        {
            if(map[s[i]-'A'] >= map[s[i+1]-'A'])
                res += map[s[i]-'A'];
            else res -= map[s[i]-'A'];
        }
        return res;
    }
};

 


Integer to Roman

Given an integer, convert it to a roman numeral.

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

我们注意到罗马数字的字母是有规律的,可以分成几组,I(1), V(5) 是一组, X(10), L(50)是一组, C(100), D(500)是一组, M(1000), d(应该是D加一个上划线,表示5000) 是一组 ……。后一组的两个数是前一组的10倍。

对于大于10的整数,我们把该整数逐位表示成罗马数字。                                    本文地址

个位上的数字1~9的分别为: I II III IV V VI VII VIII IX

十位上的数字1~9,只要把原来个位上的I 替换成 X, V 替换成L,X替换成C,即十位上的1~9表示的是10~90.

百位、千位以此类推。。。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string intToRoman(int num) {
        char romanChar[] = {'I','V','X','L','C','D','M'};
        string res;
        int i = 6, factor = 1000;
        while(num != 0)
        {
            helper(num / factor, &romanChar[i], res);
            i -= 2;
            num %= factor;
            factor /= 10;
        }
        return res;
    }
     
    void helper(int k, char romanChar[], string &res)
    {// 0 <= k <= 9
        if(k <= 0);
        else if(k <= 3)
            res.append(k, romanChar[0]);
        else if(k == 4)
        {
            res.push_back(romanChar[0]);
            res.push_back(romanChar[1]);
        }
        else if(k <= 8)
        {
            res.push_back(romanChar[1]);
            res.append(k-5, romanChar[0]);
        }
        else if(k == 9)
        {
            res.push_back(romanChar[0]);
            res.push_back(romanChar[2]);
        }
    }
};

 






本文转自tenos博客园博客,原文链接:http://www.cnblogs.com/TenosDoIt/p/3793503.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
[LeetCode]--12. Integer to Roman
[LeetCode]–13. Roman to Integer 可以在上面的链接看一下罗马数字的排列规律。然后利用规律,构建数组,把基本的构建数放在数组里面,然后依次判断加进去就行。 public class Solution { public String intToRoman(int num) { String[][] roman = {
944 0
[LeetCode]--13. Roman to Integer
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. 先来科普一波罗马数字吧。 大约在两千五百年前,罗马人还处在文化发展的初期,当时他们用手指作为计算工具.为了表示一、二、三、四个物体,就分别伸出一、二、三、四
1026 0
LeetCode - 13. Roman to Integer
13. Roman to Integer Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个字符串,代表罗马数字,将其转换为int型数字.
639 0
LeetCode - 12. Integer to Roman
12. Integer to Roman  Problem's Link  ---------------------------------------------------------------------------- Mean:  将一个int型的整数转化为罗马数字.
728 0
Roman to Integer
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.   首先简单介绍一下罗马数字,一下摘自维基百科 罗马数字共有7个,即I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。
638 0
Integer to Roman
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. Question: Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. 给你一个整数,把它转化为罗马数字,输入保证在1到3999之间。
616 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载