字符串相关题目
# 罗马数字转整数
See More
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。
示例 1:
输入: s = "III" 输出: 3
示例 2:
输入: s = "IV" 输出: 4
示例 3:
输入: s = "IX" 输出: 9
示例 4:
输入: s = "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
# 解答
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function (s) {
// 首先建立罗马字符对应的数值映射
let map = new Map()
map.set('I', 1)
map.set('V', 5)
map.set('X', 10)
map.set('L', 50)
map.set('C', 100)
map.set('D', 500)
map.set('M', 1000)
let len = s.length
let ans = 0
// 遍历给定的字符串
for (let i = 0; i < len; i++) {
// 获取当前索引的罗马数字对应的值
let value = map.get(s[i])
// 如果当前罗马字符对应的值小于下一个位置上罗马字符对应的值，就代表要减去当前值
// 为了防止索引越界，需要判断当前索引是否是在[0, n-1] 范围内
if (i < len - 1 && value < map.get(s[i + 1])) {
ans -= value
} else {
ans += value
}
}
return ans
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 最长公共前缀
See More
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl" 示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
# 解答
var longestCommonPrefix = function (strs) {
// 以第一个字符串为基准
let ans = strs[0]
// 依次比较剩余的每一个字符串
for (let i = 1; i < strs.length; i++) {
// 从字符串的第0个位置开始依次比较
let j = 0
// 内层循环最多比较两个字符的长度的最小值次
for (; j < strs[i].length && j < ans.length; j++) {
// 只要有一个字符不相等，就跳出循环
if (ans[j] !== strs[i][j]) break
}
// 改变基准的值
ans = ans.subStr(0, j)
// 如果基准值已经是空串了，则直接返回，没必要再继续对比
if (ans === '') return ''
}
return ans
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 括号匹配
# 解答
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
// 存储括号映射
let map = new Map([
['(', ')'],
['[', ']'],
['{', '}'],
])
let stack = []
for (let i = 0; i < s.length; i++) {
// 利用栈来存储左括号
if (['(', '[', '{'].includes(s[i])) {
stack.push(s[i])
} else {
// 遇到右括号就从栈中弹出栈顶元素进行匹配测试
let c = stack.pop()
// 不匹配则直接返回false
if (map.get(c) !== s[i]) return false
}
}
// 如果都匹配成功，栈最终应该是空的
return !stack.length
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 实现 strStr() 函数 - 字符串匹配
See More
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll" 输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba" 输出：-1
示例 3：
输入：haystack = "", needle = "" 输出：0
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-strstr
# 解答
- 暴力解法
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle) {
if (needle == '') return 0
let start = needle[0]
let hlen = haystack.length
let nlen = needle.length
for (let i = 0; i < hlen; i++) {
// 如果第一个字符匹配成功，则继续比较子串中的其它字符
if (haystack[i] === start) {
// 是否匹配成功的标记
let flag = true
// 遍历子串
for (let j = 1; j < nlen; j++) {
// 有一个字符匹配失败就跳出内部循环，并继续外层循环
if (haystack[i + j] !== needle[j]) {
flag = false
break
}
}
if (flag) return i
}
}
return -1
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29