[Leetcode] Roman to Integer and Integer to Roman 羅

wdzgege 發布于2019-08-14 12:28 / 1112人閱讀

摘要：正則表達式思路首先我們要熟悉羅馬數的表達方式。驗證字符串是否是羅馬數，我們先看一下有效的羅馬數是什么樣的，假設該數字小于，從千位到個位依次拆解。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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