首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-13-Roman to Integer

leetcode-13-Roman to Integer

作者头像
chenjx85
发布2018-05-22 16:20:11
5140
发布2018-05-22 16:20:11
举报

题目描述:

Roman numerals are represented by seven different symbols: IVXLCD and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9. 
  • X can be placed before L (50) and C (100) to make 40 and 90. 
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

要完成的函数:

int romanToInt(string s)

说明:

1、这道题给定一个字符串s,要求将字符串中的罗马数字转化为阿拉伯数字(十进制)显示出来,I/V/X/L/C/D/M分别表示1/5/10/50/100/500/1000,除此之外,还定义了两条规则,如下:

大数字在左,小数字在右,比如VI表示6。

如果小数字在左,大数字在右,那么它们的组合结果是大数字减去小数字,如IV,表示5-1=4,IX=10-1=9,CM=1000-100=900。

2、明白了题意,我们可以逐个处理字符,如果该字符比下一个字符大或者相等,那么总数加上当前字符。

如果该字符比下一个字符小,那么总数减去当前字符。

代码如下:

    int romanToInt(string s) 
    {
        int sum=0,i=0,s1=s.size();
        vector<int>char2num={100,500,0,0,0,0,1,0,0,50,1000,0,0,0,0,0,0,0,0,5,0,10};//每个罗马字符减去67,作为index,得到的值就是相应的阿拉伯数字。
        while(i<s1-1)                                  //此处也可以使用map
        {
            if(char2num[s[i]-67]>=char2num[s[i+1]-67])
                sum+=char2num[s[i]-67];
            else
                sum-=char2num[s[i]-67];
            i++;
        }
        sum+=char2num[s[i]-67];//加上最后一个字符对应的阿拉伯数字
        return sum;
    }

上述代码实测116ms,beats 44.21% of cpp submissions。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-05-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档