字符串

发表于 | 分类于 ， | 评论数：

替换空格

题目

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

思路

遍历

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        target = ""
        i = 0
        while i < len(s):
            char = s[i]
            if char == " ":
                char = "%20"
            target += char
            i += 1 
        return target

字符串的排列

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路

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

代码

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
class Solution:
    def __init__(self):
        self.result = []
    def Permutation(self, ss):
        # write code here
        if len(ss) == 0:
            return []
        # 进行切分组合
        self.PermutationCore(list(ss), 0)
        sorted(self.result)
        return self.result
    def PermutationCore(self, char_list, begin):
        # 递归的终止条件,当起始位置等于字符串长度的时候，已经完成了这一次拼接
        if begin == len(char_list):
            self.result.append("".join(char_list))
            return
        for i in range(begin, len(char_list)):
            # 过滤掉字符串中和首字母相等的元素再排在首位，避免重复递归
            if i != begin and char_list[i] == char_list[begin]:
                continue
            # 通过交换的方式，确定所有可能得首字母
            char_list = list("".join(char_list))
            char_list[i], char_list[begin] = char_list[begin], char_list[i]
            # 将剩下的字符递归进行排列组合
            self.PermutationCore(char_list, begin+1)

第一个只出现一次的字符

题目

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

思路

建立一个哈希表，第一次扫描的时候，统计每个字符的出现次数。第二次扫描的时候，如果该字符出现的次数为1，则返回这个字符的位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        length = len(s)
        if length == 0:
            return -1
        item = {}
        for i in range(length):
            if s[i] not in item.keys():
                item[s[i]] = 1
            else:
                item[s[i]] += 1
        for i in range(length):
            if item[s[i]] == 1:
                return i
        return -1

左旋转字符串

题目

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

思路

裁剪

代码

1
2
3
4
5
6
7
8
class Solution:
    def LeftRotateString(self, s, n):
        length = len(s)
        if n <= 0 or length == 0:
            return s
        if n > length:
            n = n % length
        return s[n:] + s[:n]

翻转单词顺序序列

题目

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

思路

重新拼接

代码

1
2
3
4
5
class Solution:
    def ReverseSentence(self, s):
        # write code here
        s_list = s.split(' ')
        return ' '.join(s_list[::-1])

把字符串转换成整数

题目

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

思路

这道题要考虑全面，对异常值要做出处理。

对于这个题目，需要注意的要点有：

指针是否为空指针以及字符串是否为空字符串；
字符串对于正负号的处理；
输入值是否为合法值，即小于等于’9’，大于等于’0’；
int为32位，需要判断是否溢出；
使用错误标志，区分合法值0和非法值0。
代码中用两个函数来实现该功能，其中标志位g_nStatus用来表示是否为异常输出，minus标志位用来表示是否为负数。

代码

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
class Solution:
    def StrToInt(self, s):
        # write code here
        length = len(s)
        if length == 0:
            return 0
        else:
            # 设置负数和是否有正负符号标志位
            minus = False
            flag = False
            if s[0] == '+':
                flag = True
            if s[0] == '-':
                flag = True
                minus = True
            begin = 0
            # 如果有正负符号标志位, 数字从1开始
            if flag:
                begin = 1
            num = 0
            # 确定是否有负数系数
            minus = -1 if minus else 1
            # 不断遍历数字，将其*10 + 个数位
            for each in s[begin:]:
                # 如果数字大于0 并小于9, 否则为非法字符
                if each >= '0' and each <= '9':
                    # 用 ord 计算字符和0的二进制数字差
                    num = num * 10 + minus * (ord(each) - ord('0'))
                else:
                    num = 0
                    break
            return num

正则表达式匹配

题目

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

思路

第一种方法:如果模式串中有星号，它会出现在第二个位置，即 \text{pattern[1]}pattern[1] 。
这种情况下，我们可以直接忽略模式串中这一部分，或者删除匹配串的第一个字符，前提是它能够匹配模式串当前位置字符，
即 \text{pattern[0]}pattern[0] 。如果两种操作中有任何一种使得剩下的字符串能匹配，那么初始时，匹配串和模式串就可以被匹配。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def match(self, text, pattern):
        # 如果没有匹配符号，并且没有了字符串，递归终结条件
        if not pattern:
            return not text

        # 判断第一个字符和匹配符是否相匹配
        first_match = bool(text) and pattern[0] in {text[0], '.'}

        # 如果第二个字符是*
        if len(pattern) >= 2 and pattern[1] == '*':
            return  (first_match and self.match(text[1:], pattern)) or self.match(text, pattern[2:])
            # 如果不是*
        else:
            return first_match and self.match(text[1:], pattern[1:])

表示数值的字符串

题目

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

思路

这道题还是比较简单的。表示数值的字符串遵循如下模式：

[sign]integral-digits[.[fractional-digits]][e|E[sign]exponential-digits]

其中，(‘[‘和’]’之间的为可有可无的部分)。

在数值之前可能有一个表示正负的’+’或者’-‘。接下来是若干个0到9的数位表示数值的整数部分（在某些小数里可能没有数值的整数部分）。如果数值是一个小数，那么在小数后面可能会有若干个0到9的数位表示数值的小数部分。如果数值用科学记数法表示，接下来是一个’e’或者’E’，以及紧跟着的一个整数（可以有正负号）表示指数。

判断一个字符串是否符合上述模式时，首先看第一个字符是不是正负号。如果是，在字符串上移动一个字符，继续扫描剩余的字符串中0到9的数位。如果是一个小数，则将遇到小数点。另外，如果是用科学记数法表示的数值，在整数或者小数的后面还有可能遇到’e’或者’E’。

代码

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
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        # 标记符号、小数点、e是否出现过
        sign = False
        decimal = False
        hasE = False
        for i in range(len(s)):
            # 如果字符是e，进行异常条件判断
            if s[i] == 'e' or s[i] == 'E':
                if i == len(s)-1:     # e后面一定要接数字, 如果是最后一位，直接报错
                    return False
                if hasE:      # 不能同时存在两个e
                    return False
                hasE = True
            # 如果字符是+-, 进行异常条件判断
            elif s[i] == '+' or s[i] == '-': 
                if sign and s[i-1] != 'e' and s[i-1] != 'E':  # 第二次出现+-符号，则必须紧接在e之后
                    return False
                elif sign == False and i > 0 and s[i-1] != 'e' and s[i-1] != 'E':  # 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
                    return False
                sign = True
            # 如果字符是小数点，进行异常条件的判断
            elif s[i] == '.':
                if (hasE or decimal):      # e后面不能接小数点，小数点不能出现两次
                    return False
                decimal = True
            # 如果字符是非法字符，进行异常条件判断
            elif s[i] < '0' or s[i] > '9':
                return False
        return True
刘小恺(Kyle) wechat
如有疑问可联系博主