【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)

本文主要是介绍【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 作者主页： 🔗进朱者赤的博客

• 精选专栏：🔗经典算法

• 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

• ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞
  ————————————————-

罗马数字转整数

• 标签(题目类型)：字符串处理、数学计算

题目描述

给定一个罗马数字字符串，将其转换成整数。输入确保在 1 到 3999 的范围内。

罗马数字由以下七个符号表示：I, V, X, L, C, D 和 M。这些符号对应的值分别是 1, 5, 10, 50, 100, 500 和 1000。例如，罗马数字 III 表示 3，IV 表示 4，IX 表示 9，LVIII 表示 58，如此类推。

注意，罗马数字的书写规则遵循从左到右的减法原则，例如 IV 表示 4，IX 表示 9，即从较大的数字中减去较小的数字来表示相应的数。但是也有特殊情况，例如 IV = V - I = 5 - 1 = 4，IX = X - I = 10 - 1 = 9，XL = L - X = 50 - 10 = 40，XC = C - X = 100 - 10 = 90，CD = D - C = 500 - 100 = 400，CM = M - C = 1000 - 100 = 900。

为了简化问题，我们只需要考虑这些基本的减法情况。

思路及实现

方式一：直接映射法

思路

• 创建一个映射表，将罗马数字的每个字符映射到其对应的整数值。
• 遍历输入的罗马数字字符串，对每个字符进行查找和转换。
• 对于特殊的减法情况，例如 IV, IX, XL, XC, CD, CM，需要进行额外的判断和处理。

Java版本

public class RomanToInt {public int romanToInt(String s) {Map<Character, Integer> romanValues = new HashMap<>();romanValues.put('I', 1);romanValues.put('V', 5);romanValues.put('X', 10);romanValues.put('L', 50);romanValues.put('C', 100);romanValues.put('D', 500);romanValues.put('M', 1000);int result = 0;int prevValue = 0;for (int i = s.length() - 1; i >= 0; i--) {int currentValue = romanValues.get(s.charAt(i));if (currentValue < prevValue) {result -= currentValue;} else {result += currentValue;}prevValue = currentValue;}return result;}
}

C语言版本

#include <stdio.h>
#include <string.h>int romanToInt(char * s){int romanValues[256] = {0};romanValues['I'] = 1;romanValues['V'] = 5;romanValues['X'] = 10;romanValues['L'] = 50;romanValues['C'] = 100;romanValues['D'] = 500;romanValues['M'] = 1000;int result = 0;int prevValue = 0;int length = strlen(s);for (int i = length - 1; i >= 0; i--) {int currentValue = romanValues[s[i]];if (currentValue < prevValue) {result -= currentValue;} else {result += currentValue;}prevValue = currentValue;}return result;
}

Python3版本

def romanToInt(s):romanValues = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}result = 0prevValue = 0for c in reversed(s):currentValue = romanValues[c]if currentValue < prevValue:result -= currentValueelse:result += currentValueprevValue = currentValuereturn result

Go版本

#### Go版本```go
package mainimport ("fmt""strings"
)func romanToInt(s string) int {romanValues := map[rune]int{'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000,}result := 0prevValue := 0for _, ch := range strings.ToRuneSlice(s) {currentValue := romanValues[ch]if currentValue < prevValue {result -= currentValue} else {result += currentValue}prevValue = currentValue}return result
}func main() {romanString := "MCMXCIV"integer := romanToInt(romanString)fmt.Printf("The integer representation of %s is %d\n", romanString, integer)
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是罗马数字字符串的长度。我们只需要遍历一次字符串即可得到结果。
• 空间复杂度：O(1)，因为我们使用了常量空间来存储罗马数字对应的整数值。尽管在 Python 和 Go 中使用了哈希表，但哈希表的大小是固定的，与输入字符串的长度无关，因此空间复杂度可以认为是 O(1)。

总结

方式	优点	缺点	时间复杂度	空间复杂度
方式一	实现简单、直接，效率高	需要额外处理减法情况	O(n)	O(1)

相似题目

相似题目	难度	链接
LeetCode 12. 整数转罗马数字	中等	LeetCode-12
LeetCode 415. 字符串相加	简单	LeetCode-415
LeetCode 67. 二进制求和	简单	LeetCode-67

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

• 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

• —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—

这篇关于【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---