13. Roman to Integer

题目

题意分析

本题是要将罗马数字转换成对应的整数。

本题考点

无

解法I - 直接相加

我们依次遍历字母，记下上一次的字母的值，若上一次的字母的值比本次字母小，则做减法，否则做加法。

注意，因为在上一轮我们已经加过一次上一次的值了，做减法的时候需要减去两倍的上一次的值把上一次的值给扣除。

实现

class Solution {
  public int romanToInt(String s) {
    int sum = 0;

    // 上一次的字母
    Character last = null;

    for (int i = 0; i < s.length(); i++) {
      Character c = s.charAt(i);
      
      int currentValue = getRomanValue(c);
      int lastValue = getRomanValue(last);
      
      // 如果本次的值大于上次的值，说明我们要做减法
      // 在这里需要把上一次添加的值给减去
      if (currentValue > lastValue) {
        sum = sum - 2 * lastValue + currentValue;
      } else {
        // 如果本次的值小于等于上次的值，则直接相加
        sum += currentValue;
      }

      // 更新上一次的值
      last = c;
    }

    return sum;
  }

  private int getRomanValue(Character c) {
    if (c == null) return Integer.MAX_VALUE;
    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;
      default:
      return 0;
    }
  }
}

解法II - 优化

在解法I中，我们在遇到减法时，每次都需要减去2倍的上一次的值，多做了一次加法。

我们这次将通过判断，直接进行相加（减），减少一步加法操作。

实现

class Solution {
  public int romanToInt(String s) {
    // 初始值为最后一个字母的值
    // 因为下面的循环无法覆盖到最后一个字母
    int sum = getRomanValue(s.charAt(s.length() - 1));

    // 注意边界条件i < s.length() - 1，防止越界
    for(int i = 0; i < s.length() - 1; i ++) {
      // 我们每次取两个字母进行判断
      Character currentLetter = s.charAt(i);
      Character nextLetter = s.charAt(i + 1);
      
      int currentValue = getRomanValue(currentLetter);
      int nextValue = getRomanValue(nextLetter);
      
      if (currentValue >= nextValue) {
        sum += currentValue;
      } else {
        sum -= currentValue;
      }
    }

    return sum;
  }

  private int getRomanValue(Character c) {
    if (c == null) return Integer.MAX_VALUE;
    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;
      default:
      return 0;
    }
  }
}