深入解析:【Leetcode】随笔
你好呀!我是 山顶风景独好
欢迎踏入我的博客世界,能与您在此邂逅,真是缘分使然!
愿您在此停留的每一刻,都沐浴在轻松愉悦的氛围中。
这里不仅有丰富的知识和趣味横生的内容等您来探索,更是一个自由交流的平台,期待您留下独特的思考与见解。
让我们一起踏上这段探索与成长的旅程,携手挖掘更多可能,共同进步!✨
题目一:最小好进制(LeetCode 483,困难)
题目分析
对于给定的整数 n
(n >= 3
),返回 n
的一个 最小好进制。好进制是指:在该进制下,n
的表示形式为全 1 组成的字符串(例如,111
在 3 进制下表示 1*3² + 1*3 + 1 = 13
,则 3 是 13 的一个好进制)。例如:输入 n = 13
,输出 "3"
(13 在 3 进制下为 111
,且 3 是最小好进制);输入 n = 4681
,输出 "8"
;输入 n = 1000000000000000000
,输出 "999999999999999999"
。
解题思路(数学推导+二分查找)
核心是基于“好进制的数学性质”缩小查找范围,结合二分查找高效验证可能的进制,避免暴力枚举的低效:
- 好进制的数学本质:
- 若
k
是n
的好进制,且n
在k
进制下表示为m
个 1(m >= 2
),则满足公式:n = 1 + k + k² + ... + k^(m-1) = (k^m - 1) / (k - 1)
- 推导可得:
k < n^(1/(m-1))
(因k^(m-1) < n
),且m
的最大值为log2(n) + 1
(当k=2
时,m
最大,如n=13
时m=3
)。
- 若
- 查找策略:
- 从大到小遍历
m
:m
越大,k
越小(如m=log2(n)
时k
可能接近 2),优先找到的k
即为最小好进制; - 二分查找验证
k
:对每个m
,在[2, n^(1/(m-1))]
范围内二分查找k
,验证(k^m - 1)/(k - 1) == n
是否成立。
- 从大到小遍历
- 边界情况处理:
- 若遍历所有
m
未找到好进制,n
的最小好进制为n-1
(因n
在n-1
进制下恒为11
,满足好进制定义)。
- 若遍历所有
示例代码
def smallestGoodBase(n: str) -> str:
n = int(n)
# 计算m的最大可能值:m_max = floor(log2(n)) + 1
m_max = n.bit_length() # bit_length()返回n的二进制位数,log2(n)≈bit_length()-1
# 从大到小遍历m(m>=2)
for m in range(m_max, 1, -1):
# 二分查找k:范围[2, n^(1/(m-1))]
left = 2
right = int(n ** (1.0 / (m - 1))) + 1 # +1避免浮点误差
while left <= right:
mid = (left + right) // 2
# 计算sum = 1 + mid + mid² + ... + mid^(m-1),避免溢出
sum_k = 1
overflow = False
for _ in range(m - 1):
sum_k = sum_k * mid + 1
if sum_k > n:
overflow = True
break
if overflow:
right = mid - 1
elif sum_k == n:
return str(mid)
else:
left = mid + 1
# 所有m均未找到,返回n-1(恒为好进制)
return str(n - 1)
# 测试示例
n1 = "13"
print("最小好进制1:", smallestGoodBase(n1)) # 输出:"3"
n2 = "4681"
print("最小好进制2:", smallestGoodBase(n2)) # 输出:"8"
n3 = "1000000000000000000"
print("最小好进制3:", smallestGoodBase(n3)) # 输出:"999999999999999999"
代码解析
- 数学推导的核心价值:通过公式将“好进制”转化为可计算的数学关系,将
m
的范围从无限缩小到[2, log2(n)+1]
,避免暴力枚举所有可能的进制; - 二分查找的高效性:对每个
m
,二分查找k
的时间复杂度为O(log n)
,内部求和验证为O(m)
,整体复杂度O(log² n)
,即使处理1e18
级别的n
也能快速响应; - 溢出处理:求和过程中实时判断是否超过
n
,避免Python整数溢出(虽Python支持大整数,但提前终止可提升效率)。
题目二:接雨水 II(LeetCode 407,困难)
题目分析
给定一个 m x n
的矩阵,其中每个单元格的值表示该位置的高度。计算在该矩阵中能接多少体积的雨水。例如:输入矩阵 heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
,输出 4;输入 heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
,输出 10。
解题思路(最小堆+边界扩散)
核心是将“二维接雨水”转化为“边界最小高度控制积水”的问题,用最小堆维护边界高度,从最低边界向内部扩散,计算每个单元格的积水量:
- 核心原理(木桶效应):
- 二维矩阵的积水高度由“最低边界”决定,如同木桶的最短木板;
- 初始边界为矩阵的最外层单元格(这些单元格无法积水),用最小堆存储边界单元格的
(高度, 行, 列)
;
- 扩散流程:
- 标记访问:用
visited
矩阵记录已处理的单元格,避免重复计算; - 弹出最小边界:每次从堆中弹出高度最小的边界单元格
(h, i, j)
; - 遍历相邻单元格:对上下左右四个方向的相邻单元格
(ni, nj)
,若未访问:- 积水量 =
max(0, h - heightMap[ni][nj])
(若相邻单元格高度低于边界,可积水); - 将相邻单元格的“有效高度”(
max(h, heightMap[ni][nj])
)加入堆(该单元格成为新的边界),并标记为已访问;
- 积水量 =
- 标记访问:用
- 终止条件:堆为空时,所有可积水的单元格均已处理,累计积水量即为答案。
示例代码
import heapq
def trapRainWater(heightMap) -> int:
if not heightMap or len(heightMap) <= 2 or len(heightMap[0]) <= 2:
return 0 # 边界无法积水
m, n = len(heightMap), len(heightMap[0])
visited = [[False for _ in range(n)] for _ in range(m)]
heap = []
# 1. 初始化堆:加入矩阵最外层边界
# 第一行和最后一行
for j in range(n):
heapq.heappush(heap, (heightMap[0][j], 0, j))
heapq.heappush(heap, (heightMap[m-1][j], m-1, j))
visited[0][j] = True
visited[m-1][j] = True
# 第一列和最后一列(排除已加入的行)
for i in range(1, m-1):
heapq.heappush(heap, (heightMap[i][0], i, 0))
heapq.heappush(heap, (heightMap[i][n-1], i, n-1))
visited[i][0] = True
visited[i][n-1] = True
# 四向移动方向
directions = [(-1,0), (1,0), (0,-1), (0,1)]
water = 0
# 2. 从边界向内部扩散
while heap:
h, i, j = heapq.heappop(heap)
for dx, dy in directions:
ni, nj = i + dx, j + dy
# 检查相邻单元格是否在范围内且未访问
if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
visited[ni][nj] = True
# 计算积水量:边界高度 - 单元格高度(若为正)
if h > heightMap[ni][nj]:
water += h - heightMap[ni][nj]
# 新边界高度为原边界高度(积水后水位升高)
heapq.heappush(heap, (h, ni, nj))
else:
# 新边界高度为单元格自身高度(无积水)
heapq.heappush(heap, (heightMap[ni][nj], ni, nj))
return water
# 测试示例
heightMap1 = [
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
print("接雨水量1:", trapRainWater(heightMap1)) # 输出:4
heightMap2 = [
[3,3,3,3,3],
[3,2,2,2,3],
[3,2,1,2,3],
[3,2,2,2,3],
[3,3,3,3,3]
]
print("接雨水量2:", trapRainWater(heightMap2)) # 输出:10
代码解析
- 二维问题的降维思路:将复杂的二维积水问题转化为“边界最小高度优先处理”的一维逻辑,通过堆高效获取最小边界,符合“木桶效应”的物理规律;
- 时间复杂度优化:每个单元格入堆和出堆各一次,堆操作时间复杂度
O(log(mn))
,整体复杂度O(mn log(mn))
,能高效处理中等规模的矩阵; - 访问标记的必要性:
visited
矩阵确保每个单元格仅处理一次,避免重复入堆和计算,保证算法正确性和效率。
题目三:删除无效的括号(LeetCode 301,困难)
题目分析
给你一个由若干括号和字母组成的字符串 s
,删除最小数量的无效括号,使得剩下的“括号字符串”有效。返回所有可能的有效字符串(结果不重复)。例如:输入 s = "()())()"
,输出 ["(())()","()()()"]
;输入 s = "(a)())()"
,输出 ["(a())()","(a)()()"]
;输入 s = ")("
,输出 [""]
。
解题思路(BFS+剪枝+去重)
核心是通过广度优先搜索(BFS)逐层删除括号,找到“删除最少括号”的有效字符串,结合剪枝和去重避免冗余计算:
- BFS的核心逻辑:
- 层级含义:每一层代表“删除
k
个括号”后的字符串集合(k
从 0 开始递增),首次找到有效字符串的层级即为“最小删除数”; - 终止条件:当某一层出现有效字符串时,停止搜索(因BFS保证层级递增,该层的有效字符串即为删除最少括号的结果)。
- 层级含义:每一层代表“删除
- 剪枝与去重策略:
- 剪枝1:同一层级中,若两个字符串删除相同位置的同类型括号(如连续的
')'
中删除任意一个),会产生重复字符串,仅保留首次出现的字符串(用集合current_level
去重); - 剪枝2:删除括号时,仅删除“导致括号无效的括号”(如多余的
')'
或'('
),避免无意义的删除;
- 剪枝1:同一层级中,若两个字符串删除相同位置的同类型括号(如连续的
- 有效性判断:
- 遍历字符串,用计数器
balance
记录括号平衡度('('
加 1,')'
减 1),若balance < 0
则无效;遍历结束后balance == 0
则有效。
- 遍历字符串,用计数器
示例代码
def removeInvalidParentheses(s: str) -> list[str]:
def is_valid(string):
"""判断括号字符串是否有效"""
balance = 0
for c in string:
if c == '(':
balance += 1
elif c == ')':
balance -= 1
if balance < 0:
return False
return balance == 0
# BFS初始化:第一层为原字符串
current_level = {s}
while True:
# 检查当前层级是否有有效字符串
valid = [string for string in current_level if is_valid(string)]
if valid:
return valid
# 生成下一层级:删除一个括号的所有可能字符串(去重)
next_level = set()
for string in current_level:
for i in range(len(string)):
# 仅删除括号,字母不处理
if string[i] in ('(', ')'):
# 避免连续相同括号的重复删除(如"())"删除第1或2个')'结果相同)
if i > 0 and string[i] == string[i-1]:
continue
# 删除第i个字符,加入下一层
next_level.add(string[:i] + string[i+1:])
current_level = next_level
# 若下一层为空(无字符串可删),返回空列表(仅当s全为字母时)
if not current_level:
return [""]
# 测试示例
s1 = "()())()"
print("有效字符串1:", removeInvalidParentheses(s1)) # 输出:["(())()","()()()"]
s2 = "(a)())()"
print("有效字符串2:", removeInvalidParentheses(s2)) # 输出:["(a())()","(a)()()"]
s3 = ")("
print("有效字符串3:", removeInvalidParentheses(s3)) # 输出:[""]
代码解析
- BFS的优势:天然保证“最小删除数”,因层级对应删除次数,首次找到的有效字符串即为最优解,无需后续搜索;
- 去重的关键:用集合存储每一层的字符串,自动去重相同结果;同时跳过连续相同括号的重复删除(如
'())'
中删除第1或2个')'
),减少无效计算; - 有效性判断的高效性:单次判断时间复杂度
O(n)
(n
为字符串长度),结合BFS的层级遍历,整体复杂度可控,能快速处理中等长度的字符串。
✨ 本次分享的3道题覆盖“数学推导+二分(最小好进制)”“最小堆+边界扩散(接雨水II)”“BFS+剪枝(删除无效的括号)”,均为LeetCode困难题中“思维模型独特”且“工程实现有技巧”的经典案例,避免了之前重复的题目类型。若对某题的拓展场景(如好进制的最大进制、三维接雨水)或其他冷门困难题有需求,随时告诉我!
更多算法解析欢迎到CSDN主页交流:山顶风景独好