【leetcode】字符串 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'))