罗马数字转数字

题目描述

罗马数包含以下七种字符

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。

但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字，输入确保在 1 到 3999 的范围内。

解题思路

将罗马数字在每个位置的所有可能的取值列出，例如对于个位有如下情况

"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"

以上字符分别对应 0-9，然后取出个位的数字，根据数字的大小选择对应的字符，接着取出十位上的数字，找到对应的字符，以此类推

import java.util.Stack;

public class Solution {
    public String intToRoman(int num) {
        // 列出每个位置的所有情况
        String[][] maps = new String[4][];
        maps[0] = new String[]{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        maps[1] = new String[]{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        maps[2] = new String[]{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        // 题目规定数字范围在 1-3999，所以这里列到 3000 即可
        maps[3] = new String[]{"", "M", "MM", "MMM"};

        StringBuilder stringBuilder = new StringBuilder();
        Stack<String> stack = new Stack();
        // 依次取出个位，十位 ...
        int index = 0;
        while (num != 0) {
            int n = num % 10;
            num /= 10;
            stack.push(maps[index][n]);
            index++;
        }

        while (!stack.isEmpty()) {
            stringBuilder.append(stack.pop());
        }

        return stringBuilder.toString();
    }
}

另一种思路是贪心法，想想我们是怎么找零钱的，每次都找面值最大的，我们找 154 元，我们首先找面值最大的 100 块，然后剩 54，接着找面值最大的 50，剩 4 元，找 4 个硬币。

如果我们把要转化的数字看做是要找的零钱，罗马数字就是对应的钞票，我们把罗马数字对应的钞票有多种情况列出来，然后按照找零钱的规则找钱即可

import java.util.Stack;

public class Solution {
    public String intToRoman(int num) {
        // 罗马"钞票"的面值大小依次排列
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] roma = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int index = 0;
        StringBuilder stringBuilder = new StringBuilder();
        while (num != 0) {
            // 使用目前最大的面值
            if (num >= nums[index]) {
                stringBuilder.append(roma[index]);
                num -= nums[index];
                continue;
            }
            index++;
        }

        return stringBuilder.toString();
    }
}

数字转罗马数字

题目描述

罗马数字与数字的转换规则如上题介绍，这道题的要求是将罗马数字转化为数字。

解题思路

如果还是将罗马数字看做钞票，将其转化为数字的过程，不就是相当于数钱吗！将钞票转化为对应的数值，然后加起来即可

public class Solution {
    public int romanToInt(String s) {
        // 为了处理方便，将两位的罗马数字转为一位的字符
        s = s.replace("IV", "a");
        s = s.replace("IX", "b");
        s = s.replace("XL", "c");
        s = s.replace("XC", "d");
        s = s.replace("CD", "e");
        s = s.replace("CM", "f");
        
        int sum = 0;
        // 将罗马数字对应的数值加起来即可
        for (char c: s.toCharArray()) {
            sum += romaToNum(c);
        }
        
        return sum;
    }
    
    // 罗马数字对应的数值
    private int romaToNum(char c) {
        switch (c) {
            case 'I' : return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            case 'a': return 4;
            case 'b': return 9;
            case 'c': return 40;
            case 'd': return 90;
            case 'e': return 400;
            case 'f': return 900;
            default: return 0;
        }
    }
}

还有一种编程的思路，与上面的贪心法一样，直接检查最大的钞票，然后一直加起来

public class Solution {
    public int romanToInt(String s) {
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] roma = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int index = 0;
        int sum = 0;
        while (!"".equals(s)) {
            // 依次查找开头的最大钞票，然后加起来
            if (s.startsWith(roma[index])) {
                sum += nums[index];
                s = s.substring(roma[index].length());
                continue;
            }
            index++;
        }
        return sum;
    }
}

参考文献