力扣(LeetCode)13. 罗马数字转整数(C++)
迪丽瓦拉
2024-01-31 20:32:12
0次
模拟
罗马数字和掰手指数数的区别在于，IV/IXIV/IXIV/IX 这类倒着数数的，和阿拉伯数字最大的区别在于 555 的 10k10^k10k 倍 k∈Nk\isin Nk∈N ，需要被表示出来。所以除了记录 I/X/C/MI/X/C/MI/X/C/M ——1/10/100/10001/10/100/10001/10/100/1000，还要记录 V/L/DV/L/DV/L/D——5/50/5005/50/5005/50/500 。 倒着数数的数字，其实是减去第一个数，加上第二个数。考虑 IV=−I+V=−1+5=4IV = -I+V=-1+5 = 4IV=−I+V=−1+5=4 。
代码展示
class Solution {
public:int romanToInt(string s) {unordered_map mp{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};int ans = 0;for(int i = 0;iif(i 时间复杂度 O(n)O(n)O(n) ， nnn 是 sss 的长度，加或减每一位所有罗马数字的时间复杂度 O(n)O(n)O(n)。
空间复杂度 O(∣C∣)O(|C|)O(∣C∣) ， 编码使用哈希表的空间复杂度 O(∣C∣)O(|C|)O(∣C∣) ， ∣C∣=7|C| = 7∣C∣=7 。
博主致语
理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。