• 力扣面试经典150题
  • 在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题,安装 Debug LeetCode 插件可以免费 debug
  • 本文使用 python 语言解题,文中 “数组” 通常指 python 列表;文中 “指针” 通常指 python 列表索引

21. [中等] 反转字符串中的单词

21.1 解法1:拆解再反向组合

  • 直观的思路是过滤掉空格分解出各个单词,然后反向组合得到结果。这可以通过 python 的语法特性解决
    def reverseWords(self, s: str) -> str:
    	return " ".join(reversed(s.split()))
    
  • 手动实现这个过程也很简单
    def reverseWords(self, s: str) -> str:
    	# 先拆解出各个单词
    	words = []
    	word = ''
    	for c in s:
    	    if c == ' ':
    	        if word != '':
    	            words.append(word)
    	            word = ''
    	    else:
    	        word += c 
    	if word != '':
    	    words.append(word)
    	
    	# 反向组合
    	s = ''
    	for i in range(len(words)-1, 0, -1):
    	    s += words[i] + ' '
    	s += words[0]
    	return s
    
  • 时间复杂度 O ( n ) O(n) O(n);空间复杂度 O ( n ) O(n) O(n)

21.2 解法2:就地翻转

  • 先翻转整个序列,然后去除所有多余空格,最后翻转每个单词。示意图如下
    力扣面试经典150 —— 21-25题-LMLPHP
  • 下面给出示例代码
    class Solution:
        def trim_spaces(self, s: str) -> list:
            left, right = 0, len(s) - 1
            # 去掉字符串开头的空白字符
            while left <= right and s[left] == ' ':
                left += 1
            
            # 去掉字符串末尾的空白字符
            while left <= right and s[right] == ' ':
                right -= 1
            
            # 将字符串间多余的空白字符去除
            output = []
            while left <= right:
                if s[left] != ' ':
                    output.append(s[left])
                elif output[-1] != ' ':
                    output.append(s[left])
                left += 1
            
            return output
                
        def reverse(self, l: list, left: int, right: int) -> None:
            while left < right:
                l[left], l[right] = l[right], l[left]
                left, right = left + 1, right - 1
                
        def reverse_each_word(self, l: list) -> None:
            n = len(l)
            start = end = 0
            
            while start < n:
                # 循环至单词的末尾
                while end < n and l[end] != ' ':
                    end += 1
                # 翻转单词
                self.reverse(l, start, end - 1)
                # 更新start,去找下一个单词
                start = end + 1
                end += 1
                    
        def reverseWords(self, s: str) -> str:
            l = self.trim_spaces(s)
            
            # 翻转字符串
            self.reverse(l, 0, len(l) - 1)
            
            # 翻转每个单词
            self.reverse_each_word(l)
            
            return ''.join(l)
    
  • 时间复杂度 O ( n ) O(n) O(n);空间复杂度 O ( n ) O(n) O(n)

22. [中等] Z 字形变换

22.1 解法1:按行归纳

  • numRow 为 n,注意到 Z 排列的字符行号变化规律为:0,1,…,n-2,n-1,n-2,…,1,0,1…,可以利用该规律得到输入字符串中各个字符 Z 排列后所在的行位置并将其按行归纳,最后遍历每一行构造输出
    class Solution:
        def convert(self, s: str, numRows: int) -> str:
            if numRows == 1:
                return s
    
            # row_items 是一个列表的列表,其中每个列表存储一行的元素
            row_items = []
            for _ in range(numRows):
                row_items.append([])
    
            # 按 Z 字顺序确定各个元素所在行,填入 row_items 中对应列表
            delta = 1
            row = 0
            for item in s:
                row_items[row].append(item)
                row += delta
                if row == 0 or row == numRows - 1:
                    delta = -delta
    
            # 按行序遍历 row_items 并构造输出
            ans = ''
            for row in row_items:
                for item in row:
                    ans += item
            
            return ans
    
  • 时间复杂度 O ( n ) O(n) O(n);空间复杂度 O ( n ) O(n) O(n)

22.2 解法2:直接构造

  • 直接计算输出字符串中各个字符对应输入序列中的字符下标,直接构造出结果。下标对应示意图如下
    0             0+t                    0+2t                     0+3t
    1      t-1    1+t            0+2t-1  1+2t            0+3t-1   1+3t
    2  t-2        2+t  0+2t-2            2+2t  0+3t-2             2+3t  
    3             3+t                    3+2t                     3+3t
    
    其中 t = 2 r − 2 t=2r-2 t=2r2 是 Z 字形变换的周期, r r rnumRow
  • 下面给出代码
    class Solution:
        def convert(self, s: str, numRows: int) -> str:
            n, r = len(s), numRows
            if r == 1 or r >= n:
                return s
            t = r * 2 - 2
            ans = []
            for i in range(r):  # 枚举矩阵的行
                for j in range(0, n - i, t):  # 枚举每个周期的起始下标
                    ans.append(s[j + i])  # 当前周期的第一个字符
                    if 0 < i < r - 1 and j + t - i < n:
                        ans.append(s[j + t - i])  # 当前周期的第二个字符
            return ''.join(ans)
    
  • 时间复杂度 O ( n ) O(n) O(n);空间复杂度 O ( 1 ) O(1) O(1)(返回值不计入空间复杂度)

23. [简单] 找出字符串中第一个匹配项的下标

23.1 解法1:暴力匹配

  • 让字符串 needle 和 haystack 的所有子串逐一比较,这可以通过 python 语法简单的实现
    class Solution:
        def strStr(self, haystack: str, needle: str) -> int:
            for i in range(0,len(haystack)-len(needle)+1):
                if haystack[i:i+len(needle)] == needle:
                    return i
            return -1
    
  • 为了提高效率,我们仅在首字符匹配时才考虑进一步匹配,并在匹配失败时提前结束
    class Solution:
        def strStr(self, haystack: str, needle: str) -> int:        
            def _check(haystack_sub):
                # 检查 haystack_sub 首部能否和 needle 匹配
                if len(needle) > len(haystack_sub):
                    return False
                for h, n in zip(haystack_sub, needle):
                    if h != n:
                        return False
                return True
    
            # 遍历每一个位置判断能否匹配
            for i, char in enumerate(haystack):
                if char == needle[0]:
                    if _check(haystack[i:]):
                        return i
            
            return -1
    
  • 时间复杂度 O ( n × m ) O(n \times m) O(n×m)(n,m为两个字符串的长度);空间复杂度 O ( 1 ) O(1) O(1)

24. [困难] 文本左右对齐

24.1 解法1:模拟

  • 直接根据题目要求模拟即可,详见以下代码注释

    class Solution:
        def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
            # 将单词划分到每一行
            word_row, word_lens = [], []
            l = 0
            row = []
            for word in words:
                if l + len(word) + len(row) <= maxWidth:
                    row.append(word)
                    l += len(word)
                else:
                    word_row.append(row)
                    word_lens.append(l)
                    l = len(word)
                    row = [word, ]
            word_row.append(row)
    
            # 将每一行的单词列表转换为字符串
            ans = []
            for row, word_l in zip(word_row[:-1], word_lens):
                # 计算所有空格长度
                space_num = len(row) - 1            # 空格数量
                if space_num != 0:
                    space_lens = []                 # 各个空格长度列表
                    space_room = maxWidth - word_l  # 空格总长度
                    if space_room % space_num == 0:
                        # 能整除则直接分配空格长度
                        space_lens = [int(space_room / space_num)] * space_num
                    else:
                        # 不能整除,则先放置平均长度向上取整长度,直到剩下的长度可以被平均长度向下取整整除
                        space_len = space_room / space_num
                        space_len_f, space_len_c = int(space_len), int(space_len) + 1    
                        while True:
                            space_lens.append(space_len_c)
                            space_room -= space_len_c
                            space_num -= 1
                            if space_room % space_num == 0:
                                space_lens.extend([space_len_f]*int(space_room/space_len_f))
                                break
                    
                    # 将空格和单词组成字符串
                    row_ans = row[0]
                    for word, space_len in zip(row[1:], space_lens):
                        row_ans += ' ' * space_len
                        row_ans += word     
                    ans.append(row_ans)
                else:
                    # 行内只有一个单词,在后面加空格补充长度即可
                    ans.append(row[0] + ' '*(maxWidth - len(row[0])))
        
            # 处理最后一行的特殊情况
            row_ans = ' '.join(word_row[-1])
            row_ans += ' ' * (maxWidth - len(row_ans))
            ans.append(row_ans)
            return ans
    
  • 时间复杂度 O ( m ) O(m) O(m);空间复杂度 O ( m ) O(m) O(m) m m m 是数组 words 中所有字符串长度之和)

25. [简单]:验证回文串:

25.1 解法1:双指针原位判断

  • 使用左右两个指针从首尾开始向内扫描,检查是否满足回文串定义,指针移动过程中跳过非字母数字的无关字符
    class Solution:
        def isPalindrome(self, s: str) -> bool:
            # 初始化左右指针
            left, right = 0, len(s)-1
            # 左右指针移动到第一个字母/数字位置
            while left < len(s) and not (s[left].isalpha() or s[left].isnumeric()):
                left += 1
            while right > 0 and not (s[right].isalpha() or s[right].isnumeric()):
                right -= 1
            # 检查是否满足题目回文特性,移动指针时跳过非字母/数字位置
            while left < right:
                if s[left].lower() == s[right].lower():
                    left += 1
                    while not (s[left].isalpha() or s[left].isnumeric()):
                        left += 1
                    right -= 1
                    while not (s[right].isalpha() or s[right].isnumeric()):
                        right -= 1
                else:
                    return False
            return True
    
  • 时间复杂度 O ( n ) O(n) O(n) n n n 是输入字符串长度);空间复杂度 O ( 1 ) O(1) O(1)
03-21 20:26