当前位置：首页 > news >正文

初学python的我开始Leetcode题10-2

news 2025/6/21 19:05:38

提示：100道LeetCode热题-10-2主要是回溯相关，包括四题：括号生成、单词搜索、分割回文串、N 皇后。由于初学，所以我的代码部分仅供参考。

前言

期末周过去，小学期到来，在这个难得的空闲，Leetcode启动！

提示：以下是本篇文章正文内容，下面结果代码仅供参考

题目1：括号生成

1.题目要求：

题目如下：

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：

1 <= n <= 8

代码框架已经提供如下：

class Solution(object):

def generateParenthesis(self, n):

"""

:type n: int

:rtype: List[str]

"""

2.结果代码：

class Solution:def generateParenthesis(self, n):def backtrack(current, left, right):if left == n and right == n:result.append(current)returnif left < n:backtrack(current + "(", left + 1, right)if right < left:backtrack(current + ")", left, right + 1)result = []backtrack("", 0, 0)return result

说明：

题目要求生成所有可能的 有效括号组合，给定括号对数 n。有效括号组合需要满足以下条件：

每个左括号 '(' 必须有一个对应的右括号 ')'。
在任何时刻，右括号的数量不能超过左括号的数量。

具体实现：

递归与回溯：
- 使用递归函数逐步构建括号字符串。
- 在递归过程中，根据当前的左括号和右括号数量，决定是否可以添加左括号或右括号。
- 当左括号和右括号的数量都达到 n 时，说明当前字符串是一个有效的括号组合，将其加入结果列表。
条件限制：
- 左括号数量限制：左括号的数量不能超过 n。
- 右括号数量限制：在任何时刻，右括号的数量不能超过左括号的数量。

题目2：单词搜索

1.题目要求：

题目如下：

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

代码框架已经提供如下：

class Solution(object):

def exist(self, board, word):

"""

:type board: List[List[str]]

:type word: str

:rtype: bool

"""

2.结果代码：

from collections import Counterclass Solution:def exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool"""# 统计 board 中所有字符的出现次数cnt = Counter(c for row in board for c in row)# 如果 board 中的字符不足以构成 word，直接返回 Falseif not cnt >= Counter(word):return False# 如果 word 的第一个字符在 board 中出现的次数比最后一个字符多，反转 wordif cnt[word[0]] > cnt[word[-1]]:word = word[::-1]# 获取 board 的行数和列数m, n = len(board), len(board[0])# 遍历 board 的每个单元格，尝试从每个单元格开始搜索for i in range(m):for j in range(n):if self.dfs(board, word, i, j, 0):return Truereturn Falsedef dfs(self, board, word, i, j, k):# 如果当前单元格的字符与 word 的第 k 个字符不匹配，返回 Falseif board[i][j] != word[k]:return False# 如果已经匹配到 word 的最后一个字符，返回 Trueif k == len(word) - 1:return True# 保存当前单元格的字符，并将其设置为空字符串，避免重复访问curr_char = board[i][j]board[i][j] = ''# 定义四个方向的移动向量directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]# 遍历四个方向for curr_dir in directions:new_i, new_j = i + curr_dir[0], j + curr_dir[1]# 检查新位置是否在网格范围内，并且新位置的字符不为空字符串if 0 <= new_i < len(board) and 0 <= new_j < len(board[0]) and board[new_i][new_j] != '':if self.dfs(board, word, new_i, new_j, k + 1):return True# 回溯，恢复当前单元格的字符board[i][j] = curr_charreturn False

优化说明：

字符计数优化：
- 使用 collections.Counter 统计 board 中所有字符的出现次数，并与 word 中的字符计数进行比较。如果 board 中的字符不足以构成 word，直接返回 False。
- 如果 word 的第一个字符在 board 中出现的次数比最后一个字符多，将 word 反转。这样可以减少搜索的起点数量，提高效率。
DFS 优化：
- 在搜索过程中，直接将当前单元格的字符设置为空字符串 ''，而不是使用额外的标记数组，这样可以减少空间复杂度。
- 在递归调用 dfs 时，直接传递更新后的 board，并在回溯时恢复当前单元格的字符。
边界条件优化：
- 在检查边界条件时，直接使用 new_i >= 0 and new_i < m and new_j >= 0 and new_j < n，避免了额外的越界检查。

时间复杂度：最坏情况下，需要遍历网格的每个单元格，并从每个单元格开始进行深度优先搜索。时间复杂度为 O(M×n×4^K)，其中 M 和 n 分别是网格的行数和列数，K 是单词的长度。

题目3：分割回文串

1.题目要求：

题目如下：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

代码框架已经提供如下：

class Solution(object):

def partition(self, s):

"""

:type s: str

:rtype: List[List[str]]

"""

2.结果代码：

class Solution(object):def partition(self, s):""":type s: str:rtype: List[List[str]]"""n = len(s)# dp[i] 存储字符串 s[:i] 的所有分割方案dp = [[] for _ in range(n + 1)]dp[0] = [[]]  # 初始化，空字符串的分割方案只有一个空列表# 遍历字符串的每个位置for i in range(1, n + 1):# 尝试从每个位置 j 到 i 的子串for j in range(i):# 当前子串 s[j:i]sub = s[j:i]# 如果子串是回文串if sub == sub[::-1]:# 将子串加入所有前缀分割方案for prev in dp[j]:dp[i].append(prev + [sub])return dp[-1]  # 返回最终结果

说明：

本题多种方法中选择了动态规划构建分割方案：

逻辑简洁：
- 直接通过动态规划构建所有可能的分割方案，避免了回溯算法中复杂的递归和回溯逻辑。
- 动态规划的过程更加直观，容易理解。
避免重复计算：
- 在动态规划过程中，直接利用之前计算的结果，避免了回溯算法中可能出现的重复计算。

具体实现:

动态规划表 dp：
- dp[i] 存储字符串 s[:i] 的所有分割方案。
- 初始化 dp[0] = [[]]，表示空字符串的分割方案只有一个空列表。
外层循环：
- 遍历字符串的每个位置 i，从 1 到 n。
内层循环：
- 尝试从每个位置 j 到 i 的子串 s[j:i]。
- 如果子串是回文串（通过 sub == sub[::-1] 判断），则将子串加入所有前缀分割方案 dp[j]。
结果：
- 最终结果存储在 dp[-1] 中，即 s[:n] 的所有分割方案。

时间复杂度：
- 动态规划的时间复杂度为 O(n3)，其中：
  - 外层循环 O(n)。
  - 内层循环 O(n)。
  - 每次判断回文串的时间复杂度为 O(n)

题目4：N 皇后

1.题目要求：

题目如下：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：

1 <= n <= 9

代码框架已经提供如下：

class Solution(object):

def solveNQueens(self, n):

"""

:type n: int

:rtype: List[List[str]]

"""

2.结果代码：

class Solution:def solveNQueens(self, n):def backtrack(row, cols, diag1, diag2, board):# 如果已经放置完所有皇后，生成当前棋盘的字符串表示if row == n:result.append(["".join(row) for row in board])return# 尝试在当前行的每一列放置皇后for col in range(n):# 检查是否冲突if col in cols or (row - col) in diag1 or (row + col) in diag2:continue# 放置皇后board[row][col] = 'Q'cols.add(col)diag1.add(row - col)diag2.add(row + col)# 递归处理下一行backtrack(row + 1, cols, diag1, diag2, board)# 回溯，移除当前皇后board[row][col] = '.'cols.remove(col)diag1.remove(row - col)diag2.remove(row + col)result = []cols = set()diag1 = set()diag2 = set()board = [['.' for _ in range(n)] for _ in range(n)]backtrack(0, cols, diag1, diag2, board)return result

N 皇后问题是一个经典的回溯算法问题。目标是在 n×n 的棋盘上放置 n 个皇后，使得它们彼此之间不能相互攻击。皇后可以攻击同一行、同一列或同一斜线上的棋子。

解题思路：

回溯算法：
- 使用递归函数逐步放置皇后。
- 在每一行尝试放置一个皇后，并检查是否满足条件（不与已放置的皇后冲突）。
- 如果当前行可以放置皇后，递归处理下一行。
- 如果某一行无法放置皇后，回溯到上一行，尝试其他位置。
冲突检查：
- 检查当前皇后是否与已放置的皇后在同一列或同一斜线上。
- 使用三个集合分别记录列、左对角线和右对角线的占用情况。
结果生成：
- 每当成功放置完所有皇后时，生成当前棋盘的字符串表示，并将其加入结果列表。

代码解析：

backtrack 函数：
- 参数：
  - row：当前处理的行。
  - cols：已占用的列。
  - diag1：已占用的左对角线（行 - 列）。
  - diag2：已占用的右对角线（行 + 列）。
  - board：当前棋盘的状态。
- 逻辑：
  - 如果当前行等于 n，说明已经成功放置完所有皇后，生成当前棋盘的字符串表示，并将其加入结果列表。
  - 尝试在当前行的每一列放置皇后：
    - 检查是否与已放置的皇后冲突（同一列或同一斜线）。
    - 如果不冲突，放置皇后，并递归处理下一行。
    - 递归返回后，回溯，移除当前皇后，尝试其他位置。
主函数：
- 初始化结果列表 result。
- 初始化集合 cols、diag1 和 diag2，分别记录已占用的列和对角线。
- 初始化棋盘 board，初始状态为全 '.'。
- 从第 0 行开始调用 backtrack 函数。