文章目录
🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨
题目一：旋转图像（LeetCode 48）
题目分析：
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。例如：输入matrix = [[1,2,3],[4,5,6],[7,8,9]]，输出[[7,4,1],[8,5,2],[9,6,3]]。
解题思路：
先转置矩阵：将矩阵的行和列互换（即matrix[i][j]与matrix[j][i]交换）。
再反转每一行：将转置后的矩阵中每一行的元素反转（即matrix[i][j]与matrix[i][n-1-j]交换）。
通过这两步操作，可实现矩阵的顺时针旋转90度，且整个过程在原矩阵上进行，无需额外空间。
示例代码：
def rotate(matrix):
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 第一步：转置矩阵（行变列，列变行）
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 第二步：反转每一行
for i in range(n):
matrix[i].reverse()
# 测试示例
if __name__ == "__main__":
matrix1 = [[1,2,3],[4,5,6],[7,8,9]]
rotate(matrix1)
print("旋转后的矩阵1：", matrix1) # 输出：[[7,4,1],[8,5,2],[9,6,3]]
matrix2 = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
rotate(matrix2)
print("旋转后的矩阵2：", matrix2) # 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
代码解析：
转置矩阵时，通过双层循环遍历，仅交换i <= j的元素（避免重复交换），将matrix[i][j]与matrix[j][i]互换，实现行和列的转换。
反转每一行利用Python列表的reverse()方法，直接在原列表上反转元素顺序。
整个算法时间复杂度为O(n²)（n为矩阵边长，需遍历所有元素两次），空间复杂度为O(1)（仅使用常数额外空间）。
题目二：字母异位词分组（LeetCode 49）
题目分析：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。例如：输入strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]，输出[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]。
解题思路：
使用哈希表（字典）分组：以排序后的字符串作为键，原字符串作为值，将字母异位词分到同一组。
排序的作用：字母异位词排序后会得到相同的字符串（如"eat"和"tea"排序后都是"aet"），因此可作为分组的依据。
遍历所有字符串：对每个字符串排序后，将其加入对应键的列表中，最终返回字典中所有的值组成的列表。
示例代码：
def groupAnagrams(strs):
from collections import defaultdict
# 创建默认字典，键为排序后的字符串，值为字母异位词列表
anagram_groups = defaultdict(list)
for s in strs:
# 对字符串排序，得到键（如"eat"排序后为"aet"）
sorted_s = ''.join(sorted(s))
# 将原字符串加入对应分组
anagram_groups[sorted_s].append(s)
# 返回所有分组组成的列表
return list(anagram_groups.values())
# 测试示例
if __name__ == "__main__":
strs = ["eat","tea","tan","ate","nat","bat"]
result = groupAnagrams(strs)
print("字母异位词分组结果：", result) # 输出：[["eat","tea","ate"], ["tan","nat"], ["bat"]]（顺序可能不同）
代码解析：
使用collections.defaultdict创建字典，避免处理键不存在的情况，默认值为列表。
对每个字符串s，通过sorted(s)得到排序后的字符列表，再用’'.join()转换为字符串作为键，确保字母异位词有相同的键。
将原字符串s加入对应键的列表中，最后通过list(anagram_groups.values())得到分组结果。
时间复杂度为O(n×k log k)（n为字符串数量，k为字符串的最大长度，排序每个字符串需O(k log k)时间），空间复杂度为O(n×k)（存储所有字符串）。
题目三：括号生成（LeetCode 22）
题目分析：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。例如：输入n = 3，输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]。
解题思路：
回溯法：通过递归生成所有可能的括号组合，同时加入约束条件确保有效性。
约束条件：
- 左括号数量不能超过n；
- 右括号数量不能超过左括号数量（保证括号有效闭合）。
递归终止条件：当生成的括号长度为2n时（即n对括号），将其加入结果列表。
递归过程：在每一步选择添加左括号（若未达上限）或右括号（若符合约束），继续递归直到生成完整括号组合。
示例代码：
def generateParenthesis(n):
result = []
def backtrack(current, left, right):
# 递归终止：生成了n对括号
if len(current) == 2 * n:
result.append(current)
return
# 若左括号数量不足n，可添加左括号
if left < n:
backtrack(current + '(', left + 1, right)
# 若右括号数量小于左括号，可添加右括号（保证有效）
if right < left:
backtrack(current + ')', left, right + 1)
# 从空字符串、0个左括号、0个右括号开始递归
backtrack("", 0, 0)
return result
# 测试示例
if __name__ == "__main__":
n = 3
result = generateParenthesis(n)
print(f"{n}对括号的所有有效组合：", result)
# 输出：["((()))","(()())","(())()","()(())","()()()"]
代码解析：
定义回溯函数backtrack，参数current为当前生成的括号字符串，left和right分别为已使用的左、右括号数量。
当current长度为2n时，说明生成了完整的n对括号，加入结果列表。
递归分支：
- 若left < n，可添加左括号，递归调用backtrack(current + ‘(’, left + 1, right)；
- 若right < left，可添加右括号（确保不会出现单独的右括号无法闭合），递归调用backtrack(current + ‘)’, left, right + 1)。
初始调用backtrack(“”, 0, 0)，从空字符串开始生成所有有效组合。
时间复杂度为O(4ⁿ / √n)（卡特兰数，生成的有效组合数量为第n个卡特兰数），空间复杂度为O(n)（递归栈深度为2n）。
✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍