罗马数字转整数
题目链接: https://leetcode.cn/problems/roman-to-integer
解题思路:
当小值在大值的左边,则减小值,如
IV=5-1=4
当小值在大值的右边,则加小值,如
VI=5+1=6
由上可知,右值永远为正,因此最后一位必然为正
从左往右遍历,如果当前值小于右边的值,则减去当前值,否则加上当前值
由于最后一位必然为正,因此最后一位必然会加上
复杂度分析
时间复杂度: 时间复杂度为 ,其中
n
是字符串s
的长度空间复杂度: 空间复杂度为 ,因为只需要常数级别的额外空间来存储映射表和一些变量
最后更新于