关于SegmentFault:13-罗马数字转整数leetcodeC语言

思路：
遍历字符串，比拟以后罗马字符与后一个罗马字符对应的十进制数字的大小。
如果大于，则将该数字累加到 num，如果小于，则求出他们的差值，并将其累加到 num。
遍历完结，将 num 返回即可。

第一版、没有应用哈希表，应用数组模仿

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int getIndex(char *str, char c) 
{
  int k = 0;
  while (str[k] != '\0')
  {if (str[k] == c) 
    {return k;}
    k++;
  }
  return -1;
}

int romanToInt(char *str)
{int numArr[] = {1000, 500, 100, 50, 10, 5, 1};
  char roman[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
  int k = 0;
  int num = 0;
  while (str[k] != '\0') {int indexCurt = getIndex(roman, str[k]);
    // 判断下一个字符是否是空字符，避免字符串越界
    // 如果是空字符，就将其下标与前一个字符的下标置为一样
    int indexNext = str[k + 1] != '\0' ? getIndex(roman, str[k + 1]) : indexCurt;
    if (numArr[indexCurt] < numArr[indexNext])
    {num += numArr[indexNext] - numArr[indexCurt];
      k += 2;
    } else {num += numArr[indexCurt];
      k++;
    }
  }
  return num;
}

int main(void) {
  char *str = "MCMXCIV";
  printf("%d\n", romanToInt(str));
}

工夫复杂度：O(1)
空间复杂度：O(1)

办法二、将罗马数字与十进制数字作为键值对存储在哈希表中，而后其余步骤和办法一一样。

js 实现

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let intRoman = {
        "M": 1000,
        "D": 500,
        "C": 100,
        "L": 50,
        "X": 10,
        "V": 5,
        "I": 1
    };
    let len = s.length;
    let i = 0; 
    let num = 0;
    while (i < len) {if (intRoman[s[i]] < intRoman[s[i + 1]]) {num += intRoman[s[i + 1]] - intRoman[s[i]];
            i += 2;
        } else {num += intRoman[s[i]];
            i++;
        }
    }
    return num;
};