[力扣_13] 罗马数字转整数

题目入口：点击进入

相关算法：

• 横向搜索——时间复杂度O(n)，空间复杂度——O(1)
• Hash表——时间复杂度O(n)，空间复杂度——O(1)

这题是上一道题的变形，而在这题里我们不需要涉及字符串的拼接，所以使用的空间复杂度为O(1)

Hash表

其实C使用Hash是真的操蛋，这边用的hash函数依旧是对整长度求余，我们从题意中可以知道，罗马数字有十三种组合，下面放上"花花酱"的教学视频：

解题思路如下所示：

• 首先利用hash函数将所有可能的字符串组合存入hash表中
• 然后遍历字符串，这儿需要注意优先判断在当前字符的下一个字符是否为特殊组合中的一种
• 将遍历的字符串对应key到hash中取出val
• 最后逐步相加val，知道字符串遍历结束即可。

代码如下所示：

typedef struct HashData
{
    int val;
    char key[3];
}HashData;

typedef struct HashNode
{
    HashData data;
    struct HashNode* next;
}HashNode;

typedef struct HashMap
{
    HashNode** L;
    int size;
}HashMap;

void PutHashMap(HashMap Map, char* key, int val)
{
    if (Map.L[key[0] % Map.size] == NULL)
    {
        Map.L[key[0] % Map.size] = (HashNode*)malloc(sizeof(HashNode));
        Map.L[key[0] % Map.size]->data.val = val;
        int i=0;
        for (; key[i] != '\0'; i++)
            Map.L[key[0] % Map.size]->data.key[i] = key[i];
            Map.L[key[0] % Map.size]->data.key[i] = '\0'; 
        Map.L[key[0] % Map.size]->next = NULL;
    }
    else
    {
        HashNode* p = Map.L[key[0] % Map.size];
        while (p->next != NULL) p = p->next;
        p->next = (HashNode*)malloc(sizeof(HashNode));
        p->next->data.val = val;
        int i=0;
        while(key[i] != '\0'){ 
        p->next->data.key[i] = key[i];
        i++;
        }
        p->next->data.key[i]='\0';
        p = p->next;
        p->next = NULL;
    }
}
int FindHashMap(HashMap Map, char* key)
{
    HashNode* p = Map.L[key[0] % Map.size];
    while (p)
    {
      if (!strcmp(p->data.key, key)) break;
      p = p->next;
    }
    return p->data.val;
}
int romanToInt(char *s) {

    HashMap Map;
        if (!s) return 0;
        int sleng = strlen(s);
        Map.size = 13;
        Map.L = (HashNode**)malloc(sizeof(HashNode*) * Map.size);
    for (int i = 0; i < Map.size; i++) Map.L[i] = NULL;
    PutHashMap(Map, "I", 1);
    PutHashMap(Map, "V", 5);
    PutHashMap(Map, "X", 10);
    PutHashMap(Map, "L", 50);
    PutHashMap(Map, "C", 100);
    PutHashMap(Map, "D", 500);
    PutHashMap(Map, "M", 1000);
    PutHashMap(Map, "IV", 4);
    PutHashMap(Map, "IX", 9);
    PutHashMap(Map, "XL", 40);
    PutHashMap(Map, "XC", 90);
    PutHashMap(Map, "CD", 400);
    PutHashMap(Map, "CM", 900);

    char s1[3];int ReturnNum = 0;
    for (int i = 0; i < sleng; i++)
    {
        int j = 0;
        s1[j] = s[i];
        s1[j + 1] = '\0';
        if (i + 1 < sleng && (s[i] == 'I' || s[i] == 'X' || s[i] == 'C'))
        {
            if (s[i] == 'I' && (s[i + 1] == 'V' || s[i + 1] == 'X'))
            {
                j++; i++;
                s1[j] = s[i];
                s1[j + 1] = '\0';
            }
            else if (s[i] == 'X' && (s[i + 1] == 'L' || s[i + 1] == 'C'))
            {
                j++; i++;
                s1[j] = s[i];
                s1[j + 1] = '\0';
            }
            else if (s[i] == 'C' && (s[i + 1] == 'D' || s[i + 1] == 'M'))
            {
                j++; i++;
                s1[j] = s[i];
                s1[j + 1] = '\0';
            }
        }

        ReturnNum += FindHashMap(Map, s1);
    }
    return ReturnNum;
}

横向扫描

上面那种在C语言中，恕我知识储备量不够，无法构造出合适的hashmap，所以时间复杂度很高

则暴力用 switch判断，直接横向扫描，则会好很多，下面给出思路和代码：

• 遍历串s，通过当前字符去相加对应的值
• 同时判断下一个字符是否为特殊情况，若为特殊情况，则对应做减法运算

代码如下所示：

int romanToInt(char * s){
    int num=0;
for(int i=0;i<strlen(s);i++)
{
    switch(s[i])
    {
        case 'I' :num=num+1;if(s[i+1]=='V'||s[i+1]=='X'){num=num-2;}break;
        case 'V' :num=num+5;break;
        case 'X' :num=num+10;if(s[i+1]=='L'||s[i+1]=='C'){num=num-20;}break;
        case 'L' :num=num+50;break;
        case 'C' :num=num+100;if(s[i+1]=='D'||s[i+1]=='M'){num=num-200;}break;
        case 'D' :num=num+500;break;
        default:num=num+1000;break;
    }

}
   return num;
}

本文链接：