1 字符串专题

1.1 反转字符串一

  • 题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

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

示例 2： 输入：[“H”,“a”,“n”,“n”,“a”,“h”] 输出：[“h”,“a”,“n”,“n”,“a”,“H”]

  • 解题思路

其实一个库函数就能完成的reverse or [::-1]，但是不能这样

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        while(left < right):
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        return s

1.2 反转字符串二

  • 题目描述

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = “abcdefg”, k = 2 输出: “bacdfeg”

  • 解题思路

每隔2k个字符反转，某年天眼查的面试题，根基还是反转字符串


class Solution(object):
    def reverseStr(self, s, k):
        from functools import reduce
        s = list(s) # 先把字符串变成list
        # a另一种方法 a[::-1]
        def reverse(s): # 这个就是反转字符串
            left, right = 0, len(s) - 1
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
            return s
        
        # make sure we reverse each 2k elements 
        for i in range(0, len(s), 2*k): # 选择条件是每隔2k个
            s[i:(i+k)] = reverse(s[i:(i+k)]) # 递归
        
        # combine list into str.
        return reduce(lambda a, b: a+b, s) # 最后拼成字符串

1.3 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例1:

输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:

输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:

输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是“wke”，所以其长度为 3。 请注意，你的答案必须是子串的长度，“pwke”是一个子序列，不是子串。

分析：切割大法好

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        L = [] # 定义一个空的列表用来存字串
        lenth = 0
        for i in s:
            #如果字符不在列表中，追加该字符并计算列表长度
            if i not in L:
                L.append(i)
            #如果字符在列表中，从字符所在位置切分列表
            else:
                idx = L.index(i) # 获得索引的一种方式
                L = L[idx+1:]
                L.append(i)#切分之后将字符追加入列表
            current = len(L)
            lenth = max(current,lenth)
        return lenth

1.4 替换空格

  • 题目描述

请实现一个函数，把字符串 s 中的每个空格替换成“%20”。

示例 1： 输入：s = “We are happy.” 输出：“We%20are%20happy.”

  • 解题思路

其实一个replace就能搞定，但是不能这么干

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s = list(s)
        for i in range(len(s)):
            if s[i] == ' ':
                s[i] = '%20'
        return ''.join(s)

1.5 反转字符串里面的单词

  • 题目描述 给定一个字符串，逐个翻转字符串中的每个单词。

示例 1： 输入: “the sky is blue” 输出: “blue is sky the”

示例 2： 输入: " hello world! " 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3： 输入: “a good example” 输出: “example good a” 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

只是交换单词的顺序，但是单词还是原来的单词

  • 解题思路
class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(s.strip().split()[::-1])

1.6 左旋字符串

  • 题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串“abcdefg”和数字2，该函数将返回左旋转两位得到的结果“cdefgab”。

示例 1： 输入: s = “abcdefg”, k = 2 输出: “cdefgab”

示例 2： 输入: s = “lrloseumgh”, k = 6 输出: “umghlrlose”

限制： 1 <= k < s.length <= 10000

限制条件，不额外开辟空间

  • 解题思路
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[0:n]

1.7 最小覆盖字串

  • 题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 示例 2：

输入：s = “a”, t = “a” 输出：“a” 示例 3:

输入: s = “a”, t = “aa” 输出: "" 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

  • 解题思路

滑动窗口

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.defaultdict(int) # 记录t中字符出现次数
        window = collections.defaultdict(int) # 记录窗口中响应的字符出现的次数
        for c in t:
            need[c] += 1
        
        left,right = 0,0 # 初始窗口长度为0
        valid = 0 # 用于记录window中t中字符是否出现完，比如：t='abc'，window='abd',valid就等于2.代表need中应该出现的字符在window中才出现了两个，还没有出现完全

        # 记录最小覆盖子串的起始索引及长度
        start = 0
        length = len(s) + 1

        while right < len(s):
            c = s[right] # 即将加入window的字符c
            right += 1 # 右移窗口

            # 窗口内数据的一系列更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]: # window中字符c出现的次数已经达到need所需要的次数时，valid进行更新
                    valid += 1

            # 判断窗口左侧边界是否要收缩
            while valid == len(need):
                # 在这里更新最小覆盖子串
                if right-left < length:
                    start = left
                    length = right-left

                # d是将移出窗口的字符
                d = s[left]
                # 左移窗口
                left += 1
                # 进行窗口内数据的一系列更新
                if d in need:
                    if window[d] == need[d]: # 这句话和下面的window[c]-=1不能反，先判断删去的字符c的数量是不是满足need的数量，如果满足，valid将减去1。
                        valid -= 1
                    window[d] -= 1
        # 返回最小覆盖子串
        if length == len(s) + 1:
            return ''
        else:
            return s[start:start+length]

1.8 字符串转换整数

  • 题目描述

将字符串转化成为整数

例子 s=“1234” 转化后：ss=[1,2,3,4]

使用正则表达式：


^ 匹配字符串开头

[\+\-] 代表一个+字符或-字符

? 前面一个字符可有可无

\d 一个数字

+ 前面一个字符的一个或多个

\D 一个非数字字符

* 前面一个字符的0个或多个

max(min(数字, 2**31 - 1), -2**31) 用来防止结果越界

为什么可以使用正则表达式？如果整数过大溢出怎么办？

题目中描述： 假设我们的环境只能存储 32 位大小的有符号整数

首先，这个假设对于 Python 不成立，Python 不存在 32 位的 int 类型。其次，即使搜索到的字符串转32位整数可能导致溢出，我们也可以直接通过字符串判断是否存在溢出的情况（比如 try 函数 或 判断字符串长度 + 字符串比较），

class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)

正则真的好方便啊啊啊啊~

1.9 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

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

输入: [“dog”,“racecar”,“car”] 输出: "" 解释: 输入不存在公共前缀。 说明:

所有输入只包含小写字母 a-z 。 - ascii 码思路，字母是可以比较大小的 >利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        s1=min(strs)
        s2=max(strs)
        for k,v in enumerate(s1):
            if v !=s2[k]:
                return s2[:k]
        return s1
  • 解题思路2 使用 zip 根据字符串下标合并成数组， 判断合并后数组里元素是否都相同
class Solution(object):
    def longestCommonPrefix(self, strs):
        ans = ''
        for i in zip(*strs):
            if len(set(i)) == 1:
                ans += i[0]
            else:
                break
        return ans

1.10 重复的子字符串

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

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

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

示例 3: 输入: “abcabcabcabc” 输出: True 解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

  • 解题思路

第一眼看上去就是先找到字串，然后replace替换，剩下的字串为空即为true

s='abcabca'
m=""
for i in s:
    if i not in m:
        m+=i
if s.replace('abc','')=='':
    print('true')
else:
    print('false')

1.11 z形树或者N形树问题

  • 题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：


L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows); 示例 1:

输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN” 示例 2:

输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G
  • 解题思路： 题目理解: 。字符串 \(\quad s \quad\) 是以 \(Z\) 字形为顺序存储的字符串, 目标是按行打印。 \(\circ\) 设 numRows 行字符串分别为 \(s_{1}, s_{2}, \ldots, s_{n},\) 则容易发现：按顺序遍历字符串 \(s\) 时, 每个字符 \(\quad\) c 在 \(Z\) 字形中对应的 行索引 先从 \(s_{1}\) 增大至 \(s_{n},\) 再从 \(s_{n}\) 减小至 \(s_{1} \ldots \ldots\) 如此反复。 因此, 解决方案为：模拟这个行索引的变化, 在遍历 \(s\) 中把每个字符填到正确的行 res[i] 算法流程：按顺序遍历字符串 \(\quad s\);
  1. res[i] += c : 把每个字符 \(c\) 填入对应行 \(s_{i}\)
  2. i += flag : 更新当前字符 c 对应的行索引;
  3. flag = - flag : 在达到 Z 字形转折点时，执行反向。 复杂度分析： 。时间复杂度 \(O(N):\) 遍历一遍字符串 \(s\); \(\circ\) 空间复杂度 \(O(N):\) 各行字符串共占用 \(O(N)\) 额外空间。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows<2:
            return s
        res=["" for _ in range(numRows)]
        i,flag=0,-1
        for c in s:
            res[i] += c
            if i ==0 or i == numRows-1:
                flag=-flag

                i+=flag
            return "".join(res)

1.12 连续字符串计数

string = “aaabbcc” 输出：“ a3b2c2”


coded = ''
while string:
    i = 0
    while i < len(string) and string[0] == string[i]:
        i += 1
    coded += string[0]+str(i)
    string = string[i:]

print(coded)

1.13 滑动窗口模版

就感觉这个模板有点复杂

初始化窗口端点L，R，一般L为0，R为1
    初始化最优值
    while R < len(Array):
        while R < len(Array):
            R += 1              #移动右端点
            if R < len(Array):
                更新状态        
            if 状态满足条件:
                可选的更新最优值的位置
                break           #一旦满足条件即跳出
        if R == len(Array):     # 若循环是由于移动到数组末尾结束，则停止整个程序。因为之后已经不再有可能的解
            break
        while L < R:
            更新状态    # 移动左端点，需要更新状态
            L += 1
            if 状态满足条件：
                可选的更新最优值的位置
            else：  # 一旦窗口所在区间不再满足条件即跳出，去移动右端点
                break
        可选的对于L，R端点的后续处理
    return 最优值

没有什么比理解题意直接套模版更爽的，字符串这里很多题会用到滑动窗口