[Leetcode] Roman to Integer and Integer to Roman 罗

wdzgege 发布于2019-08-14 12:28 / 1111人阅读

摘要：正则表达式思路首先我们要熟悉罗马数的表达方式。验证字符串是否是罗马数，我们先看一下有效的罗马数是什么样的，假设该数字小于，从千位到个位依次拆解。

Valid Roman Numeral 正则表达式 思路

首先我们要熟悉罗马数的表达方式。M是1000，D是500，C是100，L是50，X是10，V是5，I是1。验证字符串是否是罗马数，我们先看一下有效的罗马数是什么样的，假设该数字小于5000，从千位到个位依次拆解。
千位的表达方式 M{0,4}

MMMM      4000
MMM       3000
MM        2000
M         1000

百位的表达方式 (CM|CD|D?C{0,3})

CM        900
DCCC      800
DCC       700
DC        600
D         500
CD        400
CCC       300
CC        200
C         100

十位的表达方式 (XC|XL|L?X{0,3})

XC        90
LXXX      80
LXX       70
LX        60
L         50
XL        40
XXX       30
XX        20
X         10

个位的表达方式 (IX|IV|V?I{0,3})

IX        9
VIII      8
VII       7
VI        6
V         5
IV        4
III       3
II        2
I         1

所以我们正则表达式的就是将这四个部分顺序组合在一起就行了。

注意

罗马数字没有0

正则表达式以^开头，以$结尾

代码

public boolean isRoman(){
    if(s.matches("^M{0,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$")) return true;
    return false;
}

Roman to Integer 减大加小法 复杂度

时间 O(N) 空间 O(1)

思路

如果我们通过Valid Roman Numeral确定了一个字符串是罗马数字后，我们就可以用一个非常简单的技巧来计算罗马数字的值，而不用考虑那些非法情况。我们知道罗马数字中较小的字母在较大的字母之前意味着较大的字母减去较小的字母，而较小的字母在较大的字母之后意味着较大的字母加上较小的字母。而且这种前面最多只有1个较小字母。所以我们只要在遍历的过程中记住该字母的上一个就行了。如果该字母比上一个小，说明可以直接加上。如果该字母比上一个大，说明正确的值应该是该字母减去上一个字母，而我们之前已经加上了上一个字母，所以我们要减去两倍的上一个字母，然后再加上当前字母。

代码

public class Solution {
    public int romanToInt(String s) {
        int total = charToInt(s.charAt(0));
        for(int i = 1; i < s.length(); i++){
            int prev = charToInt(s.charAt(i-1));
            int curr = charToInt(s.charAt(i));
            if(curr <= prev){
                total += curr;
            } else {
                total = total - 2 * prev + curr;
            }
        }
        return total;
    }

    public int charToInt(char c) {
        int data = 0;

        switch (c) {
            case "I":
                data = 1;
                break;
            case "V":
                data = 5;
                break;
            case "X":
                data = 10;
                break;
            case "L":
                data = 50;
                break;
            case "C":
                data = 100;
                break;
            case "D":
                data = 500;
                break;
            case "M":
                data = 1000;
                break;
        }

        return data;
    }
}

Integer to Roman 贪心法 复杂度

时间 O(N) 空间 O(1)

思路

因为罗马数字都是由最大化的表示，比如10会表示成X而不是VV，所以我们可以从最大可能的表示向小的依次尝试。因为提示1-3999，所有的可能性不多，我们可以直接打表来帮助我们选择表示方法。在一个数量级中有四种可能的表示方法，以1-9为例，1-3是由I表示出来的，4是IV，5是V，6-8是V和若干个I，9是IX。

代码

public class Solution {
    public String intToRoman(int num) {
        String[] symbol = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] value = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        StringBuilder res = new StringBuilder();
        int i = 0;
        while(num>0){
            if(num>=value[i]){
                res.append(symbol[i]);
                num -= value[i];
            } else {
                i++;
            }
        }
        return res.toString();
    }
}

云服务器 GPU云服务器 roman integer integer类型 reverse-integer

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64492.html

【LeetCode Easy】013 Roman to Integer

摘要：将罗马字母的字符串转换为代表的整数这题不难，用一个存罗马数字和具体数字的对应关系，然后遍历前后两两比较，该加加，该减减时间复杂度这里是自己写的一个方法，里面用一个，相当于存对应当时一直想着用一个来存减的值，所以没法用就用了指针，但其实就 Easy 013 Roman to Integer Description: 将罗马字母的字符串转换为代表的整数Roman numerals are ...

wizChen 2019-08-16 16:54 评论0 收藏0
LeetCode13 - Roman to Integer

摘要：解题思路罗马数字是符号和加操作的一个组合。他基于以下七个符号。组合规则基本数字中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个放在大数的左边只能用一个。想更一进步的支持我，请扫描下方的二维码，你懂的 Given a roman numeral, convert it to an integer. Input is guaranteed to be...

elisa.yang 2019-08-14 12:10 评论0 收藏0
leetcode 12 Integer to Roman

摘要：题目详情题目的意思是输入一个阿拉伯数字，我们需要输出这个数字的罗马数字表示形式字符串。想法这道题最重要的点就是理解罗马数和阿拉伯数之间的转换规律。题目详情 Given an integer, convert it to a roman numeral.Input is guaranteed to be within the range from 1 to 3999.题目的意思是：输...

wqj97 2019-08-15 14:35 评论0 收藏0
Leetcode12 Integer to Roman

摘要：解题思路其中每两个阶段的之间有一个减法的表示，比如，写在前面表示。所以映射关系应该是然后就是贪心的做法，每次选择能表示的最大值，把对应的字符串连起来。 Roman to Integer Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range fro...

CoorChice 2019-08-14 12:10 评论0 收藏0
Leetcode PHP题解--D82 13. Roman to Integer

摘要：题目链接题目分析将给定的罗马数字转换成阿拉伯数字。要注意，先替换连续出现的那些。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D82 13. Roman to Integer 题目链接 13. Roman to Integer 题目分析将给定的罗马数字转换成阿拉伯数字。思路用替换法。要注意，先替换连续出现的那些。例如，比先替换I，要先替换III。最终代码

CODING 2019-07-01 13:57 评论0 收藏0