【经典算法】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)
}