- 力扣面试经典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：就地翻转
- 先翻转整个序列，然后去除所有多余空格，最后翻转每个单词。示意图如下
- 下面给出示例代码
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：直接构造
- 直接计算输出字符串中各个字符对应输入序列中的字符下标，直接构造出结果。下标对应示意图如下
其中 t = 2 r − 2 t=2r-2 t=2r−2 是 Z 字形变换的周期， r r r 是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+3tnumRow - 下面给出代码
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)