【数据结构】字符串 String

1、Leetcode13:罗马数字转整数

罗马数字包含以下七种字符: 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 到 3999 的范围内。

1
2
3
4
5
6
7
8
9
10
11
def romanToInt(s):
a = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
ans = 0
for i in range(len(s)):
if i<len(s)-1 and a[s[i]] < a[s[i+1]]: # 处理特殊规则
ans -= a[s[i]]
else:
ans += a[s[i]]
return ans

print(romanToInt('XXVII'))

2、Leetcode14:最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 “”。

示例 1:输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。

说明:所有输入只包含小写字母 a-z 。

1
2
3
4
5
6
7
8
9
10
def longestCommonPrefix(l):
if not l: return ""
s1 = min(l)
s2 = max(l)
for i, x in enumerate(s1):
if x != s2[i]:
return s2[:i]
return s1

print(longestCommonPrefix(['float', 'flo', 'flood']))

3、leetcode20:有效的括号

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:输入: “()”
输出: true

示例 2:输入: “()[]{}”
输出: true

示例 3:输入: “(]”
输出: false

示例 4:输入: “([)]”
输出: false

示例 5:输入: “{[]}”
输出: true

1
2
3
4
5
6
7
8
def isValid(s):
while '{}' in s or '()' in s or '[]' in s:
s = s.replace('{}', '')
s = s.replace('[]', '')
s = s.replace('()', '')
return s == ''

print(isValid('()[]'))

4、 leetcode58:最后一个单词的长度

给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串,返回其最后一个单词的长度。如果不存在最后一个单词,请返回 0 。
说明:一个单词是指由字母组成,但不包含任何空格的字符串。

示例:输入: “Hello World”
输出: 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def lengthOfLastWord(s):
tailOfLastWord = len(s) - 1
# 去掉末尾空格
while tailOfLastWord >= 0 and s[tailOfLastWord] == ' ':
tailOfLastWord -= 1
# LastWord首位
headOfLastWord = tailOfLastWord
while headOfLastWord >= 0 and s[headOfLastWord] != ' ':
headOfLastWord -= 1
return tailOfLastWord - headOfLastWord

def lengthOfLastWord2(s):
return len(s.split(' ')[-1]) if (len(s.split(' ')) != 0) else 0

print(lengthOfLastWord('hello world'))
print(lengthOfLastWord2('hello world'))

5、leetcode67:二进制求和

给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1 和 0。

示例 1:
输入: a = “11”, b = “1”
输出: “100”

示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def addBinary(a, b):
r, p = '', 0
# 位数补齐
d = len(b) - len(a)
a = '0' * d + a
b = '0' * -d + b
# 二进制运算
for i, j in zip(a[::-1], b[::-1]):
s = int(i) + int(j) + p
r = str(s % 2) + r
p = s // 2
# 判断进位返回运算结果
return '1' + r if p else r

print(addBinary('1011','1001'))

6、leetcode415:字符串相加

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def addStrings(a, b):
r, p = '', 0
# 位数补齐
d = len(b) - len(a)
a = '0' * d + a
b = '0' * -d + b
# 十进制运算
for i, j in zip(a[::-1], b[::-1]):
s = int(i) + int(j) + p
r = str(s % 10) + r
p = s // 10
# 判断进位返回运算结果
return '1' + r if p else r

print(addStrings('587','23'))

7、leetcode125:验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true

示例 2:
输入: “race a car”
输出: false

1
2
3
4
5
6
7
def isPalindrome(s):
if not s:
return True
s = ''.join(filter(str.isalnum, s)).lower()
return s == s[::-1]

print(isPalindrome('A man, a plan, a canal: Panama'))

8、 leetcode157:用 Read4 读取 N 个字符

假设给定 API read4 可以从文件中读取 4 个连续的字符。
现要求通过使用 read4 方法,实现 read 方法。该方法可以从文件中读取 n 个字符并将其存储到缓存数组 buf[] 中。您不能直接操作文件。

示例1:
输入: file = “abcde”, n = 5
输出: 5
解释: 当执行你的 rand 方法后,buf 需要包含 “abcde”。文件共 5 个字符,因此返回 5。

示例2:
输入: file = “leetcode”, n = 5
输出: 5
解释: 当执行你的 rand 方法后,buf 需要包含 “leetc”。文件中一共 5 个字符,因此返回 5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def read(buf, n):
tmp = ["","","",""]
cnt = 0
read4(tmp)
while tmp != ["","","",""]:
for i in range(4):
if tmp[i]:
buf[cnt] = tmp[i]
cnt += 1
if cnt == n + 1:
return n
tmp = ["","","",""]
read4(tmp)
return cnt

9、leetcode293:翻转游戏

给定一个只有 + 和 - 的字符串。
要求写出一个函数能计算出将连续的两个 “++” 反转成 “–”的所有情况。

示例:
输入: s = “++++”
输出:
[
“–++”,
“+–+”,
“++–”
]

1
2
3
4
5
6
7
8
def generatePossibleNextMoves(s):
ans=[]
for i in range(len(s)-1):
if s[i]==s[i+1]=='+':
ans.append(s[:i]+'--'+s[i+2:])
return ans

print(generatePossibleNextMoves('+++++'))

10、leetcode344:反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例:
输入:[“h”,”e”,”l”,”l”,”o”]
输出:[“o”,”l”,”l”,”e”,”h”]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def reverseString1(s):
s.reverse()
return s

def reverseString2(s):
s[0::] = s[::-1]
return s

def reverseString3(s):
i, j = 0, len(s) - 1
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
return s

print(reverseString1(list('abcdef')))
print(reverseString2(list('abcdef')))
print(reverseString3(list('abcdef')))

11、leetcode345:反转字符串中的元音字母

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例:
输入: “hello”
输出: “holle”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def reverseVowels(s):
seed = "aeiouAEIOU" # 元音中还有大小写之分
s = list(s)
l, r = 0, len(s)-1
while l < r:
if s[l] not in seed:
l += 1
if s[r] not in seed:
r -= 1
if s[l] in seed and s[r] in seed:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
return "".join(s)

print(reverseVowels(list('hello')))

12、leetcode383:赎金信

为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成,返回 true ;否则返回 false。

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
def canConstruct1(ransomNote, magazine):
'''
统计两个字符串的char,进行减法操作,如果有剩余证明结果是false。
'''
import collections
return not collections.Counter(ransomNote) - collections.Counter(magazine)

def canConstruct2(ransomNote, magazine):
magazine_dict = {}
# 哈希表存储magazine字符及个数
for c in magazine:
if c in magazine_dict:
magazine_dict[c] += 1
else:
magazine_dict[c] = 1

for c in ransomNote:
if c in magazine_dict and magazine_dict[c] > 0:
magazine_dict[c] -= 1
else:
return False
return True

print(canConstruct1('abcc','aabc'))
print(canConstruct2('abcc','aabc'))

13、leetcode387:字符串中的第一个唯一字符

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

示例1:
s = “leetcode”
返回 0

示例2:
s = “loveleetcode”
返回 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def firstUniqChar1(s):
# 计算字符出现次数
dic = {c: s.count(c) for c in set(s)}
# 找到并返回首个满足出现次数为一的字符
for i, c in enumerate(s):
if dic[c] == 1:
return i
return -1

def firstUniqChar2(s):
# 先定义一个最小索引, 默认值是最后的字符索引
min_unique_char_index = len(s)
# 已知字符串由小写字母构成,则遍历a-z
for c in "abcdefghijklmnopqrstuvwxyz":
i = s.find(c)
# 分别从目标的字符串头和字符串尾查找对应字母的索引;如果两索引相等,则说明是单一字符
if i != -1 and i == s.rfind(c):
# 更新最新的最小索引
min_unique_char_index = min(min_unique_char_index, i)
return min_unique_char_index if min_unique_char_index != len(s) else -1

print(firstUniqChar1('loveleetcode'))
print(firstUniqChar2('loveleetcode'))

14、leetcode443:压缩字符串

给定一组字符,使用原地算法将其压缩。压缩后的长度必须始终小于或等于原数组长度。数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。
在完成原地修改输入数组后,返回数组的新长度。

示例 1:
输入:
[“a”,”a”,”b”,”b”,”c”,”c”,”c”]
输出:
返回6,输入数组的前6个字符应该是:[“a”,”2”,”b”,”2”,”c”,”3”]
说明:
“aa”被”a2”替代。”bb”被”b2”替代。”ccc”被”c3”替代。

示例 2:
输入:
[“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”]
输出:
返回4,输入数组的前4个字符应该是:[“a”,”b”,”1”,”2”]。
说明:
由于字符”a”不重复,所以不会被压缩。”bbbbbbbbbbbb”被“b12”替代。
注意每个数字在数组中都有它自己的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
def compress(chars):
count = 1
length = len(chars)
for index in range(length-1, -1, -1):
if index > 0 and chars[index] == chars[index-1]:
count += 1
else:
end = index+count
chars[index: end] = [chars[index]] if count == 1 else [chars[index]] + list(str(count))
count = 1
return len(chars)

print(compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"]))

15、leetcode459:重复的子字符串

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。

示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2:
输入: “aba”
输出: False

1
2
3
4
5
6
7
8
9
10
11
12
def repeatedSubstringPattern1(s):
return (s + s)[1:-1].count(s) != 0

def repeatedSubstringPattern2(s):
return (s + s)[1:-1].find(s) != -1

def repeatedSubstringPattern3(s):
return s in (s + s)[1: -1]

print(repeatedSubstringPattern1('aba'))
print(repeatedSubstringPattern2('aba'))
print(repeatedSubstringPattern3('aba'))

16、leetcode520:检测大写字母

给定一个单词,你需要判断单词的大写使用是否正确。
我们定义,在以下情况时,单词的大写用法是正确的:
全部字母都是大写,比如”USA”。
单词中所有字母都不是大写,比如”leetcode”。
如果单词不只含有一个字母,只有首字母大写, 比如 “Google”。
否则,我们定义这个单词没有正确使用大写字母。

示例 1:
输入: “USA”
输出: True

示例 2:
输入: “FlaG”
输出: False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def detectCapitalUse1(word):
a = word
b = word[1:]
if a == a.upper() or a == a.lower():
return True
elif a[0] == a[0].upper() and b == b.lower():
return True
else:
return False

def detectCapitalUse2(word):
return word.isupper() or word.islower() or word.istitle()

print(detectCapitalUse1('aBa'))
print(detectCapitalUse2('aBa'))
0%