力扣leetCode 13 罗马数字问题 代码算法详解 [C++实现]

leetCode 13 罗马数字求解

目录

• • leetCode 13 罗马数字求解
  • • 题目描述
    • 题解
    • 解释①

题目描述

现有罗马数字组合对应的表格

romanNum	arabicNum
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

不同的罗马数字代表不同的阿拉伯数字，而且罗马数字不同的排列也可以表示不同的阿拉伯数字，例如

Input: s = "III"
Output: 3
Explanation: III = 3
---
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4

题解

从例子中我们可以看出来罗马数字的排列如果是按顺序排列的，优先级低的排在前面的需要被后面的数字减掉，例如IVV，I的优先级比V小，所以要进行 V - I 的计算，而且IV自动成为一组，不再进行后面的运算。最后再用V - I + V，得出最后的Sum结果。

根据上述分析，这道题最重要的一个东西就是优先级，只有列出了输入romanNum每个罗马数字的优先级，我们才能够根据优先级进行加减运算。

优先级可以用数字表示，所以将罗马数字化成String类型后，其对应的位置例如romanNum[1] 就代表最低的优先级，以此类推，就解决了优先级的问题。

解决优先级后，需要对优先级进行分析，如果得到了一组优先级为“2641”的罗马数字，那么就需要进行用优先级为6的数字减去优先级为2的数字再分别加上优先级为4和1的数字，就得出了结果，所以我们还需要两个数组，一个存放优先级对应的阿拉伯数字的数组arabicNum[]，一个存放优先级序列的数组priority[]，这样就可以写出代码：

#include 
#include 
using namespace std;
string romanNum = "IVXLCDM"; // 将罗马数字存入string字符串中，以便通过下标查询
int arabicNum[] = { 1,5,10,50,100,500,1000 }; // 将罗马数字对应的阿拉伯数字存入数组中，以便通过下标和罗马数字对应   ★解释①
int priority[50]; // 存放优先级序列
int sum = 0; // 最后输出的结果
int romanNumChange(string s) {  
    int len = s.length();  
    int arabicLen = sizeof(arabicNum) / sizeof(*arabicNum);
    for (int i = 0; i < len; i++) {    // 遍历输入的罗马数字
        for (int j = 0; j < arabicLen; j++) { // 进入罗马数字字符串内开始对比
            if (s[i] == romanNum[j]) { // 罗马数字对应
                priority[i] = j;  // j是罗马数字在标准序列里的优先级 将优先级按顺序放入数组
            }
        }
    }
    int n = 0;
    while (n < len) {
        if (priority[n] < priority[n + 1]) {   // 如果下一个的优先级大于当前优先级
            sum += arabicNum[priority[n + 1]] - arabicNum[priority[n]];  // 后面优先级对应的阿拉伯数字减去前面的
            n += 2; // 此时已经用掉了两个罗马字符 所以需要+2，从第三个开始求和
        }
        else {  
            sum += arabicNum[priority[n]];  // 如果当前优先级和下一个优先级相等或大于，那么就加起来即可
            n += 1; // 此时只用了一个罗马字符 所以只需+1
        }
    }
    return sum;
}

int main(void) {
    string s = "MCMXCIV";
    cout << "answer is: " << romanNumChange(s) << endl;
    return 0;
}

解释①

大多数时候，数组的大小可以从初始化器中推导出来，例如int array[] = {1,2,3}; array的长度就是3，但这不适用于作为类成员的数组，所以必须明确说明尺寸，例如int array[3] = {1,2,3}; 说明数组的长度.