剑指offer题解 - 字符串

Posted on | Post modified: | In
Words count in article: 2.9k

本系列为剑指offer刷题笔记，刷题平台为牛客网。

本文主要是字符串相关题目题解总结。

2.替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路

  • 思路1：开辟一个新的字符串，遍历给定字符串，当字符为空格时，在新字符串后添加%20，否则，添加原字符
  • 思路2：将字符串转换成列表，遍历字符串，当字符为空格时，依次在列表后面添加’%’，’2’，’0’；否则，添加原字符
  • 思路3：如果直接每次遇到空格添加’%20’，那么空格后面的数字就需要频繁向后移动。遇到这种移动问题，我们可以尝试先给出最终需要的长度，然后从后向前扫描，同时给定两个指针来保证定位。
    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
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    # -*- coding:utf-8 -*-
    class Solution:
        # s 源字符串
        def replaceSpace(self, s):
            # write code here
            if len(s) == 0:
                return ''
            # 思路1
            # newString = ''
            # for i in s:
            #     if i == ' ':
            #         newString += '%20'
            #     else:
            #         newString += i
            # return newString
            # 思路2：
            # lis = list(s)
            # newLis = []
            # for i in lis:
            #     if i == ' ':
            #         newLis.append('%')
            #         newLis.append('2')
            #         newLis.append('0')
            #     else:
            #         newLis.append(i)
            # return "".join(newLis)
            # 思路3 
            count = 0
            for i in s:
                if i == ' ':
                    count += 1
            newLen = len(s) + count * 2
            newStr = newLen * [None]
            indexOfNew, indexOfOri = len(newStr)-1, len(s)-1
            while indexOfNew >= 0 and indexOfNew >= indexOfOri:
                if s[indexOfOri] == ' ':
                    newStr[indexOfNew-2:indexOfNew+1] = ['%','2','0']
                    indexOfNew -= 3
                    indexOfOri -= 1
                else:
                    newStr[indexOfNew] = s[indexOfOri]
                    indexOfNew -= 1
                    indexOfOri -= 1
            return "".join(newStr)

    if __name__ == '__main__':
        result = Solution().replaceSpace('We are happy.')
        print(result)

27 字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解题思路

我们求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有字符交换。如下图所示：

上图就是分别把第一个字符a和后面的b、c等字符交换的情形。首先固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分为两部分：后面的字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。
是典型的递归思路。

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
30
31
32
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if len(ss) == 0:
            return []
        if len(ss) == 1:
            return [ss]
    #     写法1
    #     res = []
    #     self.perm(ss, res, '')
    #     uniq = list(set(res))
    #     return sorted(res)
    # def perm(self, ss, res, path):
    #     if ss == '':
    #         res.append(path)
    #     else:
    #         for i in range(len(ss)):
    #             self.perm(ss[:i] + ss[i + 1:], res, path + ss[i])
    #     写法2:
        res = []
        for i in range(len(ss)):
            if i > 1 and ss[i] == ss[i-1]:
                continue
            temp = self.Permutation(ss[:i]+ss[i+1:])
            for x in temp:
                res.append(ss[i]+x)
        return sorted(list(set(res)))

if __name__ == '__main__':
    result = Solution().Permutation('aba')
    print(result)

34 第一个只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

解题思路

思路：两轮遍历
第一轮，使用hash表，记录各字符出现的次数
第二轮，当次数为1时，返回位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if not s:
            return -1
        if len(s) == 1:
            return 0
        hash = {}
        for i in range(len(s)):
            if s[i] not in hash:
                hash[s[i]] = 1
            else:
                hash[s[i]] += 1
        for i in range(len(s)):
            if hash[s[i]] == 1:
                return i
        return -1
if __name__ == '__main__':
    result = Solution().FirstNotRepeatingChar('abcabcdef')
    print(result)

43 左旋转字符串

题目描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

解题思路

思路1：利用字符串切片
思路2：多次翻转，先将0~n-1翻转，n~len(s)-1翻转，最后将整个字符串翻转

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
# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if len(s) <= 1:
            return s
        n = n % len(s) # 处理n>len(s)的情况
        # 思路1
        # return s[k:] + s[:k]
        # 思路2
        # return (s[:n][::-1]+s[n:][::-1])[::-1]
        # 思路2
        s = list(s)
        self.reverse(s,0,n-1)
        self.reverse(s,n,len(s)-1)
        self.reverse(s,0,len(s)-1)
        return "".join(s)
    def reverse(self, s,start,end):
        while start < end:
            s[start],s[end] = s[end],s[start]
            start += 1
            end -= 1
if __name__ == '__main__':
    result = Solution().LeftRotateString('abcXYZdef',4)
    print(result)

44 翻转单词顺序序列

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

解题思路

思路1：分割成列表，然后对列表翻转，返回合并的字符串。
思路2：先翻转整个字符串，然后翻转每个单词，用两个指针记录每个单词的开始和结尾的位置。遇到 ‘ ‘ 说明单词的结尾，需要调节指针。
另外需要注意的是，字符串不能直接修改，需要转成list之后才能直接对每一位进行修改。

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
30
31
32
33
# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        if not s:
            return s
        # 思路1
        # s = s.split(' ')
        # s.reverse()
        # return " ".join(s)
        # 思路2:
        if len(s) == 0:
            return s
        s = list(s)
        self.reverse(s, 0, len(s)-1)
        start, end = 0, 0
        while end <= len(s)-1:
            while end <= len(s)-1 and s[end] != ' ':
                end += 1
            self.reverse(s, start, end-1)
            start = end+1
            end = start
        return ''.join(s)
    
    def reverse(self, s, left, right):
        i, j = left, right
        while i <= j:
            s[i], s[j] = s[j], s[i]
            i, j = i+1, j-1

if __name__ == '__main__':
    result = Solution().ReverseSentence('student. a am I')
    print(result)

49 把字符串转换成整数

题目描述

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

1
2
3
4
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0

示例1

1
2
3
4
5
6
输入
+2147483647
    1a33
输出
2147483647
    0

解题思路

思路1： 使用了ord函数
考虑首位是否有符号位
遍历字符串，如果字符串为字母，跳出循环
字符0对应的ASCII码为48，对于每个字符，求其ASCII-48

思路2：使用hash将’0’~’9’和数字0~9映射，在遍历

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
# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here
        if not s:
            return 0
        sign = 1
        if s[0] == '+' or s[0] == '-':
            if s[0] == '-':
                sign = -1
            s = s[1:]
        # 思路1
        # res = 0
        # for x in s:
        #     if x > '9' or x < '0':
        #         return 0
        #     res = res * 10 + ord(x)- 48
        # return res * sign
        # 思路2：
        dict = {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}
        res = 0
        for x in s:
            if x > '9' or x < '0':
                return 0
            res = res * 10 + dict[x]
        return res * sign
if __name__ == '__main__':
    result = Solution().StrToInt('-123')
    print(result)

52 正则表达式匹配

题目描述

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

解题思路

我们先来分析如何匹配一个字符，现在只考虑’.’，不考虑'*'：
如果字符串和模式串的当前字符相等，那么我们继续匹配它们的下一个字符；如果模式串中的字符是’.’，那么它可以匹配字符串中的任意字符，我们也可以继续匹配它们的下一个字符。

接下来，把字符'*'考虑进去，它可以匹配任意次的字符，当然出现0次也可以：
而当模式中的第二个字符是*时：
如果字符串第一个字符跟模式第一个字符匹配（包括模式串为’.’的情况），可以有3种匹配方式：

  1. 模式后移2字符，相当于x*被忽略；
  2. 字符串后移1字符，模式后移2字符，正好匹配x*中的'x'位；
  3. 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
    如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配，相当于把模式串中的当前字符和'*'忽略掉。

当模式中的第二个字符不是*时，也就是上面说的只有字符’.’的情况。

  1. 如果字符串第一个字符和模式中的第一个字符相匹配（包括模式串为’.’的情况），那么字符串和模式都后移一个字符，然后匹配剩余的。
  2. 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # -*- coding:utf-8 -*-
    class Solution:
        # s, pattern都是字符串
        def match(self, s, pattern):
            if s == pattern:
                return True
            if not pattern:
                return False
            if len(pattern) > 1 and pattern[1] == '*':
                if s and (s[0] == pattern[0] or pattern[0] == '.'):
                    return self.match(s,pattern[2:]) or self.match(s[1:],pattern[2:]) or self.match(s[1:],pattern)
                else:
                    return self.match(s,pattern[2:])
            elif s and (s[0] == pattern[0] or pattern[0] == '.'):
                return self.match(s[1:],pattern[1:])
            return False
    if __name__ == '__main__':
        result = Solution().match('a','.')
        print(result)

53 表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

解题思路

定义两个标志位，分别表示E或者e是否出现过，以及小数点.是否出现过。

  1. 以e（或E）为分隔，获得两个子字符串；e之前的字符串小数点只能出现一次；e之后的字符串不允许出现小数点；
  2. 符号位+或-只可能出现在两个子字符串的首位；
  3. e（或E）、小数点.不能出现在末尾
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # -*- coding:utf-8 -*-
    class Solution:
        # s字符串
        def isNumeric(self, s):
            # write code here
            isAllowDot = True
            isAllowE = True
            for i in range(len(s)):
                if (i==0 or s[i-1] in 'eE') and s[i] in '+-' and i < len(s)-1:
                    continue
                elif isAllowDot and s[i]=='.':
                    isAllowDot = False
                    if i >= len(s)-1 or s[i+1] not in '0123456789':
                        return False
                elif isAllowE and s[i] in 'eE':
                    isAllowDot = False
                    isAllowE = False
                    if i>=len(s)-1 or s[i+1] not in '0123456789+-':
                        return False
                elif s[i] not in '0123456789':
                    return False
            return True
Donate comment here
------------The End------------
0%