Day8 罗马数字转整数

定一个罗马数字，将其转换成整数

https://leetcode-cn.com/problems/roman-to-integer/

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

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

示例1：

输入: "III"
输出: 3

示例2：

输入: "IV"
输出: 4

示例3：

输入: "IX"
输出: 9

示例4：

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5：

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

Java解法

思路：

1. 记录当前值，相等时 加入，遇到大值记作负值，遇到小值或末尾记作正值，但过程太过麻烦
2. 改用栈来实现
   • 当前位置char转换为int，放入栈中
   • 栈顶数字小于当前放入时，不断出栈并由结果减去，直到栈顶不小于当前放入或栈为空
   • 放完之后，出栈累加

package sj.shimmer.algorithm;

import java.util.Stack;

/**
 * Created by SJ on 2021/2/1.
 */

class D8 {
    public static void main(String[] args) {
        System.out.println(romanToInt("III"));
        System.out.println(romanToInt("IV"));
        System.out.println(romanToInt("IX"));
        System.out.println(romanToInt("LVIII"));
        System.out.println(romanToInt("MCMXCIV"));
    }

    public static int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(getNum(s.charAt(0)));
        int i = 1;
        int result = 0;

        while (i<s.length()){
            int num = getNum(s.charAt(i));
            if (num <=stack.peek()) {
                stack.push(num);
            }else {
                result -=stack.pop();
                while (!stack.isEmpty()&&num >stack.peek()) {
                    result -=stack.pop();
                }
                stack.push(num);
            }
            i++;
        }
        while (!stack.isEmpty()) {
            result +=stack.pop();
        }
        return result;
    }

    private static int getNum(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;
        }
        return 0;
    }
}

image

精选解

1. 将相同的值视为同一个位置的数，将结果进行累加==》sum

2. 比较下一个位置的数，若大于，则sum计入结果为负值，若小于为正值，下一个位置为空也为正值

       public static int romanToInt1(String s) {
           if (s == null || s.length() == 0) {
               return 0;
           }
   
           int preNum = getNum(s.charAt(0));
           int result = 0;
           for (int i = 1; i < s.length(); i++) {
               int num = getNum(s.charAt(i));
               if (num>preNum) {
                   result -= preNum;//上一位置为负值
               }else {
                   result +=preNum;
               }
           }
           result +=preNum;//最后一位必为正值
           return result;
       }
   

   但这种解法没考虑 8 用IIX表示的情况，这里也是对罗马表示法的不熟悉之处吧，左减右加规则中，左减只会是一位吗？